( )

Size: px

Start display at page:

Download "( )"

しおりはかまや
5 years ago
Views:

1 NAIST-IS-MT

2 ( )

3 CR CR CR CR Kerberos SSH CR CR CR CR CR CR,,, ID, NAIST-IS- MT , i

4 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-MT , February 4, ii

5 CR CR CR CR on-the-fly CR CR ID CR iii

6 1 on-the-fly CR CR ID CR iv

7 1. 1

8 web CR CR 2

9 CR CR CR CR CR CR 3

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

11 ID [2] CR 5

12 2. CR 2.1 CR 6

14 CR

15 web web CR 9

16 CR 6 7 CR 10

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

18 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

19 M 5 CR CR UNIX CR CR CR CR CR SSH [6] SSH 13

20 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

21 3 4 5 sk u pk u sk u

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

23 4.1 on-the-fly CR on-the-fly KG KG KG 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

24 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 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

25 p (pk 1, sk 1 ), (pk 2, sk 2 ) pk 1 sk CR 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

26 (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) , p p p 5 pk sk 6 20

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

28 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 CR 3 22

29 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

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

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

32 26

33 [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 , [2] D. Boneh, Identity-Based Encryption from the Weil Pairing, CRYPTO 01, pp , [3] E. ElGmal, A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, CRYPTO 84, pp.10-18, [4] J.T. Kohl, B.C. Neuman and T.Y. Ts o, The Evolution of the Kerberos Authentication Service, EurOpen Conference Proceedings, pp , [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 , 1978 [6] T. Ylonen and C. Lonvick, The Secure Shell (SSH) Authentication Protocol, RFC 4252, [7],,, 2010 SCIS 2010, 1E2-3,

21 Key Exchange method for portable terminal with direct input by user

21 Key Exchange method for portable terminal with direct input by user 1110251 2011 3 17 Diffie-Hellman,..,,,,.,, 2.,.,..,,.,, Diffie-Hellman, i Abstract Key Exchange method for portable terminal with