idnits 2.17.1 draft-shin-tls-augpake-09.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 (July 19, 2017) is 2473 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 615, but not defined == Missing Reference: 'P' is mentioned on line 842, 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: January 20, 2018 July 19, 2017 7 Augmented Password-Authenticated Key Exchange for Transport Layer 8 Security (TLS) 9 draft-shin-tls-augpake-09 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's password is chosen from a small set of 17 dictionary, making the password susceptible to offline dictionary 18 attacks. The AugPAKE protocol described here is secure against 19 passive attacks, active attacks and offline dictionary attacks (on 20 the obtained messages with passive/active attacks), and also provides 21 resistance to server compromise (in the context of augmented PAKE 22 security). Based on the AugPAKE protocol, this document also 23 specifies a new password-only authentication handshake for Transport 24 Layer Security (TLS) protocol. 26 Status of This Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at http://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on January 20, 2018. 43 Copyright Notice 45 Copyright (c) 2017 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (http://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 61 1.1. Keywords . . . . . . . . . . . . . . . . . . . . . . . . 4 62 2. AugPAKE Specification . . . . . . . . . . . . . . . . . . . . 4 63 2.1. Underlying Group . . . . . . . . . . . . . . . . . . . . 4 64 2.2. Notation . . . . . . . . . . . . . . . . . . . . . . . . 5 65 2.2.1. Password Processing . . . . . . . . . . . . . . . . . 6 66 2.3. Protocol . . . . . . . . . . . . . . . . . . . . . . . . 6 67 2.3.1. Initialization . . . . . . . . . . . . . . . . . . . 7 68 2.3.2. Actual Protocol Execution . . . . . . . . . . . . . . 7 69 3. Security Considerations . . . . . . . . . . . . . . . . . . . 9 70 3.1. General Assumptions . . . . . . . . . . . . . . . . . . . 9 71 3.2. Security against Passive Attacks . . . . . . . . . . . . 9 72 3.3. Security against Active Attacks . . . . . . . . . . . . . 10 73 3.3.1. Impersonation Attacks on User U . . . . . . . . . . . 10 74 3.3.2. Impersonation Attacks on Server S . . . . . . . . . . 10 75 3.3.3. Man-in-the-Middle Attacks . . . . . . . . . . . . . . 11 76 3.4. Security against Off-line Dictionary Attacks . . . . . . 11 77 3.5. Resistance to Server Compromise . . . . . . . . . . . . . 12 78 3.6. User Privacy . . . . . . . . . . . . . . . . . . . . . . 12 79 4. Implementation Consideration . . . . . . . . . . . . . . . . 13 80 5. AugPAKE for TLS . . . . . . . . . . . . . . . . . . . . . . . 13 81 5.1. Specification of AugPAKE Handshake . . . . . . . . . . . 13 82 5.2. Changes from the TLS Handshake Protocol . . . . . . . . . 14 83 5.2.1. Changes to Client Hello Message . . . . . . . . . . . 14 84 5.2.2. Changes to Server Key Exchange Message . . . . . . . 15 85 6. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . 15 86 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 87 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 88 8.1. Normative References . . . . . . . . . . . . . . . . . . 15 89 8.2. Informative References . . . . . . . . . . . . . . . . . 16 90 Appendix A. Features of AugPAKE . . . . . . . . . . . . . . . . 17 91 Appendix B. Test Vector of AugPAKE . . . . . . . . . . . . . . . 18 92 Appendix C. AugPAKE over EC Groups . . . . . . . . . . . . . . . 20 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 95 1. Introduction 97 In the real world, many applications such as web mail, Internet 98 banking/shopping/trade require secure channels between participating 99 parties. Such secure channels can be established by using an 100 authenticated key exchange (AKE) protocol, which allows the involving 101 parties to authenticate each other and to generate a temporary 102 session key. The temporary session key is used to protect the 103 subsequent communications between the parties. 105 Until now, password-only AKE (called, PAKE) protocols have attracted 106 much attention because password-only authentication is very 107 convenient to the users. However, it is not trivial to design a 108 secure PAKE protocol due to the existence of offline dictionary 109 attacks on passwords. These attacks are possible since passwords are 110 chosen from a relatively-small dictionary that allows for an attacker 111 to perform the exhaustive searches. This problem was brought forth 112 by Bellovin and Merritt [BM92], and many following works have been 113 conducted in the literature (see some examples in [IEEEP1363.2]). A 114 PAKE protocol is said to be secure if the best attack an active 115 attacker can take is restricted to the on-line dictionary attacks, 116 which allow to check a guessed password only by interacting with the 117 honest party. 119 An augmented PAKE protocol (e.g., [BM93], [RFC2945], [ISO]) provides 120 extra protection for server compromise in the sense that an attacker, 121 who obtained a password verifier from a server, cannot impersonate 122 the corresponding user without performing offline dictionary attacks 123 on the password verifier. This additional security is known as 124 "resistance to server compromise". The AugPAKE protocol described in 125 this document is an augmented PAKE which also achieves measurable 126 efficiency over some previous works (SRP [RFC2945] and AMP [ISO]). 127 We believe the following (see [SKI10] for the formal security proof): 128 1) The AugPAKE protocol is secure against passive attacks, active 129 attacks and offline dictionary attacks (on the obtained messages with 130 passive/active attacks), and 2) It provides resistance to server 131 compromise. At the same time, the AugPAKE protocol has similar 132 computational efficiency to the plain Diffie-Hellman key exchange 133 [DH76] that does not provide authentication by itself. Specifically, 134 the user and the server need to compute 2 and 2.17 modular 135 exponentiations, respectively, in the AugPAKE protocol. After 136 excluding pre-computable costs, the user and the server are required 137 to compute only 1 and 1.17 modular exponentiations, respectively. 138 Compared with SRP [RFC2945] and AMP [ISO], the AugPAKE protocol is 139 more efficient 1) than SRP in terms of the user's computational costs 140 and 2) than AMP in terms of the server's computational costs. 142 Based on the AugPAKE protocol, this document also specifies a new 143 password-only authentication handshake for Transport Layer Security 144 (TLS) protocol [RFC5246]. 146 1.1. Keywords 148 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 149 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 150 document are to be interpreted as described in RFC 2119 [RFC2119]. 152 2. AugPAKE Specification 154 2.1. Underlying Group 156 The AugPAKE protocol can be implemented over the following group. 158 o Let p and q be sufficiently large primes such that q is a divisor 159 of ((p - 1) / 2) and every factors of ((p - 1) / 2) are also 160 primes comparable to q in size. This p is called a "secure" 161 prime. We denote by G a multiplicative subgroup of prime order q 162 over the field GF(p), the integers modulo p. Let g be a generator 163 for the subgroup G so that all the subgroup elements are generated 164 by g. The group operation is denoted multiplicatively (in modulo 165 p). 167 By using a secure prime p, the AugPAKE protocol has computational 168 efficiency gains. Specifically, it does not require the order check 169 of elements, received from the counterpart party. Note that the 170 groups, defined in Discrete Logarithm Cryptography [SP800-56A] and 171 RFC 5114 [RFC5114], are not necessarily the above secure prime 172 groups. 174 Alternatively, one can implement the AugPAKE protocol over the 175 following groups. 177 o Let p and q be sufficiently large primes such that p = (2 * q) + 178 1. This p is called a "safe" prime. We denote by G a 179 multiplicative subgroup of prime order q over the field GF(p), the 180 integers modulo p. Let g be any element of G other than 1. For 181 example, g = h^2 mod p where h is a primitive element. The group 182 operation is denoted multiplicatively (in modulo p). 184 o Let p and q be sufficiently large primes such that q is a divisor 185 of ((p - 1) / 2). We denote by G a multiplicative subgroup of 186 prime order q over the field GF(p), the integers modulo p. Let g 187 be a generator for the subgroup G so that all the subgroup 188 elements are generated by g. The group operation is denoted 189 multiplicatively (in modulo p). If p is not a "secure" prime, the 190 AugPAKE protocol MUST perform the order check of received 191 elements. 193 2.2. Notation 195 The AugPAKE protocol is a two-party protocol where a user and a 196 server authenticate each other and generate a session key. The 197 following notation is used in this document: 199 U 200 The user's identity (e.g., defined in [RFC4282]). It is a string 201 in {0,1}^* where {0,1}^* indicates a set of finite binary 202 strings. 204 S 205 The server's identity. It is a string in {0,1}^*. 207 b = H(a) 208 A binary string a is given as input to a secure one-way hash 209 function H (e.g., SHA-2 family [FIPS180-3]) which produces a 210 fixed-length output b. The hash function H maps {0,1}^* to 211 {0,1}^k where {0,1}^k indicates a set of binary strings of length 212 k and k is a security parameter. 214 b = H'(a) 215 A binary string a is given as input to a secure one-way hash 216 function H' which maps the input a in {0,1}^* to the output b in 217 Z_q^* where Z_q^* is a set of positive integers modulo prime q. 219 a | b 220 It denotes a concatenation of binary strings a and b in {0,1}^*. 222 0x 223 A hexadecimal value is shown preceded by "0x". 225 X * Y mod p 226 It indicates a multiplication of X and Y modulo prime p. 228 X = g^x mod p 229 The g^x indicates a multiplication computation of g by x times. 230 The resultant value modulo prime p is assigned to X. The 231 discrete logarithm problem says that it is computationally hard 232 to compute the discrete logarithm x from X, g and p. 234 w 235 The password remembered by the user. This password may be used 236 as an effective password (instead of itself) in the form of 237 H'(0x00 | U | S | w). 239 W 240 The password verifier registered in the server. This password 241 verifier is computed as follows: W = g^w mod p where the user's 242 password w is used itself, or W = g^w' mod p where the effective 243 password w' = H'(0x00 | U | S | w) is used. 245 bn2bin(X) 246 It indicates a conversion of a multiple precision integer X to 247 the corresponding binary string. If X is an element over GF(p), 248 its binary representation MUST have the same bit length as the 249 binary representation of prime p. 251 U -> S: msg 252 It indicates a message transmission that the user U sends a 253 message msg to the server S. 255 U: 256 It indicates a local computation of user U (without any out-going 257 messages). 259 2.2.1. Password Processing 261 The input password MUST be processed according to the rules of the 262 [RFC4013] profile of [RFC3454]. The password SHALL be considered a 263 "stored string" per [RFC3454] and unassigned code points are 264 therefore prohibited. The output SHALL be the binary representation 265 of the processed UTF-8 character string. Prohibited output and 266 unassigned code points encountered in SASLprep pre-processing SHALL 267 cause a failure of pre-processing and the output SHALL NOT be used 268 with the AugPAKE protocol. 270 The following table shows examples of how various character data is 271 transformed by the rules of the [RFC4013] profile. 273 # Input Output Comments 274 - ----- ------ -------- 275 1 IX IX SOFT HYPHEN mapped to nothing 276 2 user user no transformation 277 3 USER USER case preserved, will not match #2 278 4 a output is NFKC, input in ISO 8859-1 279 5 IX output is NFKC, will match #1 280 6 Error - prohibited character 281 7 Error - bidirectional check 283 2.3. Protocol 284 The AugPAKE protocol consists of two phases: initialization and 285 actual protocol execution. The initialization phase SHOULD be 286 finished in a secure manner between the user and the server, and it 287 is performed all at once. Whenever the user and the server need to 288 establish a secure channel, they can run the actual protocol 289 execution through an open network (i.e., the Internet) in which an 290 active attacker exists. 292 2.3.1. Initialization 294 U -> S: (U, W) 295 The user U computes W = g^w mod p (instead of w, the 296 effective password w' may be used), and transmits W to the 297 server S. The W is registered in the server as the password 298 verifier of user U. Of course, user U just remembers the 299 password w only. 301 If resistance to server compromise is not necessary, the server can 302 store w' instead of W. In either case, server S SHOULD NOT store any 303 plaintext passwords. 305 As noted above, this phase SHOULD be performed securely and all at 306 once. 308 2.3.2. Actual Protocol Execution 310 The actual protocol execution of the AugPAKE protocol allows the user 311 and the server to share an authenticated session key through an open 312 network (see Figure 1). 314 +-----------------+ +------------------+ 315 | User U | | Server S (U,W) | 316 | | (U, X) | | 317 | |----------------------------->| | 318 | | | | 319 | | (S, Y) | | 320 | |<-----------------------------| | 321 | | | | 322 | | V_U | | 323 | |----------------------------->| | 324 | | | | 325 | | V_S | | 326 | |<-----------------------------| | 327 | | | | 328 +-----------------+ +------------------+ 330 Figure 1: Actual Protocol Execution of AugPAKE 332 U -> S: (U, X) 333 The user U chooses a random element x from Z_q^* and computes 334 its Diffie-Hellman public value X = g^x mod p. The user 335 sends the first message (U, X) to the server S. 337 S -> U: (S, Y) 338 If the received X from user U is 0, 1 or -1 (mod p), server S 339 MUST terminate the protocol execution. Otherwise, the server 340 chooses a random element y from Z_q^* and computes Y = (X * 341 (W^r))^y mod p where r = H'(0x01 | U | S | bn2bin(X)). Note 342 that X^y * g^(w * r * y) mod p can be computed from y and (w 343 * r * y) efficiently using Shamir's trick [MOV97]. Then, 344 server S sends the second message (S, Y) to the user U. 346 U -> S: V_U 347 If the received Y from server S is 0, 1 or -1 (mod p), user U 348 MUST terminate the protocol execution. Otherwise, the user 349 computes K = Y^z mod p where z = 1 / (x + (w * r)) mod q and 350 r = H'(0x01 | U | S | bn2bin(X)). Also, user U generates an 351 authenticator V_U = H(0x02 | U | S | bn2bin(X) | bn2bin(Y) | 352 bn2bin(K)). Then, the user sends the third message V_U to 353 the server S. 355 S -> U: V_S 356 If the received V_U from user U is not equal to H(0x02 | U | 357 S | bn2bin(X) | bn2bin(Y) | bn2bin(K)) where K = g^y mod p, 358 server S MUST terminate the protocol execution. Otherwise, 359 the server generates an authenticator V_S = H(0x03 | U | S | 360 bn2bin(X) | bn2bin(Y) | bn2bin(K)) and a session key SK = 361 H(0x04 | U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)). Then, 362 server S sends the fourth message V_S to the user U. 364 U: 365 If the received V_S from server S is not equal to H(0x03 | U 366 | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)), user U MUST 367 terminate the protocol execution. Otherwise, the user 368 generates a session key SK = H(0x04 | U | S | bn2bin(X) | 369 bn2bin(Y) | bn2bin(K)). 371 In the actual protocol execution, the sequential order of message 372 exchanges is very important in order to avoid any possible attacks. 373 For example, if the server S sends the second message (S, Y) and the 374 fourth message V_S together, any attacker can easily derive the 375 correct password w with offline dictionary attacks. 377 The session key SK, shared only if the user and the server 378 authenticate each other successfully, MAY be generated by using a key 379 derivation function (KDF) [SP800-108]. After generating SK, the user 380 and the server MUST delete all the internal states (e.g., Diffie- 381 Hellman exponents x and y) from memory. 383 For the formal proof [SKI10] of the AugPAKE protocol, we need to 384 change slightly the computation of Y (in the above S -> U: (S, Y)) 385 and K (in the above S -> U: V_S) as follows: Y = (X * (W^r))^y' and K 386 = g^y' where y' = H'(0x05 | bn2bin(y)). 388 3. Security Considerations 390 This section shows why the AugPAKE protocol (i.e., the actual 391 protocol execution) is secure against passive attacks, active attacks 392 and offline dictionary attacks, and also provides resistance to 393 server compromise. 395 3.1. General Assumptions 397 o An attacker is computationally-bounded. 399 o Any hash functions, used in the AugPAKE protocol, are secure in 400 terms of pre-image resistance (one-wayness), second pre-image 401 resistance and collision resistance. 403 3.2. Security against Passive Attacks 405 An augmented PAKE protocol is said to be secure against passive 406 attacks in the sense that an attacker, who eavesdrops the exchanged 407 messages, cannot compute an authenticated session key (shared between 408 the honest parties in the protocol). 410 In the AugPAKE protocol, an attacker can get the messages (U, X), (S, 411 Y), V_U, V_S by eavesdropping, and then wants to compute the session 412 key SK. That is, the attacker's goal is to derive the correct K from 413 the obtained messages X and Y because the hash functions are secure 414 and the only secret in the computation of SK is K = g^y mod p. Note 415 that 417 X = g^x mod p and 419 Y = (X * (W^r))^y = X^y * W^(r * y) = X^y * (g^y)^t = X^y * K^t 421 hold where t = w * r mod q. Though t is determined from possible 422 password candidates and X, the only way for the attacker to extract K 423 from X and Y is to compute X^y. However, the probability for the 424 attacker to compute X^y is negligible in the security parameter for 425 the underlying groups since both x and y are random elements chosen 426 from Z_q^*. Therefore, the AugPAKE protocol is secure against passive 427 attacks. 429 3.3. Security against Active Attacks 431 An augmented PAKE protocol is said to be secure against active 432 attacks in the sense that an attacker, who completely controls the 433 exchanged messages, cannot compute an authenticated session key 434 (shared with the honest party in the protocol) with the probability 435 better than that of on-line dictionary attacks. In other words, the 436 probability for an active attacker to compute the session key is 437 restricted by the on-line dictioinary attacks where it grows linearly 438 to the number of interactions with the honest party. 440 In the AugPAKE protocol, the user (resp., the server) computes the 441 session key SK only if the received authenticator V_S (resp., V_U) is 442 valid. There are three cases to be considered in the active attacks. 444 3.3.1. Impersonation Attacks on User U 446 When an attacker impersonates the user U, the attacker can compute 447 the same SK (to be shared with the server S) only if the 448 authenticator V_U is valid. For a valid authenticator V_U, the 449 attacker has to compute the correct K from X and Y because the hash 450 functions are secure. In this impersonation attack, the attacker of 451 course knows the discrete logarithm x of X and guesses a password w'' 452 from the password dictionary. So, the probability for the attacker 453 to compute the correct K is bounded by the probability of w = w''. 454 That is, this impersonation attack is restricted by the on-line 455 dictionary attacks where the attacker can try a guessed password 456 communicating with the honest server S. Therefore, the AugPAKE 457 protocol is secure against impersonation attacks on user U. 459 3.3.2. Impersonation Attacks on Server S 461 When an attacker impersonates the server S, the attacker can compute 462 the same SK (to be shared with the user U) only if the authenticator 463 V_S is valid. For a valid authenticator V_S, the attacker has to 464 compute the correct K from X and Y because the hash functions are 465 secure. In this impersonation attack, the attacker chooses a random 466 element y and guesses a password w'' from the password dictionary so 467 that 469 Y = (X * (W'^r))^y = X^y * W'^(r * y) = X^y * (g^y)^t' 471 where t' = w'' * r mod q. The probability for the attacker to 472 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 offline 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 offline 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 offline 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 offline 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 offline 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 offline 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 offline 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 571 In the AugPAKE protocol, the user's identity U is sent to the server 572 in clear form. One way to provide user privacy is to use DHE for 573 encrypting the user's identity. 575 4. Implementation Consideration 577 As discussed in Section 3, the AugPAKE protocol is secure against 578 passive attacks, active attacks and offline dictionary attacks, and 579 provides resistance to server compromise. However, an attacker in 580 the on-line dictionary attacks can check whether one password 581 (guessed from the password dictionary) is correct or not by 582 interacting with the honest party. Let N be a dictionary size of 583 passwords. Certainly, the attacker's success probability grows with 584 the probability of (I / N) where I is the number of interactions with 585 the honest party. In order to provide a reasonable security margin, 586 implementation SHOULD take a countermeasure to the on-line dictionary 587 attacks. For example, it would take about 90 years to test 2^(25.5) 588 passwords with one minute lock-out for 3 failed password guesses (see 589 Appendix A in [SP800-63]). 591 5. AugPAKE for TLS 593 5.1. Specification of AugPAKE Handshake 595 The TLS Handshake Protocol [RFC5246], which operates on top of the 596 TLS record layer, is responsible for negotiating a session and 597 agreeing upon security parameters (e.g., PreMasterSecret) of the 598 session state. When protecting subsequent application data, the 599 agreed security parameters are used by the record layer. The AugPAKE 600 protocol, described in Section 2, can be easily integrated into the 601 TLS Handshake Protocol as a password-only mutual authentication by 602 modifying some messages (see Figure 2). This integrated protocol 603 preserves the TLS Handshake Protocol structure and its security 604 guarantees. 606 Client Server 608 ClientHello: name, X --------> 609 ServerHello 610 ServerKeyExchange: Y 611 <-------- ServerHelloDone 612 ClientKeyExchange 613 [ChangeCipherSpec] 614 Finished: V_U --------> 615 [ChangeCipherSpec] 616 <-------- Finished: V_S 618 Application Data <-------> Application Data 619 Figure 2: Plugging AugPAKE into TLS Handshake Protocol 621 5.2. Changes from the TLS Handshake Protocol 623 The changes from the TLS Handshake Protocol are summarized as 624 follows: 626 o The X and the TLS client name (it is preferable to use a hashed 627 value for privacy protection) are included in the "ClientHello" 628 message. 630 o The Y is included in the "ServerKeyExchange" message. 632 o The V_U (resp., V_S) is inclued in the TLS client's (resp., 633 server's) "Finished" message. 635 o The PreMasterSecret in the TLS Handshake Protocol corresponds to K 636 of the AugPAKE protocol in Section 2. The leading bytes of K that 637 contain all zero bits are stripped before it is used as the 638 pre_master_secret. 640 5.2.1. Changes to Client Hello Message 642 The extension of the "ClientHello" message will be 644 enum { AugPAKE (TBD) } ExtensionType; 646 struct { 648 opaque name<1..2^8-1>; 650 opaque X<1..2^16-1>; 652 } Extension; 654 where the extension data field of the AugPAKE extension SHALL contain 655 a "name" to be used to identify the TLS client and the client's 656 Diffie-Hellman public value X. 658 If the TLS server does not find a verifier corresponding to the 659 "name" in the extension of the "ClientHello" message, the server 660 SHOULD keep running the protocol by choosing a random element Y and 661 then rejects the TLS client's "Finished" message with a 662 bad_record_mac alert. Alternatively, the TLS server MAY terminate 663 the protocol if a verifier corresponding to the "name" in the 664 extension of the "ClientHello" message is not found. 666 5.2.2. Changes to Server Key Exchange Message 668 The "ServerKeyExchange" message contains the server's computed value 669 Y (see Section 2). Also, a new value is added to the 670 KeyExchangeAlgorithm to indicate its use of AugPAKE. 672 enum { augpake } KeyExchangeAlgorithm; 674 struct { opaque Y<1..2^16-1>; } ServerAugPAKEParams; 676 6. Acknowledgement 678 We would sincerely appreciate comments from Fabrice Gautier, Watson 679 Ladd and IIari Liusvaara. The AugPAKE protocol described in 680 Section 2 has also been specified as a password-only authentication 681 method for IKEv2. 683 7. IANA Considerations 685 This document requests IANA to assign a value. 687 IANA SHALL assign a value for "AugPAKE" from the TLS ExtensionType 688 Registry defined in [RFC5246] with the method name of "AugPAKE". 690 8. References 692 8.1. Normative References 694 [FIPS180-3] 695 Information Technology Laboratory, , "Secure Hash Standard 696 (SHS)", NIST FIPS Publication 180-3, October 2008, . 700 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 701 Requirement Levels", BCP 14, RFC 2119, March 1997. 703 [RFC3454] Hoffman, P. and M. Blanchet, "Preparation of 704 Internationalized Strings ("stringprep")", RFC 3454, 705 December 2002. 707 [RFC4013] Zeilenga, K., "SASLprep: Stringprep Profile for User Names 708 and Passwords", RFC 4013, February 2005. 710 [RFC4282] Aboba, B., Beadles, M., Arkko, J., and P. Eronen, "The 711 Network Access Identifier", RFC 4282, December 2005. 713 [RFC5246] Dierks, T., Rescorla, E., , , "The Transport Layer 714 Security (TLS) Protocol Version 1.2", RFC 5246, August 715 2008. 717 [SP800-108] 718 Chen, L., "Recommendation for Key Derivation Using 719 Pseudorandom Functions (Revised)", NIST Special 720 Publication 800-108, October 2009, . 723 8.2. Informative References 725 [BJKMRSW00] 726 Bellare, M., Jablon, D., Krawczyk, H., MacKenzie, P., 727 Rogaway, P., Swaminathan, R., and T. Wu, "Proposal for 728 P1363 Study Group on Password-Based Authenticated-Key- 729 Exchange Methods", IEEE P1363.2: Password-Based Public-Key 730 Cryptography , Submissions to IEEE P1363.2 , February 731 2000, . 734 [BM92] Bellovin, S. M. and M. Merritt, "Encrypted Key Exchange: 735 Password-based Protocols Secure against Dictionary 736 Attacks", Proceedings of the IEEE Symposium on Security 737 and Privacy , IEEE Computer Society , 1992. 739 [BM93] Bellovin, S. M. and M. Merritt, "Augmented Encrypted Key 740 Exchange: A Password-based Protocol Secure against 741 Dictionary Attacks and Password File Compromise", 742 Proceedings of the 1st ACM Conference on Computer and 743 Communication Security , ACM Press , 1993. 745 [DH76] Diffie, W. and M. Hellman, "New Directions in 746 Cryptography", IEEE Transactions on Information Theory 747 Volume IT-22, Number 6, 1976. 749 [IEEEP1363.2] 750 IEEE P1363.2, , "Password-Based Public-Key Cryptography", 751 Submissions to IEEE P1363.2 , , . 754 [ISO] ISO/IEC JTC 1/SC 27 11770-4, , "Information technology -- 755 Security techniques -- Key management -- Part 4: 756 Mechanisms based on weak secrets", May 2006, . 760 [MOV97] Menezes, A. J., Oorschot, P. C., and S. A. Vanstone, 761 "Simultaneous Multiple Exponentiation", in Handbook of 762 Applied Cryptography , CRC Press , 1997. 764 [RFC2945] Wu, T. , "The SRP Authentication and Key Exchange System", 765 RFC 2945, September 2000. 767 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman 768 Groups for Use with IETF Standards", RFC 5114, January 769 2008. 771 [SKI10] Shin, S. H., Kobara, K., and H. Imai, "Security Proof of 772 AugPAKE", Cryptology ePrint Archive: Report 2010/334, June 773 2010, . 775 [SK] Shin, S. H. and K. Kobara, "Augmented Password- 776 Authenticated Key Exchange (AugPAKE)", (work in progress), 777 August 2014, . 780 [SP800-56A] 781 Barker, E., Johnson, D., and M. Smid, "Recommendation for 782 Pair-Wise Key Establishment Schemes Using Discrete 783 Logarithm Cryptography (Revised)", NIST Special 784 Publication 800-56A, March 2007, . 788 [SP800-63] 789 Burr, W. E., Dodson, D. F., and W. T. Polk, "Electronic 790 Authentication Guideline", NIST Special Publication 800-63 791 Version 1.0.2, April 2006, . 794 Appendix A. Features of AugPAKE 796 Below are some features of the AugPAKE protocol. 798 Security: 800 AugPAKE is zero knowledge (password) proof. It is secure against 801 passive/active/offline dictionary attacks. It is also resistant 802 to server-compromise impersonation attacks. 804 AugPAKE provides Perfect Forward Secrecy (PFS) and is secure 805 against Denning-Sacco attack. 807 Any cryptographically secure Diffie-Hellman groups can be used. 809 The formal security proof of AugPAKE can be found at [SKI10]. 811 AugPAKE can be easily used with strong credentials. 813 In the case of server compromise, an attacker has to perform 814 offline dictionary attacks while computing modular exponentiation 815 with a password candidate. 817 Intellectual Property: 819 AugPAKE was publicly disclosed on Oct. 2008. 821 AIST applied for a patent in Japan on July 10, 2008. AIST would 822 provide royal-free license of AugPAKE. 824 IPR disclosure (see https://datatracker.ietf.org/ipr/2037/) 826 Miscellaneous: 828 The user needs to compute only 2 modular exponentiation 829 computations while the server needs to compute 2.17 modular 830 exponentiation computations. AugPAKE needs to exchange 2 group 831 elements and 2 hash values. This is almost the same computation/ 832 communication costs as the plain Diffie-Hellman key exchange. If 833 we use a large (e.g., 2048/3072-bits) parent group, the hash size 834 would be relatively small. 836 AugPAKE has the same performance for any type of secret. 838 Internationalization of character-based passwords can be 839 supported. 841 AugPAKE can be implemented over any ECP (Elliptic Curve Group over 842 GF[P]), EC2N (Elliptic Curve Group over GF[2^N]), and MODP 843 (Modular Exponentiation Group) groups. See Appendix 3 of[SK]. 845 AugPAKE has request/response nature. 847 No Trusted Third Party (TTP) and clock synchronization 849 No additional primitive (e.g., Full Domain Hash (FDH) and/or ideal 850 cipher) is needed. 852 Easy implementation. We already implemented AugPAKE and have been 853 testing in AIST. 855 Appendix B. Test Vector of AugPAKE 856 Here is a test vector of the AugPAKE protocol. 858 p = 0x FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 859 43000000000000000000000000000000000000000000000000000000000000 860 00000000000000000000000000000000000000000000000000000000000000 861 00000000000000000000000000000000000000000000000000000000000000 862 00000000000000000000000000000000000000000000000000000000000000 863 00000000000000000000000000000000000000000000000000000000000000 864 00000000000000000000000000000000000000000000000000000000000000 865 00000000000000000000000000000000000000000000000000000000000000 866 00000000000000000000000000000000000000000000000000000000000000 867 00000000000000000000000000000000000000000000000000000000000000 868 00000000000000000000000000000000000000000000000000000000000000 869 0000000000000000330A0DFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 870 FFFFFFFFFFFFFFFFDA5193AB 872 q = 0x FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 873 43 875 g = 0x F1AC99884ABBBBCC9BAA19BF375607FD14570B3019A03871147032445ADA7F 876 A5B8BDC399C1889BBDA197ADB1E3939D55361241F5CD5ED529B0ADD921B274 877 44BD2EB698DC962A9F7D202EAB98BC0C8CC950CA13BC6B1E632D0876A4E796 878 26FDE85F06A46C9991EB02A6D6096E0DF6BCA2CAA12E838BEC47A7CB4AF2B0 879 D94107B9CDBD67327238ECAF84DF292E776AF0F76288B39F9D9E4DDF3A9731 880 CC832D70F150A0F29E7A1E193D1D21CBE8A84B56B0A4692CB39D3048086782 881 85A23F08F9DB402487746F7E2A19CAF2171E55C76337E359217516213FF3BF 882 616F8B20586A8B3168DA444AEA862BB76B9EA2BF8CB84773D29D4EFE511C53 883 95F89CB547EFBBAE333E0BDB22DA40CE0B942A59841A12790910CC1332699D 884 64BBF667E0DF3791C4E29CEB48E8397D50C72F7765C5A18809E3497F6BD374 885 F5D185BBC8F57E36051E11E8DD0C5DD385A9DA442F22598111960CC2B83CBA 886 0A1D980745562F6C62DD6D81B7BAEA7650B1E6E57AB9CC4C95EF17256A79B1 887 31859E1BAC81FF1E 889 U = augpakeuser@aist.go.jp 891 S = augpakeserver@aist.go.jp 893 X = 0x AF261CB6FD99E2E3B4FCDE8A9C538A872EBB54CC82845E8038EA34804DD739 894 90689F2191BF6436BFFD13459DC5FF1FBD56734CA6347ADF52AFAB85EC98A0 895 4D27C122EBAF1840229C2F74E9AEEB79C27ECAF6C8B88FCD5FB3F9C8F20F8F 896 88D45CEBB56D6CAB251DC34D3656DB73E4DF77B71420565D4696DBF8D27023 897 36E909F4C33B2F14605BDEB535423F02B779D7AF0CCB4F3705E177C4334F14 898 707140218197845C708E6ABC025BCA954AA2FDAA352D284DE41D33F7CCFCFD 899 99CAB3CFD34361B6D0551C6D8AEE604316F99758A9C58A96C39AA811E8BA10 900 2E4D21D8F5EFC26920B3F95E6C800D8EBE9914B53144B038BE0E0B43D86479 901 E3CBE623FD148CC90784548C1C7C522C6C71FD4A095B15CBF3EB74C7759493 902 38AC7691A3763C0A3AB97E9E2B439192C49470BF90F292C4A8D336D86780FD 903 DC7DC3C2CC04A6E3AB632788D97D4FDDEE5B117DCF76D91CEA1794FAD91CA1 904 7C9715D83589A00CBB72DD513F6A30E4DB31ACA8DA5D6ECD0E20307D70D6DD 905 0C2D6D3D7962694B5E1B0848 907 Y = 0x 39033C00E1C30FF1A945DD699C516D3BB194FABBB46ADF54A2ED0820FEE0A4 908 DE52128E2126A4393E3040E07D90432B8C19433EC920274E5A7C165DC89AA2 909 C6D77E801A0C7676BC71955A52E74775C57C63B97304C73211C2035BD7B6D1 910 8844A28AC50DD2DA96B257236A6090CCB08D2006BF57AC69EA14ABC5D71BA0 911 6A6BD4093A2EF27C74D5D9189BB2EC865E6321D0DFECDE2D9AC537E8254E98 912 C38AE00BE2554F71FE6EFBBDBE8D7038128957E98C99206998B0B4E578EC47 913 957205C228FAC57B9A1589B8FF2B134980504F56B8A84809B8FF70EFF67520 914 2B255F0724DC0F76F3802D8A42ACC33D349A7FAF249BFBFEB324C3966D2B30 915 6093C32A928A8BEB99AC301D20372E95BB8A3E500778B4651EB8A19B162666 916 8DDFB77D0DF4C1932F1FE63389F3B1F29AE99F34BC39EF0AD04BC3A6A129DE 917 E66E50B6768EDECC529F06FE5F7AD3825E8ECFCB12DB579C40F19D12BF6F60 918 4621F60413DAEB77FE48C136518C57D02A2C6BB596EDFA0DACC127C2FD5FE1 919 9B72580A722307C3F86C0EB1 921 V_U = 0x 490C7CE33DCC3EBE8D0406EEB97CA154882DCBBA0A728F3B870263BCA36 922 9DB6 924 V_S = 0x D70D2CAA821B9D84E29D75EB5E9B2DB038BA1256ECFC35C553832743A6E 925 36F 927 Appendix C. AugPAKE over EC Groups 929 The AugPAKE protocol can be implemented over any elliptic curve 930 groups. The following is such an example. 932 Let p and q be sufficiently large primes, and let m be some positive 933 integer. An elliptic curve E is defined by one of the following two 934 curve equations 936 y^2 = x^3 + a * x + b over the prime field GF(p) or 938 y^2 + x * y = x^3 + a * x^2 + b over the binary field GF(2^m) 940 together with the point at infinity 0_E where x, y, and two 941 coefficients a and b are elements of GF(p) or GF(2^m). Let #E be the 942 number of points on E, and prime q be the order of the desired group. 943 The cofactor k is the value (#E / q) satisfying k = 2^n * q_1 * q_2 944 ... q_t where n = {0,1,2} and every primes q_i > q for i = 1, 2, 945 ..., t. Optionally, k = 2^n. Also, n can be 3 for good performance 946 and security. Let G be a generator for a subgroup of q points on E 947 so that all the subgroup elements are generated by G. The group 948 operation is denoted additively. For example, (X = [x] * G) 949 indicates that an addition computation of G by x times and the 950 resultant value is assigned to X. 952 By using the above elliptic curve groups, the AugPAKE protocol has 953 computational efficiency gains. Specifically, it does not require 954 the order check of elements, received from the counterpart party. 956 The AugPAKE protocol consists of two phases: initialization and 957 actual protocol execution. The initialization phase SHOULD be 958 finished in a secure manner between the user and the server, and it 959 is performed all at once. Whenever the user and the server need to 960 establish a secure channel, they can run the actual protocol 961 execution through an open network (i.e., the Internet) in which an 962 active attacker exists. 964 Initialization 966 U -> S: (U, W) 967 The user U computes W = [w] * G (instead of w, the 968 effective password w' may be used), and transmits W to the 969 server S. The W is registered in the server as the 970 password verifier of user U. Of course, user U just 971 remembers the password w only. 973 Actual Protocol Execution 975 U -> S: (U, X) 976 The user U chooses a random element x from Z_q^* and 977 computes its elliptic curve Diffie-Hellman public value X 978 = [x] * G. The user sends the first message (U, X) to the 979 server S. 981 S -> U: (S, Y) 982 If the received X from user U is not a point on E or [2^n] 983 * X = 0_E, server S MUST terminate the protocol execution. 984 Otherwise, the server chooses a random element y from 985 Z_q^* and computes Y = [y] * (X + ([r] * W)) where r = 986 H'(0x01 | U | S | bn2bin(X)). Then, server S sends the 987 second message (S, Y) to the user U. 989 U -> S: V_U 990 If the received Y from server S is not a point on E or 991 [2^n] * Y = 0_E, user U MUST terminate the protocol 992 execution. Otherwise, the user computes K = [z] * Y where 993 z = 1 / (x + (w * r)) mod q and r = H'(0x01 | U | S | 994 bn2bin(X)). Also, user U generates an authenticator V_U = 995 H(0x02 | U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)). 996 Then, the user sends the third message V_U to the server 997 S. 999 S -> U: V_S 1000 If the received V_U from user U is not equal to H(0x02 | U 1001 | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)) where K = [y] * 1002 G, server S MUST terminate the protocol execution. 1003 Otherwise, the server generates an authenticator V_S = 1004 H(0x03 | U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)) and a 1005 session key SK = H(0x04 | U | S | bn2bin(X) | bn2bin(Y) | 1006 bn2bin(K)). Then, server S sends the fourth message V_S 1007 to the user U. 1009 U: 1010 If the received V_S from server S is not equal to H(0x03 | 1011 U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)), user U MUST 1012 terminate the protocol execution. Otherwise, the user 1013 generates a session key SK = H(0x04 | U | S | bn2bin(X) | 1014 bn2bin(Y) | bn2bin(K)). 1016 Authors' Addresses 1018 SeongHan Shin 1019 AIST 1020 2-4-7 Aomi, Koto-ku 1021 Tokyo, Tokyo 135-0064 1022 JP 1024 Phone: +81-3-3599-8001 1025 Email: seonghan.shin@aist.go.jp 1027 Kazukuni Kobara 1028 AIST 1030 Email: kobara_conf-ml@aist.go.jp