( )

NAIST-IS-MT0851100 2010 2 4

( )

CR CR CR 1980 90 CR Kerberos SSH CR CR CR CR CR CR,,, ID, NAIST-IS- MT0851100, 2010 2 4. i

On the Key Management Policy of Challenge Response Authentication Schemes Toshiya fukunaga Abstract challenge-response authentication (CRA) is an effective mechanism to achieve mutual authentication over insecure network. In CRA, one party gives some questions (challenge) to its communication opponent, and confirms validity of the opponent only if the opponent can show correct answers (response). To ensure that only a valid entity can make correct responses, CRA mechanisms are usually designed with cryptography. Protocols for CRA were eagerly studied in 1980 s and 1990 s, and implemented in practical protocols such as Kerberos and SSH. The environment and technologies have been drastically changed since then, and those old CRA protocols cannot fulfill some of recently arising requirements. The purpose of this paper is to re-examine CRA protocols in a contemporary point of view. This paper first investigates properties which are required to CRA protocols today, and points out problems in conventional CRA protocols. After that, new CRA protocols are proposed which are safe and suitable for current systems. Keywords: challenge-response authentication, mutual authentication, protocol, ID-base cryptgraphy, availability Master s Thesis, Department of Information Processing, Graduate School of Information Science, Nara Institute of Science and Technology, NAIST-IS-MT0851100, February 4, 2010. ii

1. 1 2. 6 2.1................. 6 2.2................... 8 3. CR 11 3.1 CR........................ 11 3.2 CR......................... 13 4. CR 16 4.1 on-the-fly CR............. 17 4.2 CR.................. 19 4.3 ID CR................ 21 5. 25 26 27 iii

1 on-the-fly CR................ 18 2 CR................. 20 3 ID CR.................. 22 1........................... 24 iv

1. 1

web CR CR 2

CR CR CR CR CR CR 3

USB CR [4] [6] CR CR CR CR 3 on-the-fly 4

ID [2] CR 5

2. CR 2.1 CR 6

1 2 3 4 7

CR 5 2.2 1 8

web web CR 9

CR 6 7 CR 10

3. CR 3.1 CR CR CR Kerberos [4] CR h() k E k(), D k() pk, sk E pk (), D sk () ACK 3.2 4 k k k 11

nonce n 1 m 1 = E k(n 1 ) x D k(m 1 ) nonce n 2 m 2 = E k(x, n 2 ) (y 1, y 2 ) D k(m 2 ) y 1 = n 1 m 3 = y 2 m 3 = n 2 CR CR CR 1 2 CR 3 4 p k C k M C M M M k k p 12

M 5 CR CR UNIX CR 6 7 3.2 CR CR CR CR SSH [6] SSH 13

pk s pk u sk u pk s, sk u nonce nonce pk u sk u pk s pk s SSH CR CR 1 RSA [5] n p, q (n, e) e (p 1)(q 1) 1 2 SSH 14

3 4 5 sk u pk u sk u 6 1 1 7 15

4. CR CR CR ElGamal [3] ID ID CR KG 4.1 KG CR CR on-the-fly 3.2, 4.2 ID CR 2 4.3 16

4.1 on-the-fly CR on-the-fly KG KG KG 3.2 3.2 p ((pk 1, sk 1 ), (pk 2, sk 2 )) = KG(h(p)) ((pk 1, sk 1 ), (pk 2, sk 2 )) pk 1 sk 2 pk 1 nonce n 1 m 1 = E pk1 (n 1 ) p ((pk 1, sk 1 ), (pk 2, sk 2 )) = KG(h(p)) n 1 D sk1 (m 1 ) n 1 nonce n 2 m 2 = E pk2 (n 2, E n 1 n 2 (ACK 1 )) (x 1, x 2 ) D sk2 (m 2 ) x 2 E n 1 x 1 (ACK 1 ) m 3 = E n 1 x 1 (ACK 2 ) m 3 E n1 n2 (ACK 2) 17

