idnits 2.17.1 draft-shin-tls-augpake-08.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 17, 2017) is 2628 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'ChangeCipherSpec' is mentioned on line 616, but not defined == Missing Reference: 'P' is mentioned on line 844, but not defined -- Possible downref: Non-RFC (?) normative reference: ref. 'FIPS180-3' ** Obsolete normative reference: RFC 3454 (Obsoleted by RFC 7564) ** Obsolete normative reference: RFC 4013 (Obsoleted by RFC 7613) ** Obsolete normative reference: RFC 4282 (Obsoleted by RFC 7542) ** Obsolete normative reference: RFC 5246 (Obsoleted by RFC 8446) -- Possible downref: Non-RFC (?) normative reference: ref. 'SP800-108' Summary: 4 errors (**), 0 flaws (~~), 3 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S.H. Shin 3 Internet-Draft K. Kobara 4 Intended status: Standards Track AIST 5 Expires: July 21, 2017 January 17, 2017 7 Augmented Password-Authenticated Key Exchange for Transport Layer 8 Security (TLS) 9 draft-shin-tls-augpake-08 11 Abstract 13 This document describes an efficient augmented password-authenticated 14 key exchange (AugPAKE) protocol where a user remembers a low-entropy 15 password and its verifier is registered in the intended server. In 16 general, the user password is chosen from a small set of dictionary 17 whose space is within the off-line dictionary attacks. The AugPAKE 18 protocol described here is secure against passive attacks, active 19 attacks and off-line dictionary attacks (on the obtained messages 20 with passive/active attacks), and also provides resistance to server 21 compromise (in the context of augmented PAKE security). Based on the 22 AugPAKE protocol, this document also specifies a new password-only 23 authentication handshake for Transport Layer Security (TLS) protocol. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at http://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on July 21, 2017. 42 Copyright Notice 44 Copyright (c) 2017 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (http://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 60 1.1. Keywords . . . . . . . . . . . . . . . . . . . . . . . . 4 61 2. AugPAKE Specification . . . . . . . . . . . . . . . . . . . . 4 62 2.1. Underlying Group . . . . . . . . . . . . . . . . . . . . 4 63 2.2. Notation . . . . . . . . . . . . . . . . . . . . . . . . 5 64 2.2.1. Password Processing . . . . . . . . . . . . . . . . . 6 65 2.3. Protocol . . . . . . . . . . . . . . . . . . . . . . . . 6 66 2.3.1. Initialization . . . . . . . . . . . . . . . . . . . 7 67 2.3.2. Actual Protocol Execution . . . . . . . . . . . . . . 7 68 3. Security Considerations . . . . . . . . . . . . . . . . . . . 9 69 3.1. General Assumptions . . . . . . . . . . . . . . . . . . . 9 70 3.2. Security against Passive Attacks . . . . . . . . . . . . 9 71 3.3. Security against Active Attacks . . . . . . . . . . . . . 10 72 3.3.1. Impersonation Attacks on User U . . . . . . . . . . . 10 73 3.3.2. Impersonation Attacks on Server S . . . . . . . . . . 10 74 3.3.3. Man-in-the-Middle Attacks . . . . . . . . . . . . . . 11 75 3.4. Security against Off-line Dictionary Attacks . . . . . . 11 76 3.5. Resistance to Server Compromise . . . . . . . . . . . . . 12 77 3.6. User Privacy . . . . . . . . . . . . . . . . . . . . . . 13 78 4. Implementation Consideration . . . . . . . . . . . . . . . . 13 79 5. AugPAKE for TLS . . . . . . . . . . . . . . . . . . . . . . . 13 80 5.1. Specification of AugPAKE Handshake . . . . . . . . . . . 13 81 5.2. Changes from the TLS Handshake Protocol . . . . . . . . . 14 82 5.2.1. Changes to Client Hello Message . . . . . . . . . . . 14 83 5.2.2. Changes to Server Key Exchange Message . . . . . . . 15 84 6. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . 15 85 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 86 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 87 8.1. Normative References . . . . . . . . . . . . . . . . . . 15 88 8.2. Informative References . . . . . . . . . . . . . . . . . 16 89 Appendix A. Features of AugPAKE . . . . . . . . . . . . . . . . 17 90 Appendix B. Test Vector of AugPAKE . . . . . . . . . . . . . . . 18 91 Appendix C. AugPAKE over EC Groups . . . . . . . . . . . . . . . 20 92 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 94 1. Introduction 95 In the real world, many applications such as web mail, Internet 96 banking/shopping/trade require secure channels between participating 97 parties. Such secure channels can be established by using an 98 authenticated key exchange (AKE) protocol, which allows the involving 99 parties to authenticate each other and to generate a temporary 100 session key. The temporary session key is used to protect the 101 subsequent communications between the parties. 103 Until now, password-only AKE (called, PAKE) protocols have attracted 104 much attention because password-only authentication is very 105 convenient to the users. However, it is not trivial to design a 106 secure PAKE protocol due to the existence of off-line dictionary 107 attacks on passwords. These attacks are possible since passwords are 108 chosen from a relatively-small dictionary that allows for an attacker 109 to perform the exhaustive searches. This problem was brought forth 110 by Bellovin and Merritt [BM92], and many following works have been 111 conducted in the literature (see some examples in [IEEEP1363.2]). A 112 PAKE protocol is said to be secure if the best attack an active 113 attacker can take is restricted to the on-line dictionary attacks, 114 which allow to check a guessed password only by interacting with the 115 honest party. 117 An augmented PAKE protocol (e.g., [BM93], [RFC2945], [ISO]) provides 118 extra protection for server compromise in the sense that an attacker, 119 who obtained a password verifier from a server, cannot impersonate 120 the corresponding user without performing off-line dictionary attacks 121 on the password verifier. This additional security is known as 122 "resistance to server compromise". The AugPAKE protocol described in 123 this document is an augmented PAKE which also achieves measurable 124 efficiency over some previous works (SRP [RFC2945] and AMP [ISO]). 125 We believe the following (see [SKI10] for the formal security proof): 126 1) The AugPAKE protocol is secure against passive attacks, active 127 attacks and off-line dictionary attacks (on the obtained messages 128 with passive/active attacks), and 2) It provides resistance to server 129 compromise. At the same time, the AugPAKE protocol has similar 130 computational efficiency to the plain Diffie-Hellman key exchange 131 [DH76] that does not provide authentication by itself. Specifically, 132 the user and the server need to compute 2 and 2.17 modular 133 exponentiations, respectively, in the AugPAKE protocol. After 134 excluding pre-computable costs, the user and the server are required 135 to compute only 1 and 1.17 modular exponentiations, respectively. 136 Compared with SRP [RFC2945] and AMP [ISO], the AugPAKE protocol is 137 more efficient 1) than SRP in terms of the user's computational costs 138 and 2) than AMP in terms of the server's computational costs. 140 Based on the AugPAKE protocol, this document also specifies a new 141 password-only authentication handshake for Transport Layer Security 142 (TLS) protocol [RFC5246]. 144 1.1. Keywords 146 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 147 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 148 document are to be interpreted as described in RFC 2119 [RFC2119]. 150 2. AugPAKE Specification 152 2.1. Underlying Group 154 The AugPAKE protocol can be implemented over the following group. 156 o Let p and q be sufficiently large primes such that q is a divisor 157 of ((p - 1) / 2) and every factors of ((p - 1) / 2) are also 158 primes comparable to q in size. This p is called a "secure" 159 prime. We denote by G a multiplicative subgroup of prime order q 160 over the field GF(p), the integers modulo p. Let g be a generator 161 for the subgroup G so that all the subgroup elements are generated 162 by g. The group operation is denoted multiplicatively (in modulo 163 p). 165 By using a secure prime p, the AugPAKE protocol has computational 166 efficiency gains. Specifically, it does not require the order check 167 of elements, received from the counterpart party. Note that the 168 groups, defined in Discrete Logarithm Cryptography [SP800-56A] and 169 RFC 5114 [RFC5114], are not necessarily the above secure prime 170 groups. 172 Alternatively, one can implement the AugPAKE protocol over the 173 following groups. 175 o Let p and q be sufficiently large primes such that p = (2 * q) + 176 1. This p is called a "safe" prime. We denote by G a 177 multiplicative subgroup of prime order q over the field GF(p), the 178 integers modulo p. Let g be any element of G other than 1. For 179 example, g = h^2 mod p where h is a primitive element. The group 180 operation is denoted multiplicatively (in modulo p). 182 o Let p and q be sufficiently large primes such that q is a divisor 183 of ((p - 1) / 2). We denote by G a multiplicative subgroup of 184 prime order q over the field GF(p), the integers modulo p. Let g 185 be a generator for the subgroup G so that all the subgroup 186 elements are generated by g. The group operation is denoted 187 multiplicatively (in modulo p). If p is not a "secure" prime, the 188 AugPAKE protocol MUST perform the order check of received 189 elements. 191 2.2. Notation 193 The AugPAKE protocol is a two-party protocol where a user and a 194 server authenticate each other and generate a session key. The 195 following notation is used in this document: 197 U 198 The user's identity (e.g., defined in [RFC4282]). It is a string 199 in {0,1}^* where {0,1}^* indicates a set of finite binary 200 strings. 202 S 203 The server's identity. It is a string in {0,1}^*. 205 b = H(a) 206 A binary string a is given as input to a secure one-way hash 207 function H (e.g., SHA-2 family [FIPS180-3]) which produces a 208 fixed-length output b. The hash function H maps {0,1}^* to 209 {0,1}^k where {0,1}^k indicates a set of binary strings of length 210 k and k is a security parameter. 212 b = H'(a) 213 A binary string a is given as input to a secure one-way hash 214 function H' which maps the input a in {0,1}^* to the output b in 215 Z_q^* where Z_q^* is a set of positive integers modulo prime q. 217 a | b 218 It denotes a concatenation of binary strings a and b in {0,1}^*. 220 0x 221 A hexadecimal value is shown preceded by "0x". 223 X * Y mod p 224 It indicates a multiplication of X and Y modulo prime p. 226 X = g^x mod p 227 The g^x indicates a multiplication computation of g by x times. 228 The resultant value modulo prime p is assigned to X. The 229 discrete logarithm problem says that it is computationally hard 230 to compute the discrete logarithm x from X, g and p. 232 w 233 The password remembered by the user. This password may be used 234 as an effective password (instead of itself) in the form of 235 H'(0x00 | U | S | w). 237 W 238 The password verifier registered in the server. This password 239 verifier is computed as follows: W = g^w mod p where the user's 240 password w is used itself, or W = g^w' mod p where the effective 241 password w' = H'(0x00 | U | S | w) is used. 243 bn2bin(X) 244 It indicates a conversion of a multiple precision integer X to 245 the corresponding binary string. If X is an element over GF(p), 246 its binary representation MUST have the same bit length as the 247 binary representation of prime p. 249 U -> S: msg 250 It indicates a message transmission that the user U sends a 251 message msg to the server S. 253 U: 254 It indicates a local computation of user U (without any out-going 255 messages). 257 2.2.1. Password Processing 259 The input password MUST be processed according to the rules of the 260 [RFC4013] profile of [RFC3454]. The password SHALL be considered a 261 "stored string" per [RFC3454] and unassigned code points are 262 therefore prohibited. The output SHALL be the binary representation 263 of the processed UTF-8 character string. Prohibited output and 264 unassigned code points encountered in SASLprep pre-processing SHALL 265 cause a failure of pre-processing and the output SHALL NOT be used 266 with the AugPAKE protocol. 268 The following table shows examples of how various character data is 269 transformed by the rules of the [RFC4013] profile. 271 # Input Output Comments 272 - ----- ------ -------- 273 1 IX IX SOFT HYPHEN mapped to nothing 274 2 user user no transformation 275 3 USER USER case preserved, will not match #2 276 4 a output is NFKC, input in ISO 8859-1 277 5 IX output is NFKC, will match #1 278 6 Error - prohibited character 279 7 Error - bidirectional check 281 2.3. Protocol 283 The AugPAKE protocol consists of two phases: initialization and 284 actual protocol execution. The initialization phase SHOULD be 285 finished in a secure manner between the user and the server, and it 286 is performed all at once. Whenever the user and the server need to 287 establish a secure channel, they can run the actual protocol 288 execution through an open network (i.e., the Internet) in which an 289 active attacker exists. 291 2.3.1. Initialization 293 U -> S: (U, W) 294 The user U computes W = g^w mod p (instead of w, the 295 effective password w' may be used), and transmits W to the 296 server S. The W is registered in the server as the password 297 verifier of user U. Of course, user U just remembers the 298 password w only. 300 If resistance to server compromise is not necessary, the server can 301 store w' instead of W. In either case, server S SHOULD NOT store any 302 plaintext passwords. 304 As noted above, this phase SHOULD be performed securely and all at 305 once. 307 2.3.2. Actual Protocol Execution 309 The actual protocol execution of the AugPAKE protocol allows the user 310 and the server to share an authenticated session key through an open 311 network (see Figure 1). 313 +-----------------+ +------------------+ 314 | User U | | Server S (U,W) | 315 | | (U, X) | | 316 | |----------------------------->| | 317 | | | | 318 | | (S, Y) | | 319 | |<-----------------------------| | 320 | | | | 321 | | V_U | | 322 | |----------------------------->| | 323 | | | | 324 | | V_S | | 325 | |<-----------------------------| | 326 | | | | 327 +-----------------+ +------------------+ 329 Figure 1: Actual Protocol Execution of AugPAKE 331 U -> S: (U, X) 332 The user U chooses a random element x from Z_q^* and computes 333 its Diffie-Hellman public value X = g^x mod p. The user 334 sends the first message (U, X) to the server S. 336 S -> U: (S, Y) 337 If the received X from user U is 0, 1 or -1 (mod p), server S 338 MUST terminate the protocol execution. Otherwise, the server 339 chooses a random element y from Z_q^* and computes Y = (X * 340 (W^r))^y mod p where r = H'(0x01 | U | S | bn2bin(X)). Note 341 that X^y * g^(w * r * y) mod p can be computed from y and (w 342 * r * y) efficiently using Shamir's trick [MOV97]. Then, 343 server S sends the second message (S, Y) to the user U. 345 U -> S: V_U 346 If the received Y from server S is 0, 1 or -1 (mod p), user U 347 MUST terminate the protocol execution. Otherwise, the user 348 computes K = Y^z mod p where z = 1 / (x + (w * r)) mod q and 349 r = H'(0x01 | U | S | bn2bin(X)). Also, user U generates an 350 authenticator V_U = H(0x02 | U | S | bn2bin(X) | bn2bin(Y) | 351 bn2bin(K)). Then, the user sends the third message V_U to 352 the server S. 354 S -> U: V_S 355 If the received V_U from user U is not equal to H(0x02 | U | 356 S | bn2bin(X) | bn2bin(Y) | bn2bin(K)) where K = g^y mod p, 357 server S MUST terminate the protocol execution. Otherwise, 358 the server generates an authenticator V_S = H(0x03 | U | S | 359 bn2bin(X) | bn2bin(Y) | bn2bin(K)) and a session key SK = 360 H(0x04 | U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)). Then, 361 server S sends the fourth message V_S to the user U. 363 U: 364 If the received V_S from server S is not equal to H(0x03 | U 365 | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)), user U MUST 366 terminate the protocol execution. Otherwise, the user 367 generates a session key SK = H(0x04 | U | S | bn2bin(X) | 368 bn2bin(Y) | bn2bin(K)). 370 In the actual protocol execution, the sequential order of message 371 exchanges is very important in order to avoid any possible attacks. 372 For example, if the server S sends the second message (S, Y) and the 373 fourth message V_S together, any attacker can easily derive the 374 correct password w with off-line dictionary attacks. 376 The session key SK, shared only if the user and the server 377 authenticate each other successfully, MAY be generated by using a key 378 derivation function (KDF) [SP800-108]. After generating SK, the user 379 and the server MUST delete all the internal states (e.g., Diffie- 380 Hellman exponents x and y) from memory. 382 For the formal proof [SKI10] of the AugPAKE protocol, we need to 383 change slightly the computation of Y (in the above S -> U: (S, Y)) 384 and K (in the above S -> U: V_S) as follows: Y = (X * (W^r))^y' and K 385 = g^y' where y' = H'(0x05 | bn2bin(y)). 387 3. Security Considerations 389 This section shows why the AugPAKE protocol (i.e., the actual 390 protocol execution) is secure against passive attacks, active attacks 391 and off-line dictionary attacks, and also provides resistance to 392 server compromise. 394 3.1. General Assumptions 396 o An attacker is computationally-bounded. 398 o Any hash functions, used in the AugPAKE protocol, are secure in 399 terms of pre-image resistance (one-wayness), second pre-image 400 resistance and collision resistance. 402 3.2. Security against Passive Attacks 404 An augmented PAKE protocol is said to be secure against passive 405 attacks in the sense that an attacker, who eavesdrops the exchanged 406 messages, cannot compute an authenticated session key (shared between 407 the honest parties in the protocol). 409 In the AugPAKE protocol, an attacker can get the messages (U, X), (S, 410 Y), V_U, V_S by eavesdropping, and then wants to compute the session 411 key SK. That is, the attacker's goal is to derive the correct K from 412 the obtained messages X and Y because the hash functions are secure 413 and the only secret in the computation of SK is K = g^y mod p. Note 414 that 416 X = g^x mod p and 418 Y = (X * (W^r))^y = X^y * W^(r * y) = X^y * (g^y)^t = X^y * K^t 420 hold where t = w * r mod q. Though t is determined from possible 421 password candidates and X, the only way for the attacker to extract K 422 from X and Y is to compute X^y. However, the probability for the 423 attacker to compute X^y is negligible in the security parameter for 424 the underlying groups since both x and y are random elements chosen 425 from Z_q^*. Therefore, the AugPAKE protocol is secure against passive 426 attacks. 428 3.3. Security against Active Attacks 430 An augmented PAKE protocol is said to be secure against active 431 attacks in the sense that an attacker, who completely controls the 432 exchanged messages, cannot compute an authenticated session key 433 (shared with the honest party in the protocol) with the probability 434 better than that of on-line dictionary attacks. In other words, the 435 probability for an active attacker to compute the session key is 436 restricted by the on-line dictioinary attacks where it grows linearly 437 to the number of interactions with the honest party. 439 In the AugPAKE protocol, the user (resp., the server) computes the 440 session key SK only if the received authenticator V_S (resp., V_U) is 441 valid. There are three cases to be considered in the active attacks. 443 3.3.1. Impersonation Attacks on User U 445 When an attacker impersonates the user U, the attacker can compute 446 the same SK (to be shared with the server S) only if the 447 authenticator V_U is valid. For a valid authenticator V_U, the 448 attacker has to compute the correct K from X and Y because the hash 449 functions are secure. In this impersonation attack, the attacker of 450 course knows the discrete logarithm x of X and guesses a password w'' 451 from the password dictionary. So, the probability for the attacker 452 to compute the correct K is bounded by the probability of w = w''. 453 That is, this impersonation attack is restricted by the on-line 454 dictionary attacks where the attacker can try a guessed password 455 communicating with the honest server S. Therefore, the AugPAKE 456 protocol is secure against impersonation attacks on user U. 458 3.3.2. Impersonation Attacks on Server S 460 When an attacker impersonates the server S, the attacker can compute 461 the same SK (to be shared with the user U) only if the authenticator 462 V_S is valid. For a valid authenticator V_S, the attacker has to 463 compute the correct K from X and Y because the hash functions are 464 secure. In this impersonation attack, the attacker chooses a random 465 element y and guesses a password w'' from the password dictionary so 466 that 468 Y = (X * (W'^r))^y = X^y * W'^(r * y) = X^y * (g^y)^t' 470 where t' = w'' * r mod q. The probability for the attacker to 471 compute the correct K is bounded by the probability of w = w''. 473 Also, the attacker knows whether the guessed password is equal to w 474 or not by seeing the received authenticator V_U. However, when w is 475 not equal to w'', the probability for the attacker to compute the 476 correct K is negligible in the security parameter for the underlying 477 groups since the attacker has to guess the discrete logarithm x 478 (chosen by user U) as well. That is, this impersonation attack is 479 restricted by the on-line dictionary attacks where the attacker can 480 try a guessed password communicating with the honest user U. 481 Therefore, the AugPAKE protocol is secure against impersonation 482 attacks on server S. 484 3.3.3. Man-in-the-Middle Attacks 486 When an attacker performs the man-in-the-middle attack, the attacker 487 can compute the same SK (to be shared with the user U or the server 488 S) only if one of the authenticators V_U, V_S is valid. Note that if 489 the attacker relays the exchanged messages honestly, it corresponds 490 to the passive attacks. In order to generate a valid authenticator 491 V_U or V_S, the attacker has to compute the correct K from X and Y 492 because the hash functions are secure. So, the attacker is in the 493 same situation as discussed above. Though the attacker can test two 494 passwords (one with user U and the other with server S), it does not 495 change the fact that this attack is restricted by the on-line 496 dictionary attacks where the attacker can try a guessed password 497 communicating with the honest party. Therefore, the AugPAKE protocol 498 is also secure against man-in-the-middle attacks. 500 3.4. Security against Off-line Dictionary Attacks 502 An augmented PAKE protocol is said to be secure against off-line 503 dictionary attacks in the sense that an attacker, who completely 504 controls the exchanged messages, cannot reduce the possible password 505 candidates better than on-line dictionary attacks. Note that, in the 506 on-line dictionary attacks, an attacker can test one guessed password 507 by running the protocol execution (i.e., communicating with the 508 honest party). 510 As discussed in Section 3.2, an attacker in the passive attacks does 511 not compute X^y (and the correct K = g^y mod p) from the obtained 512 messages X, Y. This security analysis also indicates that, even if 513 the attacker can guess a password, the K is derived independently 514 from the guessed password. Next, we consider an active attacker 515 whose main goal is to perform the off-line dictionary attacks in the 516 AugPAKE protocol. As in Section 3.3, the attacker can 1) test one 517 guessed password by impersonating the user U or the server S, or 2) 518 test two guessed passwords by impersonating the server S (to the 519 honest user U) and impersonating the user U (to the honest server S) 520 in the man-in-the-middle attacks. Whenever the honest party receives 521 an invalid authenticator, the party terminates the actual protocol 522 execution without sending any message. In fact, this is important to 523 prevent an attacker from testing more than one password in the active 524 attacks. Since passive attacks and active attacks cannot remove the 525 possible password candidates efficiently than on-line dictionary 526 attacks, the AugPAKE protocol is secure against off-line dictionary 527 attacks. 529 3.5. Resistance to Server Compromise 531 We consider an attacker who has obtained a (user's) password verifier 532 from a server. In the (augmented) PAKE protocols, there are two 533 limitations [BJKMRSW00]: 1) the attacker can find out the correct 534 password from the password verifier with the off-line dictionary 535 attacks because the verifier has the same entropy as the password; 536 and 2) if the attacker impersonates the server with the password 537 verifier, this attack is always possible because the attacker has 538 enough information to simulate the server. An augmented PAKE 539 protocol is said to provide resistance to server compromise in the 540 sense that the attacker cannot impersonate the user without 541 performing off-line dictionary attacks on the password verifier. 543 In order to show resistance to server compromise in the AugPAKE 544 protocol, we consider an attacker who has obtained the password 545 verifier W and then tries to impersonate the user U without off-line 546 dictionary attacks on W. As a general attack, the attacker chooses 547 two random elements c and d from Z_q^*, and computes 549 X = (g^c) * (W^d) mod p 551 and sends the first message (U, X) to the server S. In order to 552 impersonate user U successfully, the attacker has to compute the 553 correct K = g^y mod p where y is randomly chosen by server S. After 554 receiving Y from the server, the attacker's goal is to find out a 555 value e satisfying Y^e = K mod p. That is, 557 log_g (Y^e) = log_g K mod q 559 (c + (w * d) + (w * r)) * y * e = y mod q 561 (c + w * (d + r)) * e = 1 mod q 563 where log_g K indicates the logarithm of K to the base g. Since 564 there is no off-line dictionary attacks on W, the above solution is 565 that e = 1 / c mod q and d = -r mod q. However, the latter is not 566 possible since r is determined by X (i.e., r = H'(0x01 | U | S | 567 bn2bin(X))) and H' is a secure hash function. Therefore, the AugPAKE 568 protocol provides resistance to server compromise. 570 3.6. User Privacy 572 In the AugPAKE protocol, the user's identity U is sent to the server 573 in clear form. One way to provide user privacy is to use DHE for 574 encrypting the user's identity. 576 4. Implementation Consideration 578 As discussed in Section 3, the AugPAKE protocol is secure against 579 passive attacks, active attacks and off-line dictionary attacks, and 580 provides resistance to server compromise. However, an attacker in 581 the on-line dictionary attacks can check whether one password 582 (guessed from the password dictionary) is correct or not by 583 interacting with the honest party. Let N be a dictionary size of 584 passwords. Certainly, the attacker's success probability grows with 585 the probability of (I / N) where I is the number of interactions with 586 the honest party. In order to provide a reasonable security margin, 587 implementation SHOULD take a countermeasure to the on-line dictionary 588 attacks. For example, it would take about 90 years to test 2^(25.5) 589 passwords with one minute lock-out for 3 failed password guesses (see 590 Appendix A in [SP800-63]). 592 5. AugPAKE for TLS 594 5.1. Specification of AugPAKE Handshake 596 The TLS Handshake Protocol [RFC5246], which operates on top of the 597 TLS record layer, is responsible for negotiating a session and 598 agreeing upon security parameters (e.g., PreMasterSecret) of the 599 session state. When protecting subsequent application data, the 600 agreed security parameters are used by the record layer. The AugPAKE 601 protocol, described in Section 2, can be easily integrated into the 602 TLS Handshake Protocol as a password-only mutual authentication by 603 modifying some messages (see Figure 2). This integrated protocol 604 preserves the TLS Handshake Protocol structure and its security 605 guarantees. 607 Client Server 609 ClientHello: name, X --------> 610 ServerHello 611 ServerKeyExchange: Y 612 <-------- ServerHelloDone 613 ClientKeyExchange 614 [ChangeCipherSpec] 615 Finished: V_U --------> 616 [ChangeCipherSpec] 617 <-------- Finished: V_S 619 Application Data <-------> Application Data 621 Figure 2: Plugging AugPAKE into TLS Handshake Protocol 623 5.2. Changes from the TLS Handshake Protocol 625 The changes from the TLS Handshake Protocol are summarized as 626 follows: 628 o The X and the TLS client name (it is preferable to use a hashed 629 value for privacy protection) are included in the "ClientHello" 630 message. 632 o The Y is included in the "ServerKeyExchange" message. 634 o The V_U (resp., V_S) is inclued in the TLS client's (resp., 635 server's) "Finished" message. 637 o The PreMasterSecret in the TLS Handshake Protocol corresponds to K 638 of the AugPAKE protocol in Section 2. The leading bytes of K that 639 contain all zero bits are stripped before it is used as the 640 pre_master_secret. 642 5.2.1. Changes to Client Hello Message 644 The extension of the "ClientHello" message will be 646 enum { AugPAKE (TBD) } ExtensionType; 648 struct { 650 opaque name<1..2^8-1>; 652 opaque X<1..2^16-1>; 654 } Extension; 656 where the extension data field of the AugPAKE extension SHALL contain 657 a "name" to be used to identify the TLS client and the client's 658 Diffie-Hellman public value X. 660 If the TLS server does not find a verifier corresponding to the 661 "name" in the extension of the "ClientHello" message, the server 662 SHOULD keep running the protocol by choosing a random element Y and 663 then rejects the TLS client's "Finished" message with a 664 bad_record_mac alert. Alternatively, the TLS server MAY terminate 665 the protocol if a verifier corresponding to the "name" in the 666 extension of the "ClientHello" message is not found. 668 5.2.2. Changes to Server Key Exchange Message 670 The "ServerKeyExchange" message contains the server's computed value 671 Y (see Section 2). Also, a new value is added to the 672 KeyExchangeAlgorithm to indicate its use of AugPAKE. 674 enum { augpake } KeyExchangeAlgorithm; 676 struct { opaque Y<1..2^16-1>; } ServerAugPAKEParams; 678 6. Acknowledgement 680 We would sincerely appreciate comments from Fabrice Gautier, Watson 681 Ladd and IIari Liusvaara. The AugPAKE protocol described in 682 Section 2 has also been specified as a password-only authentication 683 method for IKEv2. 685 7. IANA Considerations 687 This document requests IANA to assign a value. 689 IANA SHALL assign a value for "AugPAKE" from the TLS ExtensionType 690 Registry defined in [RFC5246] with the method name of "AugPAKE". 692 8. References 694 8.1. Normative References 696 [FIPS180-3] 697 Information Technology Laboratory, , "Secure Hash Standard 698 (SHS)", NIST FIPS Publication 180-3, October 2008, . 702 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 703 Requirement Levels", BCP 14, RFC 2119, March 1997. 705 [RFC3454] Hoffman, P. and M. Blanchet, "Preparation of 706 Internationalized Strings ("stringprep")", RFC 3454, 707 December 2002. 709 [RFC4013] Zeilenga, K., "SASLprep: Stringprep Profile for User Names 710 and Passwords", RFC 4013, February 2005. 712 [RFC4282] Aboba, B., Beadles, M., Arkko, J., and P. Eronen, "The 713 Network Access Identifier", RFC 4282, December 2005. 715 [RFC5246] Dierks, T., Rescorla, E., , , "The Transport Layer 716 Security (TLS) Protocol Version 1.2", RFC 5246, August 717 2008. 719 [SP800-108] 720 Chen, L., "Recommendation for Key Derivation Using 721 Pseudorandom Functions (Revised)", NIST Special 722 Publication 800-108, October 2009, . 725 8.2. Informative References 727 [BJKMRSW00] 728 Bellare, M., Jablon, D., Krawczyk, H., MacKenzie, P., 729 Rogaway, P., Swaminathan, R., and T. Wu, "Proposal for 730 P1363 Study Group on Password-Based Authenticated-Key- 731 Exchange Methods", IEEE P1363.2: Password-Based Public-Key 732 Cryptography , Submissions to IEEE P1363.2 , February 733 2000, . 736 [BM92] Bellovin, S. M. and M. Merritt, "Encrypted Key Exchange: 737 Password-based Protocols Secure against Dictionary 738 Attacks", Proceedings of the IEEE Symposium on Security 739 and Privacy , IEEE Computer Society , 1992. 741 [BM93] Bellovin, S. M. and M. Merritt, "Augmented Encrypted Key 742 Exchange: A Password-based Protocol Secure against 743 Dictionary Attacks and Password File Compromise", 744 Proceedings of the 1st ACM Conference on Computer and 745 Communication Security , ACM Press , 1993. 747 [DH76] Diffie, W. and M. Hellman, "New Directions in 748 Cryptography", IEEE Transactions on Information Theory 749 Volume IT-22, Number 6, 1976. 751 [IEEEP1363.2] 752 IEEE P1363.2, , "Password-Based Public-Key Cryptography", 753 Submissions to IEEE P1363.2 , , . 756 [ISO] ISO/IEC JTC 1/SC 27 11770-4, , "Information technology -- 757 Security techniques -- Key management -- Part 4: 758 Mechanisms based on weak secrets", May 2006, . 762 [MOV97] Menezes, A. J., Oorschot, P. C., and S. A. Vanstone, 763 "Simultaneous Multiple Exponentiation", in Handbook of 764 Applied Cryptography , CRC Press , 1997. 766 [RFC2945] Wu, T. , "The SRP Authentication and Key Exchange System", 767 RFC 2945, September 2000. 769 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman 770 Groups for Use with IETF Standards", RFC 5114, January 771 2008. 773 [SKI10] Shin, S. H., Kobara, K., and H. Imai, "Security Proof of 774 AugPAKE", Cryptology ePrint Archive: Report 2010/334, June 775 2010, . 777 [SK] Shin, S. H. and K. Kobara, "Augmented Password- 778 Authenticated Key Exchange (AugPAKE)", (work in progress), 779 August 2014, . 782 [SP800-56A] 783 Barker, E., Johnson, D., and M. Smid, "Recommendation for 784 Pair-Wise Key Establishment Schemes Using Discrete 785 Logarithm Cryptography (Revised)", NIST Special 786 Publication 800-56A, March 2007, . 790 [SP800-63] 791 Burr, W. E., Dodson, D. F., and W. T. Polk, "Electronic 792 Authentication Guideline", NIST Special Publication 800-63 793 Version 1.0.2, April 2006, . 796 Appendix A. Features of AugPAKE 798 Below are some features of the AugPAKE protocol. 800 Security: 802 AugPAKE is zero knowledge (password) proof. It is secure against 803 passive/active/off-line dictionary attacks. It is also resistant 804 to server-compromise impersonation attacks. 806 AugPAKE provides Perfect Forward Secrecy (PFS) and is secure 807 against Denning-Sacco attack. 809 Any cryptographically secure Diffie-Hellman groups can be used. 811 The formal security proof of AugPAKE can be found at [SKI10]. 813 AugPAKE can be easily used with strong credentials. 815 In the case of server compromise, an attacker has to perform off- 816 line dictionary attacks while computing modular exponentiation 817 with a password candidate. 819 Intellectual Property: 821 AugPAKE was publicly disclosed on Oct. 2008. 823 AIST applied for a patent in Japan on July 10, 2008. AIST would 824 provide royal-free license of AugPAKE. 826 IPR disclosure (see https://datatracker.ietf.org/ipr/2037/) 828 Miscellaneous: 830 The user needs to compute only 2 modular exponentiation 831 computations while the server needs to compute 2.17 modular 832 exponentiation computations. AugPAKE needs to exchange 2 group 833 elements and 2 hash values. This is almost the same computation/ 834 communication costs as the plain Diffie-Hellman key exchange. If 835 we use a large (e.g., 2048/3072-bits) parent group, the hash size 836 would be relatively small. 838 AugPAKE has the same performance for any type of secret. 840 Internationalization of character-based passwords can be 841 supported. 843 AugPAKE can be implemented over any ECP (Elliptic Curve Group over 844 GF[P]), EC2N (Elliptic Curve Group over GF[2^N]), and MODP 845 (Modular Exponentiation Group) groups. See Appendix 3 of[SK]. 847 AugPAKE has request/response nature. 849 No Trusted Third Party (TTP) and clock synchronization 851 No additional primitive (e.g., Full Domain Hash (FDH) and/or ideal 852 cipher) is needed. 854 Easy implementation. We already implemented AugPAKE and have been 855 testing in AIST. 857 Appendix B. Test Vector of AugPAKE 858 Here is a test vector of the AugPAKE protocol. 860 p = 0x FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 861 43000000000000000000000000000000000000000000000000000000000000 862 00000000000000000000000000000000000000000000000000000000000000 863 00000000000000000000000000000000000000000000000000000000000000 864 00000000000000000000000000000000000000000000000000000000000000 865 00000000000000000000000000000000000000000000000000000000000000 866 00000000000000000000000000000000000000000000000000000000000000 867 00000000000000000000000000000000000000000000000000000000000000 868 00000000000000000000000000000000000000000000000000000000000000 869 00000000000000000000000000000000000000000000000000000000000000 870 00000000000000000000000000000000000000000000000000000000000000 871 0000000000000000330A0DFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 872 FFFFFFFFFFFFFFFFDA5193AB 874 q = 0x FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 875 43 877 g = 0x F1AC99884ABBBBCC9BAA19BF375607FD14570B3019A03871147032445ADA7F 878 A5B8BDC399C1889BBDA197ADB1E3939D55361241F5CD5ED529B0ADD921B274 879 44BD2EB698DC962A9F7D202EAB98BC0C8CC950CA13BC6B1E632D0876A4E796 880 26FDE85F06A46C9991EB02A6D6096E0DF6BCA2CAA12E838BEC47A7CB4AF2B0 881 D94107B9CDBD67327238ECAF84DF292E776AF0F76288B39F9D9E4DDF3A9731 882 CC832D70F150A0F29E7A1E193D1D21CBE8A84B56B0A4692CB39D3048086782 883 85A23F08F9DB402487746F7E2A19CAF2171E55C76337E359217516213FF3BF 884 616F8B20586A8B3168DA444AEA862BB76B9EA2BF8CB84773D29D4EFE511C53 885 95F89CB547EFBBAE333E0BDB22DA40CE0B942A59841A12790910CC1332699D 886 64BBF667E0DF3791C4E29CEB48E8397D50C72F7765C5A18809E3497F6BD374 887 F5D185BBC8F57E36051E11E8DD0C5DD385A9DA442F22598111960CC2B83CBA 888 0A1D980745562F6C62DD6D81B7BAEA7650B1E6E57AB9CC4C95EF17256A79B1 889 31859E1BAC81FF1E 891 U = augpakeuser@aist.go.jp 893 S = augpakeserver@aist.go.jp 895 X = 0x AF261CB6FD99E2E3B4FCDE8A9C538A872EBB54CC82845E8038EA34804DD739 896 90689F2191BF6436BFFD13459DC5FF1FBD56734CA6347ADF52AFAB85EC98A0 897 4D27C122EBAF1840229C2F74E9AEEB79C27ECAF6C8B88FCD5FB3F9C8F20F8F 898 88D45CEBB56D6CAB251DC34D3656DB73E4DF77B71420565D4696DBF8D27023 899 36E909F4C33B2F14605BDEB535423F02B779D7AF0CCB4F3705E177C4334F14 900 707140218197845C708E6ABC025BCA954AA2FDAA352D284DE41D33F7CCFCFD 901 99CAB3CFD34361B6D0551C6D8AEE604316F99758A9C58A96C39AA811E8BA10 902 2E4D21D8F5EFC26920B3F95E6C800D8EBE9914B53144B038BE0E0B43D86479 903 E3CBE623FD148CC90784548C1C7C522C6C71FD4A095B15CBF3EB74C7759493 904 38AC7691A3763C0A3AB97E9E2B439192C49470BF90F292C4A8D336D86780FD 905 DC7DC3C2CC04A6E3AB632788D97D4FDDEE5B117DCF76D91CEA1794FAD91CA1 906 7C9715D83589A00CBB72DD513F6A30E4DB31ACA8DA5D6ECD0E20307D70D6DD 907 0C2D6D3D7962694B5E1B0848 909 Y = 0x 39033C00E1C30FF1A945DD699C516D3BB194FABBB46ADF54A2ED0820FEE0A4 910 DE52128E2126A4393E3040E07D90432B8C19433EC920274E5A7C165DC89AA2 911 C6D77E801A0C7676BC71955A52E74775C57C63B97304C73211C2035BD7B6D1 912 8844A28AC50DD2DA96B257236A6090CCB08D2006BF57AC69EA14ABC5D71BA0 913 6A6BD4093A2EF27C74D5D9189BB2EC865E6321D0DFECDE2D9AC537E8254E98 914 C38AE00BE2554F71FE6EFBBDBE8D7038128957E98C99206998B0B4E578EC47 915 957205C228FAC57B9A1589B8FF2B134980504F56B8A84809B8FF70EFF67520 916 2B255F0724DC0F76F3802D8A42ACC33D349A7FAF249BFBFEB324C3966D2B30 917 6093C32A928A8BEB99AC301D20372E95BB8A3E500778B4651EB8A19B162666 918 8DDFB77D0DF4C1932F1FE63389F3B1F29AE99F34BC39EF0AD04BC3A6A129DE 919 E66E50B6768EDECC529F06FE5F7AD3825E8ECFCB12DB579C40F19D12BF6F60 920 4621F60413DAEB77FE48C136518C57D02A2C6BB596EDFA0DACC127C2FD5FE1 921 9B72580A722307C3F86C0EB1 923 V_U = 0x 490C7CE33DCC3EBE8D0406EEB97CA154882DCBBA0A728F3B870263BCA36 924 9DB6 926 V_S = 0x D70D2CAA821B9D84E29D75EB5E9B2DB038BA1256ECFC35C553832743A6E 927 36F 929 Appendix C. AugPAKE over EC Groups 931 The AugPAKE protocol can be implemented over any elliptic curve 932 groups. The following is such an example. 934 Let p and q be sufficiently large primes, and let m be some positive 935 integer. An elliptic curve E is defined by one of the following two 936 curve equations 938 y^2 = x^3 + a * x + b over the prime field GF(p) or 940 y^2 + x * y = x^3 + a * x^2 + b over the binary field GF(2^m) 942 together with the point at infinity 0_E where x, y, and two 943 coefficients a and b are elements of GF(p) or GF(2^m). Let #E be the 944 number of points on E, and prime q be the order of the desired group. 945 The cofactor k is the value (#E / q) satisfying k = 2^n * q_1 * q_2 946 ... q_t where n = {0,1,2} and every primes q_i > q for i = 1, 2, 947 ..., t. Optionally, k = 2^n. Also, n can be 3 for good performance 948 and security. Let G be a generator for a subgroup of q points on E 949 so that all the subgroup elements are generated by G. The group 950 operation is denoted additively. For example, (X = [x] * G) 951 indicates that an addition computation of G by x times and the 952 resultant value is assigned to X. 954 By using the above elliptic curve groups, the AugPAKE protocol has 955 computational efficiency gains. Specifically, it does not require 956 the order check of elements, received from the counterpart party. 958 The AugPAKE protocol consists of two phases: initialization and 959 actual protocol execution. The initialization phase SHOULD be 960 finished in a secure manner between the user and the server, and it 961 is performed all at once. Whenever the user and the server need to 962 establish a secure channel, they can run the actual protocol 963 execution through an open network (i.e., the Internet) in which an 964 active attacker exists. 966 Initialization 968 U -> S: (U, W) 969 The user U computes W = [w] * G (instead of w, the 970 effective password w' may be used), and transmits W to the 971 server S. The W is registered in the server as the 972 password verifier of user U. Of course, user U just 973 remembers the password w only. 975 Actual Protocol Execution 977 U -> S: (U, X) 978 The user U chooses a random element x from Z_q^* and 979 computes its elliptic curve Diffie-Hellman public value X 980 = [x] * G. The user sends the first message (U, X) to the 981 server S. 983 S -> U: (S, Y) 984 If the received X from user U is not a point on E or [2^n] 985 * X = 0_E, server S MUST terminate the protocol execution. 986 Otherwise, the server chooses a random element y from 987 Z_q^* and computes Y = [y] * (X + ([r] * W)) where r = 988 H'(0x01 | U | S | bn2bin(X)). Then, server S sends the 989 second message (S, Y) to the user U. 991 U -> S: V_U 992 If the received Y from server S is not a point on E or 993 [2^n] * Y = 0_E, user U MUST terminate the protocol 994 execution. Otherwise, the user computes K = [z] * Y where 995 z = 1 / (x + (w * r)) mod q and r = H'(0x01 | U | S | 996 bn2bin(X)). Also, user U generates an authenticator V_U = 997 H(0x02 | U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)). 998 Then, the user sends the third message V_U to the server 999 S. 1001 S -> U: V_S 1002 If the received V_U from user U is not equal to H(0x02 | U 1003 | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)) where K = [y] * 1004 G, server S MUST terminate the protocol execution. 1005 Otherwise, the server generates an authenticator V_S = 1006 H(0x03 | U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)) and a 1007 session key SK = H(0x04 | U | S | bn2bin(X) | bn2bin(Y) | 1008 bn2bin(K)). Then, server S sends the fourth message V_S 1009 to the user U. 1011 U: 1012 If the received V_S from server S is not equal to H(0x03 | 1013 U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)), user U MUST 1014 terminate the protocol execution. Otherwise, the user 1015 generates a session key SK = H(0x04 | U | S | bn2bin(X) | 1016 bn2bin(Y) | bn2bin(K)). 1018 Authors' Addresses 1020 SeongHan Shin 1021 AIST 1022 2-4-7 Aomi, Koto-ku 1023 Tokyo, Tokyo 135-0064 1024 JP 1026 Phone: +81-3-3599-8001 1027 Email: seonghan.shin@aist.go.jp 1029 Kazukuni Kobara 1030 AIST 1032 Email: kobara_conf-ml@aist.go.jp