idnits 2.17.1 draft-irtf-cfrg-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 (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: Informational ---------------------------------------------------------------------------- == Missing Reference: 'P' is mentioned on line 732, but not defined == Unused Reference: 'IEEE1363.2' is defined on line 635, but no explicit reference was found in the text ** 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) Summary: 3 errors (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Research Task Force S.H. Shin 3 Internet-Draft K. Kobara 4 Intended status: Informational AIST 5 Expires: January 20, 2018 July 19, 2017 7 Augmented Password-Authenticated Key Exchange (AugPAKE) 8 draft-irtf-cfrg-augpake-08 10 Abstract 12 This document describes a secure and highly-efficient augmented 13 password-authenticated key exchange (AugPAKE) protocol where a user 14 remembers a low-entropy password and its verifier is registered in 15 the intended server. In general, the user's password is chosen from 16 a small set of dictionary, making the password susceptible to offline 17 dictionary attacks. The AugPAKE protocol described here is secure 18 against passive attacks, active attacks and offline dictionary 19 attacks (on the obtained messages with passive/active attacks). 20 Also, this protocol provides resistance to server compromise in the 21 context that an attacker, who obtained the password verifier from the 22 server, must at least perform offline dictionary attacks to gain any 23 advantage in impersonating the user. The AugPAKE protocol is not 24 only provably secure in the random oracle model but also the most 25 efficient over the previous augmented PAKE protocols (SRP and AMP). 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at http://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on January 20, 2018. 44 Copyright Notice 46 Copyright (c) 2017 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents 51 (http://trustee.ietf.org/license-info) in effect on the date of 52 publication of this document. Please review these documents 53 carefully, as they describe your rights and restrictions with respect 54 to this document. Code Components extracted from this document must 55 include Simplified BSD License text as described in Section 4.e of 56 the Trust Legal Provisions and are provided without warranty as 57 described in the Simplified BSD License. 59 Table of Contents 61 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 62 1.1. Keywords . . . . . . . . . . . . . . . . . . . . . . . . 3 63 2. AugPAKE Specification . . . . . . . . . . . . . . . . . . . . 4 64 2.1. Underlying Group . . . . . . . . . . . . . . . . . . . . 4 65 2.2. Notation . . . . . . . . . . . . . . . . . . . . . . . . 4 66 2.2.1. Password Processing . . . . . . . . . . . . . . . . . 6 67 2.3. Protocol . . . . . . . . . . . . . . . . . . . . . . . . 6 68 2.3.1. Initialization . . . . . . . . . . . . . . . . . . . 7 69 2.3.2. Actual Protocol Execution . . . . . . . . . . . . . . 7 70 3. Security Considerations . . . . . . . . . . . . . . . . . . . 9 71 3.1. General Assumptions . . . . . . . . . . . . . . . . . . . 9 72 3.2. Security against Passive Attacks . . . . . . . . . . . . 9 73 3.3. Security against Active Attacks . . . . . . . . . . . . . 10 74 3.3.1. Impersonation Attacks on User U . . . . . . . . . . . 10 75 3.3.2. Impersonation Attacks on Server S . . . . . . . . . . 10 76 3.3.3. Man-in-the-Middle Attacks . . . . . . . . . . . . . . 11 77 3.4. Security against Off-line Dictionary Attacks . . . . . . 11 78 3.5. Resistance to Server Compromise . . . . . . . . . . . . . 12 79 4. Implementation Consideration . . . . . . . . . . . . . . . . 13 80 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 81 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 13 82 6.1. Normative References . . . . . . . . . . . . . . . . . . 13 83 6.2. Informative References . . . . . . . . . . . . . . . . . 14 84 Appendix A. Features of AugPAKE . . . . . . . . . . . . . . . . 15 85 Appendix B. Test Vector of AugPAKE . . . . . . . . . . . . . . . 16 86 Appendix C. AugPAKE over EC Groups . . . . . . . . . . . . . . . 18 87 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 89 1. Introduction 90 In the real world, many applications such as web mail, Internet 91 banking/shopping/trade require secure channels between participating 92 parties. Such secure channels can be established by using an 93 authenticated key exchange (AKE) protocol, which allows the involving 94 parties to authenticate each other and to generate a temporary 95 session key. The temporary session key is used to protect the 96 subsequent communications between the parties. 98 Until now, password-only AKE (called, PAKE) protocols have attracted 99 much attention because password-only authentication is very 100 convenient to the users. However, it is not trivial to design a 101 secure PAKE protocol due to the existence of offline dictionary 102 attacks on passwords. These attacks are possible since passwords are 103 chosen from a relatively-small dictionary that allows for an attacker 104 to perform the exhaustive searches. This problem was brought forth 105 by Bellovin and Merritt [BM92], and many following works have been 106 conducted in the literature (see some examples in [IEEEP1363.2]). A 107 PAKE protocol is said to be secure if the best attack an active 108 attacker can take is restricted to the on-line dictionary attacks, 109 which allow to check a guessed password only by interacting with the 110 honest party. 112 An augmented PAKE protocol (e.g., [BM93], [RFC2945], [ISOIEC11770-4], 113 [IEEEP1363.2]) provides extra protection for server compromise in the 114 sense that an attacker, who obtained a password verifier from a 115 server, cannot impersonate the corresponding user without performing 116 offline dictionary attacks on the password verifier. This additional 117 security is known as "resistance to server compromise". The AugPAKE 118 protocol described in this document is an augmented PAKE which also 119 achieves highly efficiency over the previous works (SRP [RFC2945], 120 [ISOIEC11770-4], and AMP [ISOIEC11770-4]). In summary, 1) The 121 AugPAKE protocol is secure against passive attacks, active attacks 122 and offline dictionary attacks on the obtained messages with passive/ 123 active attacks (see [SKI10] for the formal security proof), and 2) It 124 provides resistance to server compromise. At the same time, the 125 AugPAKE protocol has similar computational efficiency to the plain 126 Diffie-Hellman key exchange [DH76] that does not provide 127 authentication by itself. Specifically, the user and the server need 128 to compute 2 and 2.17 modular exponentiations, respectively, in the 129 AugPAKE protocol. After excluding pre-computable costs, the user and 130 the server are required to compute only 1 and 1.17 modular 131 exponentiations, respectively. Compared with SRP [RFC2945], 132 [ISOIEC11770-4], and AMP [ISOIEC11770-4], the AugPAKE protocol is 133 more efficient 1) than SRP in terms of the user's computational costs 134 and 2) than AMP in terms of the server's computational costs. 136 1.1. Keywords 137 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 138 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 139 document are to be interpreted as described in RFC 2119 [RFC2119]. 141 2. AugPAKE Specification 143 2.1. Underlying Group 145 The AugPAKE protocol can be implemented over the following group. 147 o Let p and q be sufficiently large primes such that q is a divisor 148 of ((p - 1) / 2) and every factors of ((p - 1) / 2) are also 149 primes comparable to q in size. This p is called a "secure" 150 prime. We denote by G a multiplicative subgroup of prime order q 151 over the field GF(p), the integers modulo p. Let g be a generator 152 for the subgroup G so that all the subgroup elements are generated 153 by g. The group operation is denoted multiplicatively (in modulo 154 p). 156 By using a secure prime p, the AugPAKE protocol has computational 157 efficiency gains. Specifically, it does not require the order check 158 of elements, received from the counterpart party. Note that the 159 groups, defined in Discrete Logarithm Cryptography [SP800-56A] and 160 RFC 5114 [RFC5114], are not necessarily the above secure prime 161 groups. 163 Alternatively, one can implement the AugPAKE protocol over the 164 following groups. 166 o Let p and q be sufficiently large primes such that p = (2 * q) + 167 1. This p is called a "safe" prime. We denote by G a 168 multiplicative subgroup of prime order q over the field GF(p), the 169 integers modulo p. Let g be any element of G other than 1. For 170 example, g = h^2 mod p where h is a primitive element. The group 171 operation is denoted multiplicatively (in modulo p). 173 o Let p and q be sufficiently large primes such that q is a divisor 174 of ((p - 1) / 2). We denote by G a multiplicative subgroup of 175 prime order q over the field GF(p), the integers modulo p. Let g 176 be a generator for the subgroup G so that all the subgroup 177 elements are generated by g. The group operation is denoted 178 multiplicatively (in modulo p). If p is not a "secure" prime, the 179 AugPAKE protocol MUST perform the order check of received 180 elements. 182 2.2. Notation 183 The AugPAKE protocol is a two-party protocol where a user and a 184 server authenticate each other and generate a session key. The 185 following notation is used in this document: 187 U 188 The user's identity (e.g., defined in [RFC4282]). It is a string 189 in {0,1}^* where {0,1}^* indicates a set of finite binary 190 strings. 192 S 193 The server's identity. It is a string in {0,1}^*. 195 b = H(a) 196 A binary string a is given as input to a secure one-way hash 197 function H (e.g., SHA-2 family [FIPS180-3]) which produces a 198 fixed-length output b. The hash function H maps {0,1}^* to 199 {0,1}^k where {0,1}^k indicates a set of binary strings of length 200 k and k is a security parameter. 202 b = H'(a) 203 A binary string a is given as input to a secure one-way hash 204 function H' which maps the input a in {0,1}^* to the output b in 205 Z_q^* where Z_q^* is a set of positive integers modulo prime q. 207 a | b 208 It denotes a concatenation of binary strings a and b in {0,1}^*. 210 0x 211 A hexadecimal value is shown preceded by "0x". 213 X * Y mod p 214 It indicates a multiplication of X and Y modulo prime p. 216 X = g^x mod p 217 The g^x indicates a multiplication computation of g by x times. 218 The resultant value modulo prime p is assigned to X. The 219 discrete logarithm problem says that it is computationally hard 220 to compute the discrete logarithm x from X, g and p. 222 w 223 The password remembered by the user. This password may be used 224 as an effective password (instead of itself) in the form of 225 H'(0x00 | U | S | w). 227 W 228 The password verifier registered in the server. This password 229 verifier is computed as follows: W = g^w mod p where the user's 230 password w is used itself, or W = g^w' mod p where the effective 231 password w' = H'(0x00 | U | S | w) is used. 233 bn2bin(X) 234 It indicates a conversion of a multiple precision integer X to 235 the corresponding binary string. If X is an element over GF(p), 236 its binary representation MUST have the same bit length as the 237 binary representation of prime p. 239 U -> S: msg 240 It indicates a message transmission that the user U sends a 241 message msg to the server S. 243 U: 244 It indicates a local computation of user U (without any out-going 245 messages). 247 2.2.1. Password Processing 249 The input password MUST be processed according to the rules of the 250 [RFC4013] profile of [RFC3454]. The password SHALL be considered a 251 "stored string" per [RFC3454] and unassigned code points are 252 therefore prohibited. The output SHALL be the binary representation 253 of the processed UTF-8 character string. Prohibited output and 254 unassigned code points encountered in SASLprep pre-processing SHALL 255 cause a failure of pre-processing and the output SHALL NOT be used 256 with the AugPAKE protocol. 258 The following table shows examples of how various character data is 259 transformed by the rules of the [RFC4013] profile. 261 # Input Output Comments 262 - ----- ------ -------- 263 1 IX IX SOFT HYPHEN mapped to nothing 264 2 user user no transformation 265 3 USER USER case preserved, will not match #2 266 4 a output is NFKC, input in ISO 8859-1 267 5 IX output is NFKC, will match #1 268 6 Error - prohibited character 269 7 Error - bidirectional check 271 2.3. Protocol 273 The AugPAKE protocol consists of two phases: initialization and 274 actual protocol execution. The initialization phase SHOULD be 275 finished in a secure manner between the user and the server, and it 276 is performed all at once. Whenever the user and the server need to 277 establish a secure channel, they can run the actual protocol 278 execution through an open network (i.e., the Internet) in which an 279 active attacker exists. 281 2.3.1. Initialization 283 U -> S: (U, W) 284 The user U computes W = g^w mod p (instead of w, the 285 effective password w' may be used), and transmits W to the 286 server S. The W is registered in the server as the password 287 verifier of user U. Of course, user U just remembers the 288 password w only. 290 If resistance to server compromise is not necessary, the server can 291 store w' instead of W. In either case, server S SHOULD NOT store any 292 plaintext passwords. 294 As noted above, this phase SHOULD be performed securely and all at 295 once. 297 2.3.2. Actual Protocol Execution 299 The actual protocol execution of the AugPAKE protocol allows the user 300 and the server to share an authenticated session key through an open 301 network (see Figure 1). 303 +-----------------+ +------------------+ 304 | User U | | Server S (U,W) | 305 | | (U, X) | | 306 | |----------------------------->| | 307 | | | | 308 | | (S, Y) | | 309 | |<-----------------------------| | 310 | | | | 311 | | V_U | | 312 | |----------------------------->| | 313 | | | | 314 | | V_S | | 315 | |<-----------------------------| | 316 | | | | 317 +-----------------+ +------------------+ 319 Figure 1: Actual Protocol Execution of AugPAKE 321 U -> S: (U, X) 322 The user U chooses a random element x from Z_q^* and computes 323 its Diffie-Hellman public value X = g^x mod p. The user 324 sends the first message (U, X) to the server S. 326 S -> U: (S, Y) 327 If the received X from user U is 0, 1 or -1 (mod p), server S 328 MUST terminate the protocol execution. Otherwise, the server 329 chooses a random element y from Z_q^* and computes Y = (X * 330 (W^r))^y mod p where r = H'(0x01 | U | S | bn2bin(X)). Note 331 that X^y * g^(w * r * y) mod p can be computed from y and (w 332 * r * y) efficiently using Shamir's trick [MOV97]. Then, 333 server S sends the second message (S, Y) to the user U. 335 U -> S: V_U 336 If the received Y from server S is 0, 1 or -1 (mod p), user U 337 MUST terminate the protocol execution. Otherwise, the user 338 computes K = Y^z mod p where z = 1 / (x + (w * r)) mod q and 339 r = H'(0x01 | U | S | bn2bin(X)). Also, user U generates an 340 authenticator V_U = H(0x02 | U | S | bn2bin(X) | bn2bin(Y) | 341 bn2bin(K)). Then, the user sends the third message V_U to 342 the server S. 344 S -> U: V_S 345 If the received V_U from user U is not equal to H(0x02 | U | 346 S | bn2bin(X) | bn2bin(Y) | bn2bin(K)) where K = g^y mod p, 347 server S MUST terminate the protocol execution. Otherwise, 348 the server generates an authenticator V_S = H(0x03 | U | S | 349 bn2bin(X) | bn2bin(Y) | bn2bin(K)) and a session key SK = 350 H(0x04 | U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)). Then, 351 server S sends the fourth message V_S to the user U. 353 U: 354 If the received V_S from server S is not equal to H(0x03 | U 355 | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)), user U MUST 356 terminate the protocol execution. Otherwise, the user 357 generates a session key SK = H(0x04 | U | S | bn2bin(X) | 358 bn2bin(Y) | bn2bin(K)). 360 In the actual protocol execution, the sequential order of message 361 exchanges is very important in order to avoid any possible attacks. 362 For example, if the server S sends the second message (S, Y) and the 363 fourth message V_S together, any attacker can easily derive the 364 correct password w with offline dictionary attacks. 366 The session key SK, shared only if the user and the server 367 authenticate each other successfully, MAY be generated by using a key 368 derivation function (KDF) [SP800-108]. After generating SK, the user 369 and the server MUST delete all the internal states (e.g., Diffie- 370 Hellman exponents x and y) from memory. 372 For the formal proof [SKI10] of the AugPAKE protocol, we need to 373 change slightly the computation of Y (in the above S -> U: (S, Y)) 374 and K (in the above S -> U: V_S) as follows: Y = (X * (W^r))^y' and K 375 = g^y' where y' = H'(0x05 | bn2bin(y)). 377 3. Security Considerations 379 This section shows why the AugPAKE protocol (i.e., the actual 380 protocol execution) is secure against passive attacks, active attacks 381 and offline dictionary attacks, and also provides resistance to 382 server compromise. 384 3.1. General Assumptions 386 o An attacker is computationally-bounded. 388 o Any hash functions, used in the AugPAKE protocol, are secure in 389 terms of pre-image resistance (one-wayness), second pre-image 390 resistance and collision resistance. 392 3.2. Security against Passive Attacks 394 An augmented PAKE protocol is said to be secure against passive 395 attacks in the sense that an attacker, who eavesdrops the exchanged 396 messages, cannot compute an authenticated session key (shared between 397 the honest parties in the protocol). 399 In the AugPAKE protocol, an attacker can get the messages (U, X), (S, 400 Y), V_U, V_S by eavesdropping, and then wants to compute the session 401 key SK. That is, the attacker's goal is to derive the correct K from 402 the obtained messages X and Y because the hash functions are secure 403 and the only secret in the computation of SK is K = g^y mod p. Note 404 that 406 X = g^x mod p and 408 Y = (X * (W^r))^y = X^y * W^(r * y) = X^y * (g^y)^t = X^y * K^t 410 hold where t = w * r mod q. Though t is determined from possible 411 password candidates and X, the only way for the attacker to extract K 412 from X and Y is to compute X^y. However, the probability for the 413 attacker to compute X^y is negligible in the security parameter for 414 the underlying groups since both x and y are random elements chosen 415 from Z_q^*. Therefore, the AugPAKE protocol is secure against passive 416 attacks. 418 3.3. Security against Active Attacks 420 An augmented PAKE protocol is said to be secure against active 421 attacks in the sense that an attacker, who completely controls the 422 exchanged messages, cannot compute an authenticated session key 423 (shared with the honest party in the protocol) with the probability 424 better than that of on-line dictionary attacks. In other words, the 425 probability for an active attacker to compute the session key is 426 restricted by the on-line dictioinary attacks where it grows linearly 427 to the number of interactions with the honest party. 429 In the AugPAKE protocol, the user (resp., the server) computes the 430 session key SK only if the received authenticator V_S (resp., V_U) is 431 valid. There are three cases to be considered in the active attacks. 433 3.3.1. Impersonation Attacks on User U 435 When an attacker impersonates the user U, the attacker can compute 436 the same SK (to be shared with the server S) only if the 437 authenticator V_U is valid. For a valid authenticator V_U, the 438 attacker has to compute the correct K from X and Y because the hash 439 functions are secure. In this impersonation attack, the attacker of 440 course knows the discrete logarithm x of X and guesses a password w'' 441 from the password dictionary. So, the probability for the attacker 442 to compute the correct K is bounded by the probability of w = w''. 443 That is, this impersonation attack is restricted by the on-line 444 dictionary attacks where the attacker can try a guessed password 445 communicating with the honest server S. Therefore, the AugPAKE 446 protocol is secure against impersonation attacks on user U. 448 3.3.2. Impersonation Attacks on Server S 450 When an attacker impersonates the server S, the attacker can compute 451 the same SK (to be shared with the user U) only if the authenticator 452 V_S is valid. For a valid authenticator V_S, the attacker has to 453 compute the correct K from X and Y because the hash functions are 454 secure. In this impersonation attack, the attacker chooses a random 455 element y and guesses a password w'' from the password dictionary so 456 that 458 Y = (X * (W'^r))^y = X^y * W'^(r * y) = X^y * (g^y)^t' 460 where t' = w'' * r mod q. The probability for the attacker to 461 compute the correct K is bounded by the probability of w = w''. 463 Also, the attacker knows whether the guessed password is equal to w 464 or not by seeing the received authenticator V_U. However, when w is 465 not equal to w'', the probability for the attacker to compute the 466 correct K is negligible in the security parameter for the underlying 467 groups since the attacker has to guess the discrete logarithm x 468 (chosen by user U) as well. That is, this impersonation attack is 469 restricted by the on-line dictionary attacks where the attacker can 470 try a guessed password communicating with the honest user U. 471 Therefore, the AugPAKE protocol is secure against impersonation 472 attacks on server S. 474 3.3.3. Man-in-the-Middle Attacks 476 When an attacker performs the man-in-the-middle attack, the attacker 477 can compute the same SK (to be shared with the user U or the server 478 S) only if one of the authenticators V_U, V_S is valid. Note that if 479 the attacker relays the exchanged messages honestly, it corresponds 480 to the passive attacks. In order to generate a valid authenticator 481 V_U or V_S, the attacker has to compute the correct K from X and Y 482 because the hash functions are secure. So, the attacker is in the 483 same situation as discussed above. Though the attacker can test two 484 passwords (one with user U and the other with server S), it does not 485 change the fact that this attack is restricted by the on-line 486 dictionary attacks where the attacker can try a guessed password 487 communicating with the honest party. Therefore, the AugPAKE protocol 488 is also secure against man-in-the-middle attacks. 490 3.4. Security against Off-line Dictionary Attacks 492 An augmented PAKE protocol is said to be secure against offline 493 dictionary attacks in the sense that an attacker, who completely 494 controls the exchanged messages, cannot reduce the possible password 495 candidates better than on-line dictionary attacks. Note that, in the 496 on-line dictionary attacks, an attacker can test one guessed password 497 by running the protocol execution (i.e., communicating with the 498 honest party). 500 As discussed in Section 3.2, an attacker in the passive attacks does 501 not compute X^y (and the correct K = g^y mod p) from the obtained 502 messages X, Y. This security analysis also indicates that, even if 503 the attacker can guess a password, the K is derived independently 504 from the guessed password. Next, we consider an active attacker 505 whose main goal is to perform the offline dictionary attacks in the 506 AugPAKE protocol. As in Section 3.3, the attacker can 1) test one 507 guessed password by impersonating the user U or the server S, or 2) 508 test two guessed passwords by impersonating the server S (to the 509 honest user U) and impersonating the user U (to the honest server S) 510 in the man-in-the-middle attacks. Whenever the honest party receives 511 an invalid authenticator, the party terminates the actual protocol 512 execution without sending any message. In fact, this is important to 513 prevent an attacker from testing more than one password in the active 514 attacks. Since passive attacks and active attacks cannot remove the 515 possible password candidates efficiently than on-line dictionary 516 attacks, the AugPAKE protocol is secure against offline dictionary 517 attacks. 519 3.5. Resistance to Server Compromise 521 We consider an attacker who has obtained a (user's) password verifier 522 from a server. In the (augmented) PAKE protocols, there are two 523 limitations [BJKMRSW00]: 1) the attacker can find out the correct 524 password from the password verifier with the offline dictionary 525 attacks because the verifier has the same entropy as the password; 526 and 2) if the attacker impersonates the server with the password 527 verifier, this attack is always possible because the attacker has 528 enough information to simulate the server. An augmented PAKE 529 protocol is said to provide resistance to server compromise in the 530 sense that the attacker cannot impersonate the user without 531 performing offline dictionary attacks on the password verifier. 533 In order to show resistance to server compromise in the AugPAKE 534 protocol, we consider an attacker who has obtained the password 535 verifier W and then tries to impersonate the user U without offline 536 dictionary attacks on W. As a general attack, the attacker chooses 537 two random elements c and d from Z_q^*, and computes 539 X = (g^c) * (W^d) mod p 541 and sends the first message (U, X) to the server S. In order to 542 impersonate user U successfully, the attacker has to compute the 543 correct K = g^y mod p where y is randomly chosen by server S. After 544 receiving Y from the server, the attacker's goal is to find out a 545 value e satisfying Y^e = K mod p. That is, 547 log_g (Y^e) = log_g K mod q 549 (c + (w * d) + (w * r)) * y * e = y mod q 551 (c + w * (d + r)) * e = 1 mod q 553 where log_g K indicates the logarithm of K to the base g. Since 554 there is no offline dictionary attacks on W, the above solution is 555 that e = 1 / c mod q and d = -r mod q. However, the latter is not 556 possible since r is determined by X (i.e., r = H'(0x01 | U | S | 557 bn2bin(X))) and H' is a secure hash function. Therefore, the AugPAKE 558 protocol provides resistance to server compromise. 560 4. Implementation Consideration 562 As discussed in Section 3, the AugPAKE protocol is secure against 563 passive attacks, active attacks and offline dictionary attacks, and 564 provides resistance to server compromise. However, an attacker in 565 the on-line dictionary attacks can check whether one password 566 (guessed from the password dictionary) is correct or not by 567 interacting with the honest party. Let N be a dictionary size of 568 passwords. Certainly, the attacker's success probability grows with 569 the probability of (I / N) where I is the number of interactions with 570 the honest party. In order to provide a reasonable security margin, 571 implementation SHOULD take a countermeasure to the on-line dictionary 572 attacks. For example, it would take about 90 years to test 2^(25.5) 573 passwords with one minute lock-out for 3 failed password guesses (see 574 Appendix A in [SP800-63]). 576 5. IANA Considerations 578 This document has no request to IANA. 580 6. References 582 6.1. Normative References 584 [FIPS180-3] 585 Information Technology Laboratory, , "Secure Hash Standard 586 (SHS)", NIST FIPS Publication 180-3, October 2008, . 590 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 591 Requirement Levels", BCP 14, RFC 2119, March 1997. 593 [RFC3454] Hoffman, P. and M. Blanchet, "Preparation of 594 Internationalized Strings ("stringprep")", RFC 3454, 595 December 2002. 597 [RFC4013] Zeilenga, K., "SASLprep: Stringprep Profile for User Names 598 and Passwords", RFC 4013, February 2005. 600 [RFC4282] Aboba, B., Beadles, M., Arkko, J., and P. Eronen, "The 601 Network Access Identifier", RFC 4282, December 2005. 603 [SP800-108] 604 Chen, L., "Recommendation for Key Derivation Using 605 Pseudorandom Functions (Revised)", NIST Special 606 Publication 800-108, October 2009, . 609 6.2. Informative References 611 [BJKMRSW00] 612 Bellare, M., Jablon, D., Krawczyk, H., MacKenzie, P., 613 Rogaway, P., Swaminathan, R., and T. Wu, "Proposal for 614 P1363 Study Group on Password-Based Authenticated-Key- 615 Exchange Methods", IEEE P1363.2: Password-Based Public-Key 616 Cryptography , Submissions to IEEE P1363.2 , February 617 2000, . 620 [BM92] Bellovin, S. M. and M. Merritt, "Encrypted Key Exchange: 621 Password-based Protocols Secure against Dictionary 622 Attacks", Proceedings of the IEEE Symposium on Security 623 and Privacy , IEEE Computer Society , 1992. 625 [BM93] Bellovin, S. M. and M. Merritt, "Augmented Encrypted Key 626 Exchange: A Password-based Protocol Secure against 627 Dictionary Attacks and Password File Compromise", 628 Proceedings of the 1st ACM Conference on Computer and 629 Communication Security , ACM Press , 1993. 631 [DH76] Diffie, W. and M. Hellman, "New Directions in 632 Cryptography", IEEE Transactions on Information Theory 633 Volume IT-22, Number 6, 1976. 635 [IEEE1363.2] 636 IEEE 1363.2, , "IEEE Standard Specifications for Password- 637 Based Public-Key Cryptographic Techniques", IEEE Std 638 1363.2, IEEE Computer Society , January 2009. 640 [IEEEP1363.2] 641 IEEE P1363.2, , "Password-Based Public-Key Cryptography", 642 Submissions to IEEE P1363.2 , , . 645 [ISOIEC11770-4] 646 ISO/IEC 11770-4, , "Information technology -- Security 647 techniques -- Key management -- Part 4: Mechanisms based 648 on weak secrets", International Standard ISO/IEC 649 11770-4:2006, May 2006, . 653 [MOV97] Menezes, A. J., Oorschot, P. C., and S. A. Vanstone, 654 "Simultaneous Multiple Exponentiation", in Handbook of 655 Applied Cryptography , CRC Press , 1997. 657 [RFC2945] Wu, T., "The SRP Authentication and Key Exchange System", 658 RFC 2945, September 2000. 660 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman 661 Groups for Use with IETF Standards", RFC 5114, January 662 2008. 664 [SKI10] Shin, S. H., Kobara, K., and H. Imai, "Security Proof of 665 AugPAKE", Cryptology ePrint Archive: Report 2010/334, June 666 2010, . 668 [SP800-56A] 669 Barker, E., Johnson, D., and M. Smid, "Recommendation for 670 Pair-Wise Key Establishment Schemes Using Discrete 671 Logarithm Cryptography (Revised)", NIST Special 672 Publication 800-56A, March 2007, . 676 [SP800-63] 677 Burr, W. E., Dodson, D. F., and W. T. Polk, "Electronic 678 Authentication Guideline", NIST Special Publication 800-63 679 Version 1.0.2, April 2006, . 682 Appendix A. Features of AugPAKE 684 Below are some features of the AugPAKE protocol. 686 Security: 688 o AugPAKE is zero knowledge (password) proof. It is secure against 689 passive/active/offline dictionary attacks. It is also resistant 690 to server-compromise impersonation attacks. 692 o AugPAKE provides Perfect Forward Secrecy (PFS) and is secure 693 against Denning-Sacco attack. 695 o Any cryptographically secure Diffie-Hellman groups can be used. 697 o The formal security proof of AugPAKE can be found at [SKI10]. 699 o AugPAKE can be easily used with strong credentials. 701 o In the case of server compromise, an attacker has to perform 702 offline dictionary attacks while computing modular exponentiation 703 with a password candidate. 705 Intellectual Property: 707 o AugPAKE was publicly disclosed on Oct. 2008. 709 o AIST applied for a patent in Japan on July 10, 2008. AIST would 710 provide royal-free license of AugPAKE. 712 o IPR disclosure (see https://datatracker.ietf.org/ipr/2037/) 714 Miscellaneous: 716 o The user needs to compute only 2 modular exponentiation 717 computations while the server needs to compute 2.17 modular 718 exponentiation computations. AugPAKE needs to exchange 2 group 719 elements and 2 hash values. This is almost the same computation/ 720 communication costs as the plain Diffie-Hellman key exchange. If 721 we use a large (e.g., 2048/3072-bits) parent group, the hash size 722 would be relatively small. 724 o AugPAKE can be easily converted to 'balanced' PAKE. 726 o AugPAKE has the same performance for any type of secret. 728 o Internationalization of character-based passwords can be 729 supported. 731 o AugPAKE can be implemented over any ECP (Elliptic Curve Group over 732 GF[P]), EC2N (Elliptic Curve Group over GF[2^N]), and MODP 733 (Modular Exponentiation Group) groups. 735 o AugPAKE has request/response nature. 737 o No Trusted Third Party (TTP) and clock synchronization 739 o No additional primitive (e.g., Full Domain Hash (FDH) and/or ideal 740 cipher) is needed. 742 o Easy implementation. We already implemented AugPAKE and have been 743 testing in AIST. 745 Appendix B. Test Vector of AugPAKE 747 Here is a test vector of the AugPAKE protocol. 749 p = 0x FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 750 43000000000000000000000000000000000000000000000000000000000000 751 00000000000000000000000000000000000000000000000000000000000000 752 00000000000000000000000000000000000000000000000000000000000000 753 00000000000000000000000000000000000000000000000000000000000000 754 00000000000000000000000000000000000000000000000000000000000000 755 00000000000000000000000000000000000000000000000000000000000000 756 00000000000000000000000000000000000000000000000000000000000000 757 00000000000000000000000000000000000000000000000000000000000000 758 00000000000000000000000000000000000000000000000000000000000000 759 00000000000000000000000000000000000000000000000000000000000000 760 0000000000000000330A0DFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 761 FFFFFFFFFFFFFFFFDA5193AB 763 q = 0x FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 764 43 766 g = 0x F1AC99884ABBBBCC9BAA19BF375607FD14570B3019A03871147032445ADA7F 767 A5B8BDC399C1889BBDA197ADB1E3939D55361241F5CD5ED529B0ADD921B274 768 44BD2EB698DC962A9F7D202EAB98BC0C8CC950CA13BC6B1E632D0876A4E796 769 26FDE85F06A46C9991EB02A6D6096E0DF6BCA2CAA12E838BEC47A7CB4AF2B0 770 D94107B9CDBD67327238ECAF84DF292E776AF0F76288B39F9D9E4DDF3A9731 771 CC832D70F150A0F29E7A1E193D1D21CBE8A84B56B0A4692CB39D3048086782 772 85A23F08F9DB402487746F7E2A19CAF2171E55C76337E359217516213FF3BF 773 616F8B20586A8B3168DA444AEA862BB76B9EA2BF8CB84773D29D4EFE511C53 774 95F89CB547EFBBAE333E0BDB22DA40CE0B942A59841A12790910CC1332699D 775 64BBF667E0DF3791C4E29CEB48E8397D50C72F7765C5A18809E3497F6BD374 776 F5D185BBC8F57E36051E11E8DD0C5DD385A9DA442F22598111960CC2B83CBA 777 0A1D980745562F6C62DD6D81B7BAEA7650B1E6E57AB9CC4C95EF17256A79B1 778 31859E1BAC81FF1E 780 U = augpakeuser@aist.go.jp 782 S = augpakeserver@aist.go.jp 784 X = 0x AF261CB6FD99E2E3B4FCDE8A9C538A872EBB54CC82845E8038EA34804DD739 785 90689F2191BF6436BFFD13459DC5FF1FBD56734CA6347ADF52AFAB85EC98A0 786 4D27C122EBAF1840229C2F74E9AEEB79C27ECAF6C8B88FCD5FB3F9C8F20F8F 787 88D45CEBB56D6CAB251DC34D3656DB73E4DF77B71420565D4696DBF8D27023 788 36E909F4C33B2F14605BDEB535423F02B779D7AF0CCB4F3705E177C4334F14 789 707140218197845C708E6ABC025BCA954AA2FDAA352D284DE41D33F7CCFCFD 790 99CAB3CFD34361B6D0551C6D8AEE604316F99758A9C58A96C39AA811E8BA10 791 2E4D21D8F5EFC26920B3F95E6C800D8EBE9914B53144B038BE0E0B43D86479 792 E3CBE623FD148CC90784548C1C7C522C6C71FD4A095B15CBF3EB74C7759493 793 38AC7691A3763C0A3AB97E9E2B439192C49470BF90F292C4A8D336D86780FD 794 DC7DC3C2CC04A6E3AB632788D97D4FDDEE5B117DCF76D91CEA1794FAD91CA1 795 7C9715D83589A00CBB72DD513F6A30E4DB31ACA8DA5D6ECD0E20307D70D6DD 796 0C2D6D3D7962694B5E1B0848 798 Y = 0x 39033C00E1C30FF1A945DD699C516D3BB194FABBB46ADF54A2ED0820FEE0A4 799 DE52128E2126A4393E3040E07D90432B8C19433EC920274E5A7C165DC89AA2 800 C6D77E801A0C7676BC71955A52E74775C57C63B97304C73211C2035BD7B6D1 801 8844A28AC50DD2DA96B257236A6090CCB08D2006BF57AC69EA14ABC5D71BA0 802 6A6BD4093A2EF27C74D5D9189BB2EC865E6321D0DFECDE2D9AC537E8254E98 803 C38AE00BE2554F71FE6EFBBDBE8D7038128957E98C99206998B0B4E578EC47 804 957205C228FAC57B9A1589B8FF2B134980504F56B8A84809B8FF70EFF67520 805 2B255F0724DC0F76F3802D8A42ACC33D349A7FAF249BFBFEB324C3966D2B30 806 6093C32A928A8BEB99AC301D20372E95BB8A3E500778B4651EB8A19B162666 807 8DDFB77D0DF4C1932F1FE63389F3B1F29AE99F34BC39EF0AD04BC3A6A129DE 808 E66E50B6768EDECC529F06FE5F7AD3825E8ECFCB12DB579C40F19D12BF6F60 809 4621F60413DAEB77FE48C136518C57D02A2C6BB596EDFA0DACC127C2FD5FE1 810 9B72580A722307C3F86C0EB1 812 V_U = 0x 490C7CE33DCC3EBE8D0406EEB97CA154882DCBBA0A728F3B870263BCA36 813 9DB6 815 V_S = 0x D70D2CAA821B9D84E29D75EB5E9B2DB038BA1256ECFC35C553832743A6E 816 36F 818 Appendix C. AugPAKE over EC Groups 820 The AugPAKE protocol can be implemented over any elliptic curve 821 groups. The following is such an example. 823 Let p and q be sufficiently large primes, and let m be some positive 824 integer. An elliptic curve E is defined by one of the following two 825 curve equations 827 y^2 = x^3 + a * x + b over the prime field GF(p) or 829 y^2 + x * y = x^3 + a * x^2 + b over the binary field GF(2^m) 831 together with the point at infinity 0_E where x, y, and two 832 coefficients a and b are elements of GF(p) or GF(2^m). Let #E be the 833 number of points on E, and prime q be the order of the desired group. 834 The cofactor k is the value (#E / q) satisfying k = 2^n * q_1 * q_2 835 ... q_t where n = {0,1,2} and every primes q_i > q for i = 1, 2, 836 ..., t. Optionally, k = 2^n. Also, n can be 3 for good performance 837 and security. Let G be a generator for a subgroup of q points on E 838 so that all the subgroup elements are generated by G. The group 839 operation is denoted additively. For example, (X = [x] * G) 840 indicates that an addition computation of G by x times and the 841 resultant value is assigned to X. 843 By using the above elliptic curve groups, the AugPAKE protocol has 844 computational efficiency gains. Specifically, it does not require 845 the order check of elements, received from the counterpart party. 847 The AugPAKE protocol consists of two phases: initialization and 848 actual protocol execution. The initialization phase SHOULD be 849 finished in a secure manner between the user and the server, and it 850 is performed all at once. Whenever the user and the server need to 851 establish a secure channel, they can run the actual protocol 852 execution through an open network (i.e., the Internet) in which an 853 active attacker exists. 855 Initialization 857 U -> S: (U, W) 858 The user U computes W = [w] * G (instead of w, the 859 effective password w' may be used), and transmits W to the 860 server S. The W is registered in the server as the 861 password verifier of user U. Of course, user U just 862 remembers the password w only. 864 Actual Protocol Execution 866 U -> S: (U, X) 867 The user U chooses a random element x from Z_q^* and 868 computes its elliptic curve Diffie-Hellman public value X 869 = [x] * G. The user sends the first message (U, X) to the 870 server S. 872 S -> U: (S, Y) 873 If the received X from user U is not a point on E or [2^n] 874 * X = 0_E, server S MUST terminate the protocol execution. 875 Otherwise, the server chooses a random element y from 876 Z_q^* and computes Y = [y] * (X + ([r] * W)) where r = 877 H'(0x01 | U | S | bn2bin(X)). Then, server S sends the 878 second message (S, Y) to the user U. 880 U -> S: V_U 881 If the received Y from server S is not a point on E or 882 [2^n] * Y = 0_E, user U MUST terminate the protocol 883 execution. Otherwise, the user computes K = [z] * Y where 884 z = 1 / (x + (w * r)) mod q and r = H'(0x01 | U | S | 885 bn2bin(X)). Also, user U generates an authenticator V_U = 886 H(0x02 | U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)). 887 Then, the user sends the third message V_U to the server 888 S. 890 S -> U: V_S 891 If the received V_U from user U is not equal to H(0x02 | U 892 | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)) where K = [y] * 893 G, server S MUST terminate the protocol execution. 894 Otherwise, the server generates an authenticator V_S = 895 H(0x03 | U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)) and a 896 session key SK = H(0x04 | U | S | bn2bin(X) | bn2bin(Y) | 897 bn2bin(K)). Then, server S sends the fourth message V_S 898 to the user U. 900 U: 901 If the received V_S from server S is not equal to H(0x03 | 902 U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)), user U MUST 903 terminate the protocol execution. Otherwise, the user 904 generates a session key SK = H(0x04 | U | S | bn2bin(X) | 905 bn2bin(Y) | bn2bin(K)). 907 Authors' Addresses 909 SeongHan Shin 910 AIST 911 2-4-7 Aomi, Koto-ku 912 Tokyo, Tokyo 135-0064 913 JP 915 Phone: +81-3-3599-8001 916 Email: seonghan.shin@aist.go.jp 918 Kazukuni Kobara 919 AIST 921 Email: kobara_conf-ml@aist.go.jp