n 1 D sk1 (m 1 ) m 2 = E pk2 (n 2, E n 1 n 2 (ACK 1 ))? m 3 = E n1 n2 (ACK 2) m 1 m 1 = E pk1 (n 1 ) m 2 (x 1, x 2 ) D sk2 (m 2 )? x 2 = E n 1 x 1 (ACK 1 ) m 3 m 3 = E n 1 x 1 (ACK 2 ) 1 on-the-fly CR 1 p 1 p 2 3.2 3 4 KG p ((pk 1, sk 1), (pk 2, sk 2)) KG(h(p )) sk 1, sk 2 m 1, m 2 n 1 D sk 1 (m 1 ), (n 2, x ) D sk 2 (m 2 ) x E n 1 n 2(ACK 1 ) 5 (pk 1, sk 2 ) p pk 1 sk 1 6 18

p (pk 1, sk 1 ), (pk 2, sk 2 ) pk 1 sk 2 7 4.2 CR 3.2 1 2 KG KG p (pk, sk) = KG(h(p)) pk pk nonce n 1, n 2 pk m 1 = E pk (n 1, n 2 ) p 19

(x 1, x 2 ) D sk (m 1 ) m 2 = E x 2 (x 1, n 3 )? m 3 = E n 3 (ACK) m 1 m 1 = E pk (n 1, n 2 ) m 2 (y 1, y 2 ) D n 2 (m 2 )? y 1 = n 1 m 3 m 3 = E y 2 (ACK) 2 CR (pk, sk) = KG(h(p)) (x 1, x 2 ) D sk (m 1 ) nonce n 3 m 2 = E x 2 (x 1, n 3 ) (y 1, y 2 ) D n 2 (m 2 ) y 1 = n 1 m 3 = E y 2 (ACK) m 3 E n 3 (ACK) 2 1 2 3 4, p p p 5 pk sk 6 20

p pk pk 7 4.3 ID CR CR CR ID [2] ID ID CR ID x (ID) sk x p u u p u p sk u p 21

m 1 = E u p (n 1, n 2 ) (y 1, y 2 ) D n 2 (m 2 )? y 1 = n 1 m 3 = E y 2 (ACK) m 1 (x 1, x 2 ) D sku p (m 1 ) m 2 m 2 = E x 2 (x 1, n 3 ) m 3? m 3 = E n 3 (ACK) 3 ID CR nonce n 1, n 2 u p m 1 = E u p (n 1, n 2 ) (x 1, x 2 ) D sku p (m 1 ) m 2 = E x 2 (x 1, n 3 ) (y 1, y 2 ) D x 2 (m 2 ) y 1 = n 1 m 3 = E y 2 (ACK) m 3 E n 3 (ACK) 3. u p 1 2 2 CR 3 22

4 p p p p 5 u p sk u p p sk u p 6 u u p sk u p, sk u p sk u p, sk u p 7 CR 23

1 1 2 3 4 5 1 2 3 4 5 6 7 1 : 2 : 3 : 4 : 5 : 6 : 7 : 1 : CR 2 : CR 3 : on-the-fly CR 4 : CR 5 : ID CR 24

5. CR 2 CR CR 4 CR 4.3 ID 2 25

26

[1] S.T. Bellovin and M. Meritt, Encrypted key exchange: Passwordbased protocols secure against dictionary attacks and password file compromise, 1st ACM Conference on Computer and Communications Security, pp.244-250, 1993. [2] D. Boneh, Identity-Based Encryption from the Weil Pairing, CRYPTO 01, pp.213-229, 2001. [3] E. ElGmal, A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, CRYPTO 84, pp.10-18, 1985. [4] J.T. Kohl, B.C. Neuman and T.Y. Ts o, The Evolution of the Kerberos Authentication Service, EurOpen Conference Proceedings, pp.295-313, 1991. [5] R.L. Rivest, A. Shamir and L.M. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, 21, 2, pp.120-126, 1978 [6] T. Ylonen and C. Lonvick, The Secure Shell (SSH) Authentication Protocol, RFC 4252, 2006. [7],,, 2010 SCIS 2010, 1E2-3, 2010. 27