idnits 2.17.1 draft-shin-tls-augpake-01.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 (September 04, 2013) is 3859 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 604, but not defined == Missing Reference: 'P' is mentioned on line 824, 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. Shin 3 Internet-Draft K. Kobara 4 Intended status: Standards Track AIST 5 Expires: March 08, 2014 September 04, 2013 7 Augmented Password-Authenticated Key Exchange for Transport Layer 8 Security (TLS) 9 draft-shin-tls-augpake-01 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 March 08, 2014. 42 Copyright Notice 44 Copyright (c) 2013 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 . . . . . . . . . . . . . . . . . . . . . . . . 3 61 2. AugPAKE Specification . . . . . . . . . . . . . . . . . . . . 4 62 2.1. Underlying Group . . . . . . . . . . . . . . . . . . . . 4 63 2.2. Notation . . . . . . . . . . . . . . . . . . . . . . . . 4 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 4. Implementation Consideration . . . . . . . . . . . . . . . . 13 78 5. AugPAKE for TLS . . . . . . . . . . . . . . . . . . . . . . . 13 79 5.1. Specification of AugPAKE Handshake . . . . . . . . . . . 13 80 5.2. Changes from the TLS Handshake Protocol . . . . . . . . . 14 81 5.2.1. Changes to Client Hello Message . . . . . . . . . . . 14 82 5.2.2. Changes to Server Key Exchange Message . . . . . . . 14 83 6. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . 15 84 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 85 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 86 8.1. Normative References . . . . . . . . . . . . . . . . . . 15 87 8.2. Informative References . . . . . . . . . . . . . . . . . 16 88 Appendix A. Features of AugPAKE . . . . . . . . . . . . . . . . 17 89 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18 91 1. Introduction 93 In the real world, many applications such as web mail, Internet 94 banking/shopping/trade require secure channels between participating 95 parties. Such secure channels can be established by using an 96 authenticated key exchange (AKE) protocol, which allows the involving 97 parties to authenticate each other and to generate a temporary 98 session key. The temporary session key is used to protect the 99 subsequent communications between the parties. 101 Until now, password-only AKE (called, PAKE) protocols have attracted 102 much attention because password-only authentication is very 103 convenient to the users. However, it is not trivial to design a 104 secure PAKE protocol due to the existence of off-line dictionary 105 attacks on passwords. These attacks are possible since passwords are 106 chosen from a relatively-small dictionary that allows for an attacker 107 to perform the exhaustive searches. This problem was brought forth 108 by Bellovin and Merritt [BM92], and many following works have been 109 conducted in the literature (see some examples in [IEEEP1363.2]). A 110 PAKE protocol is said to be secure if the best attack an active 111 attacker can take is restricted to the on-line dictionary attacks, 112 which allow to check a guessed password only by interacting with the 113 honest party. 115 An augmented PAKE protocol (e.g., [BM93], [RFC2945], [ISO]) provides 116 extra protection for server compromise in the sense that an attacker, 117 who obtained a password verifier from a server, cannot impersonate 118 the corresponding user without performing off-line dictionary attacks 119 on the password verifier. This additional security is known as 120 "resistance to server compromise". The AugPAKE protocol described in 121 this document is an augmented PAKE which also achieves measurable 122 efficiency over some previous works (SRP [RFC2945] and AMP [ISO]). 123 We believe the following (see [SKI10] for the formal security proof): 124 1) The AugPAKE protocol is secure against passive attacks, active 125 attacks and off-line dictionary attacks (on the obtained messages 126 with passive/active attacks), and 2) It provides resistance to server 127 compromise. At the same time, the AugPAKE protocol has similar 128 computational efficiency to the plain Diffie-Hellman key exchange 129 [DH76] that does not provide authentication by itself. Specifically, 130 the user and the server need to compute 2 and 2.17 modular 131 exponentiations, respectively, in the AugPAKE protocol. After 132 excluding pre-computable costs, the user and the server are required 133 to compute only 1 and 1.17 modular exponentiations, respectively. 134 Compared with SRP [RFC2945] and AMP [ISO], the AugPAKE protocol is 135 more efficient 1) than SRP in terms of the user's computational costs 136 and 2) than AMP in terms of the server's computational costs. 138 Based on the AugPAKE protocol, this document also specifies a new 139 password-only authentication handshake for Transport Layer Security 140 (TLS) protocol [RFC5246]. 142 1.1. Keywords 143 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 144 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 145 document are to be interpreted as described in RFC 2119 [RFC2119]. 147 2. AugPAKE Specification 149 2.1. Underlying Group 151 The AugPAKE protocol can be implemented over the following group. 153 o Let p and q be sufficiently large primes such that q is a divisor 154 of ((p - 1) / 2) and every factors of ((p - 1) / 2) are also 155 primes comparable to q in size. This p is called a "secure" 156 prime. We denote by G a multiplicative subgroup of prime order q 157 over the field GF(p), the integers modulo p. Let g be a generator 158 for the subgroup G so that all the subgroup elements are generated 159 by g. The group operation is denoted multiplicatively (in modulo 160 p). 162 By using a secure prime p, the AugPAKE protocol has computational 163 efficiency gains. Specifically, it does not require the order check 164 of elements, received from the counterpart party. Note that the 165 groups, defined in Discrete Logarithm Cryptography [SP800-56A] and 166 RFC 5114 [RFC5114], are not necessarily the above secure prime 167 groups. 169 Alternatively, one can implement the AugPAKE protocol over the 170 following groups. 172 o Let p and q be sufficiently large primes such that p = (2 * q) + 173 1. This p is called a "safe" prime. We denote by G a 174 multiplicative subgroup of prime order q over the field GF(p), the 175 integers modulo p. Let g be any element of G other than 1. For 176 example, g = h^2 mod p where h is a primitive element. The group 177 operation is denoted multiplicatively (in modulo p). 179 o Let p and q be sufficiently large primes such that q is a divisor 180 of ((p - 1) / 2). We denote by G a multiplicative subgroup of 181 prime order q over the field GF(p), the integers modulo p. Let g 182 be a generator for the subgroup G so that all the subgroup 183 elements are generated by g. The group operation is denoted 184 multiplicatively (in modulo p). If p is not a "secure" prime, the 185 AugPAKE protocol MUST perform the order check of received 186 elements. 188 2.2. Notation 189 The AugPAKE protocol is a two-party protocol where a user and a 190 server authenticate each other and generate a session key. The 191 following notation is used in this document: 193 U 194 The user's identity (e.g., defined in [RFC4282]). It is a string 195 in {0,1}^* where {0,1}^* indicates a set of finite binary 196 strings. 198 S 199 The server's identity. It is a string in {0,1}^*. 201 b = H(a) 202 A binary string a is given as input to a secure one-way hash 203 function H (e.g., SHA-2 family [FIPS180-3]) which produces a 204 fixed-length output b. The hash function H maps {0,1}^* to 205 {0,1}^k where {0,1}^k indicates a set of binary strings of length 206 k and k is a security parameter. 208 b = H'(a) 209 A binary string a is given as input to a secure one-way hash 210 function H' which maps the input a in {0,1}^* to the output b in 211 Z_q^* where Z_q^* is a set of positive integers modulo prime q. 213 a | b 214 It denotes a concatenation of binary strings a and b in {0,1}^*. 216 0x 217 A hexadecimal value is shown preceded by "0x". 219 X * Y mod p 220 It indicates a multiplication of X and Y modulo prime p. 222 X = g^x mod p 223 The g^x indicates a multiplication computation of g by x times. 224 The resultant value modulo prime p is assigned to X. The discrete 225 logarithm problem says that it is computationally hard to compute 226 the discrete logarithm x from X, g and p. 228 w 229 The password remembered by the user. This password may be used 230 as an effective password (instead of itself) in the form of 231 H'(0x00 | U | S | w). 233 W 234 The password verifier registered in the server. This password 235 verifier is computed as follows: W = g^w mod p where the user's 236 password w is used itself, or W = g^w' mod p where the effective 237 password w' = H'(0x00 | U | S | w) is used. 239 bn2bin(X) 240 It indicates a conversion of a multiple precision integer X to 241 the corresponding binary string. If X is an element over GF(p), 242 its binary representation MUST have the same bit length as the 243 binary representation of prime p. 245 U -> S: msg 246 It indicates a message transmission that the user U sends a 247 message msg to the server S. 249 U: 250 It indicates a local computation of user U (without any out-going 251 messages). 253 2.2.1. Password Processing 255 The input password MUST be processed according to the rules of the 256 [RFC4013] profile of [RFC3454]. The password SHALL be considered a 257 "stored string" per [RFC3454] and unassigned code points are 258 therefore prohibited. The output SHALL be the binary representation 259 of the processed UTF-8 character string. Prohibited output and 260 unassigned code points encountered in SASLprep pre-processing SHALL 261 cause a failure of pre-processing and the output SHALL NOT be used 262 with the AugPAKE protocol. 264 The following table shows examples of how various character data is 265 transformed by the rules of the [RFC4013] profile. 267 # Input Output Comments 268 - ----- ------ -------- 269 1 IX IX SOFT HYPHEN mapped to nothing 270 2 user user no transformation 271 3 USER USER case preserved, will not match #2 272 4 a output is NFKC, input in ISO 8859-1 273 5 IX output is NFKC, will match #1 274 6 Error - prohibited character 275 7 Error - bidirectional check 277 2.3. Protocol 279 The AugPAKE protocol consists of two phases: initialization and 280 actual protocol execution. The initialization phase SHOULD be 281 finished in a secure manner between the user and the server, and it 282 is performed all at once. Whenever the user and the server need to 283 establish a secure channel, they can run the actual protocol 284 execution through an open network (i.e., the Internet) in which an 285 active attacker exists. 287 2.3.1. Initialization 289 U -> S: (U, W) 290 The user U computes W = g^w mod p (instead of w, the 291 effective password w' may be used), and transmits W to the 292 server S. The W is registered in the server as the password 293 verifier of user U. Of course, user U just remembers the 294 password w only. 296 If resistance to server compromise is not necessary, the server can 297 store w' instead of W. In either case, server S SHOULD NOT store any 298 plaintext passwords. 300 As noted above, this phase SHOULD be performed securely and all at 301 once. 303 2.3.2. Actual Protocol Execution 305 The actual protocol execution of the AugPAKE protocol allows the user 306 and the server to share an authenticated session key through an open 307 network (see Figure 1). 309 +-----------------+ +------------------+ 310 | User U | | Server S (U,W) | 311 | | (U, X) | | 312 | |----------------------------->| | 313 | | | | 314 | | (S, Y) | | 315 | |<-----------------------------| | 316 | | | | 317 | | V_U | | 318 | |----------------------------->| | 319 | | | | 320 | | V_S | | 321 | |<-----------------------------| | 322 | | | | 323 +-----------------+ +------------------+ 325 Figure 1: Actual Protocol Execution of AugPAKE 327 U -> S: (U, X) 328 The user U chooses a random element x from Z_q^* and computes 329 its Diffie-Hellman public value X = g^x mod p. The user sends 330 the first message (U, X) to the server S. 332 S -> U: (S, Y) 333 If the received X from user U is 0, 1 or -1 (mod p), server S 334 MUST terminate the protocol execution. Otherwise, the server 335 chooses a random element y from Z_q^* and computes Y = (X * 336 (W^r))^y mod p where r = H'(0x01 | U | S | bn2bin(X)). Note 337 that X^y * g^(w * r * y) mod p can be computed from y and (w 338 * r * y) efficiently using Shamir's trick [MOV97]. Then, 339 server S sends the second message (S, Y) to the user U. 341 U -> S: V_U 342 If the received Y from server S is 0, 1 or -1 (mod p), user U 343 MUST terminate the protocol execution. Otherwise, the user 344 computes K = Y^z mod p where z = 1 / (x + (w * r)) mod q and 345 r = H'(0x01 | U | S | bn2bin(X)). Also, user U generates an 346 authenticator V_U = H(0x02 | U | S | bn2bin(X) | bn2bin(Y) | 347 bn2bin(K)). Then, the user sends the third message V_U to 348 the server S. 350 S -> U: V_S 351 If the received V_U from user U is not equal to H(0x02 | U | 352 S | bn2bin(X) | bn2bin(Y) | bn2bin(K)) where K = g^y mod p, 353 server S MUST terminate the protocol execution. Otherwise, 354 the server generates an authenticator V_S = H(0x03 | U | S | 355 bn2bin(X) | bn2bin(Y) | bn2bin(K)) and a session key SK = 356 H(0x04 | U | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)). Then, 357 server S sends the fourth message V_S to the user U. 359 U: 360 If the received V_S from server S is not equal to H(0x03 | U 361 | S | bn2bin(X) | bn2bin(Y) | bn2bin(K)), user U MUST 362 terminate the protocol execution. Otherwise, the user 363 generates a session key SK = H(0x04 | U | S | bn2bin(X) | 364 bn2bin(Y) | bn2bin(K)). 366 In the actual protocol execution, the sequential order of message 367 exchanges is very important in order to avoid any possible attacks. 368 For example, if the server S sends the second message (S, Y) and the 369 fourth message V_S together, any attacker can easily derive the 370 correct password w with off-line dictionary attacks. 372 The session key SK, shared only if the user and the server 373 authenticate each other successfully, MAY be generated by using a key 374 derivation function (KDF) [SP800-108]. After generating SK, the user 375 and the server MUST delete all the internal states (e.g., Diffie- 376 Hellman exponents x and y) from memory. 378 For the formal proof [SKI10] of the AugPAKE protocol, we need to 379 change slightly the computation of Y (in the above S -> U: (S, Y)) 380 and K (in the above S -> U: V_S) as follows: Y = (X * (W^r))^y' and K 381 = g^y' where y' = H'(0x05 | bn2bin(y)). 383 3. Security Considerations 385 This section shows why the AugPAKE protocol (i.e., the actual 386 protocol execution) is secure against passive attacks, active attacks 387 and off-line dictionary attacks, and also provides resistance to 388 server compromise. 390 3.1. General Assumptions 392 o An attacker is computationally-bounded. 394 o Any hash functions, used in the AugPAKE protocol, are secure in 395 terms of pre-image resistance (one-wayness), second pre-image 396 resistance and collision resistance. 398 3.2. Security against Passive Attacks 400 An augmented PAKE protocol is said to be secure against passive 401 attacks in the sense that an attacker, who eavesdrops the exchanged 402 messages, cannot compute an authenticated session key (shared between 403 the honest parties in the protocol). 405 In the AugPAKE protocol, an attacker can get the messages (U, X), (S, 406 Y), V_U, V_S by eavesdropping, and then wants to compute the session 407 key SK. That is, the attacker's goal is to derive the correct K from 408 the obtained messages X and Y because the hash functions are secure 409 and the only secret in the computation of SK is K = g^y mod p. Note 410 that 412 X = g^x mod p and 414 Y = (X * (W^r))^y = X^y * W^(r * y) = X^y * (g^y)^t = X^y * K^t 416 hold where t = w * r mod q. Though t is determined from possible 417 password candidates and X, the only way for the attacker to extract K 418 from X and Y is to compute X^y. However, the probability for the 419 attacker to compute X^y is negligible in the security parameter for 420 the underlying groups since both x and y are random elements chosen 421 from Z_q^*. Therefore, the AugPAKE protocol is secure against passive 422 attacks. 424 3.3. Security against Active Attacks 426 An augmented PAKE protocol is said to be secure against active 427 attacks in the sense that an attacker, who completely controls the 428 exchanged messages, cannot compute an authenticated session key 429 (shared with the honest party in the protocol) with the probability 430 better than that of on-line dictionary attacks. In other words, the 431 probability for an active attacker to compute the session key is 432 restricted by the on-line dictioinary attacks where it grows linearly 433 to the number of interactions with the honest party. 435 In the AugPAKE protocol, the user (resp., the server) computes the 436 session key SK only if the received authenticator V_S (resp., V_U) is 437 valid. There are three cases to be considered in the active attacks. 439 3.3.1. Impersonation Attacks on User U 441 When an attacker impersonates the user U, the attacker can compute 442 the same SK (to be shared with the server S) only if the 443 authenticator V_U is valid. For a valid authenticator V_U, the 444 attacker has to compute the correct K from X and Y because the hash 445 functions are secure. In this impersonation attack, the attacker of 446 course knows the discrete logarithm x of X and guesses a password w'' 447 from the password dictionary. So, the probability for the attacker 448 to compute the correct K is bounded by the probability of w = w''. 449 That is, this impersonation attack is restricted by the on-line 450 dictionary attacks where the attacker can try a guessed password 451 communicating with the honest server S. Therefore, the AugPAKE 452 protocol is secure against impersonation attacks on user U. 454 3.3.2. Impersonation Attacks on Server S 456 When an attacker impersonates the server S, the attacker can compute 457 the same SK (to be shared with the user U) only if the authenticator 458 V_S is valid. For a valid authenticator V_S, the attacker has to 459 compute the correct K from X and Y because the hash functions are 460 secure. In this impersonation attack, the attacker chooses a random 461 element y and guesses a password w'' from the password dictionary so 462 that 464 Y = (X * (W'^r))^y = X^y * W'^(r * y) = X^y * (g^y)^t' 466 where t' = w'' * r mod q. The probability for the attacker to compute 467 the correct K is bounded by the probability of w = w''. Also, the 468 attacker knows whether the guessed password is equal to w or not by 469 seeing the received authenticator V_U. However, when w is not equal 470 to w'', the probability for the attacker to compute the correct K is 471 negligible in the security parameter for the underlying groups since 472 the attacker has to guess the discrete logarithm x (chosen by user U) 473 as well. That is, this impersonation attack is restricted by the on- 474 line dictionary attacks where the attacker can try a guessed password 475 communicating with the honest user U. Therefore, the AugPAKE protocol 476 is secure against impersonation attacks on server S. 478 3.3.3. Man-in-the-Middle Attacks 480 When an attacker performs the man-in-the-middle attack, the attacker 481 can compute the same SK (to be shared with the user U or the server 482 S) only if one of the authenticators V_U, V_S is valid. Note that if 483 the attacker relays the exchanged messages honestly, it corresponds 484 to the passive attacks. In order to generate a valid authenticator 485 V_U or V_S, the attacker has to compute the correct K from X and Y 486 because the hash functions are secure. So, the attacker is in the 487 same situation as discussed above. Though the attacker can test two 488 passwords (one with user U and the other with server S), it does not 489 change the fact that this attack is restricted by the on-line 490 dictionary attacks where the attacker can try a guessed password 491 communicating with the honest party. Therefore, the AugPAKE protocol 492 is also secure against man-in-the-middle attacks. 494 3.4. Security against Off-line Dictionary Attacks 496 An augmented PAKE protocol is said to be secure against off-line 497 dictionary attacks in the sense that an attacker, who completely 498 controls the exchanged messages, cannot reduce the possible password 499 candidates better than on-line dictionary attacks. Note that, in the 500 on-line dictionary attacks, an attacker can test one guessed password 501 by running the protocol execution (i.e., communicating with the 502 honest party). 504 As discussed in Section 3.2, an attacker in the passive attacks does 505 not compute X^y (and the correct K = g^y mod p) from the obtained 506 messages X, Y. This security analysis also indicates that, even if 507 the attacker can guess a password, the K is derived independently 508 from the guessed password. Next, we consider an active attacker 509 whose main goal is to perform the off-line dictionary attacks in the 510 AugPAKE protocol. As in Section 3.3, the attacker can 1) test one 511 guessed password by impersonating the user U or the server S, or 2) 512 test two guessed passwords by impersonating the server S (to the 513 honest user U) and impersonating the user U (to the honest server S) 514 in the man-in-the-middle attacks. Whenever the honest party receives 515 an invalid authenticator, the party terminates the actual protocol 516 execution without sending any message. In fact, this is important to 517 prevent an attacker from testing more than one password in the active 518 attacks. Since passive attacks and active attacks cannot remove the 519 possible password candidates efficiently than on-line dictionary 520 attacks, the AugPAKE protocol is secure against off-line dictionary 521 attacks. 523 3.5. Resistance to Server Compromise 525 We consider an attacker who has obtained a (user's) password verifier 526 from a server. In the (augmented) PAKE protocols, there are two 527 limitations [BJKMRSW00]: 1) the attacker can find out the correct 528 password from the password verifier with the off-line dictionary 529 attacks because the verifier has the same entropy as the password; 530 and 2) if the attacker impersonates the server with the password 531 verifier, this attack is always possible because the attacker has 532 enough information to simulate the server. An augmented PAKE 533 protocol is said to provide resistance to server compromise in the 534 sense that the attacker cannot impersonate the user without 535 performing off-line dictionary attacks on the password verifier. 537 In order to show resistance to server compromise in the AugPAKE 538 protocol, we consider an attacker who has obtained the password 539 verifier W and then tries to impersonate the user U without off-line 540 dictionary attacks on W. As a general attack, the attacker chooses 541 two random elements c and d from Z_q^*, and computes 543 X = (g^c) * (W^d) mod p 545 and sends the first message (U, X) to the server S. In order to 546 impersonate user U successfully, the attacker has to compute the 547 correct K = g^y mod p where y is randomly chosen by server S. After 548 receiving Y from the server, the attacker's goal is to find out a 549 value e satisfying Y^e = K mod p. That is, 551 log_g (Y^e) = log_g K mod q 553 (c + (w * d) + (w * r)) * y * e = y mod q 555 (c + w * (d + r)) * e = 1 mod q 557 where log_g K indicates the logarithm of K to the base g. Since there 558 is no off-line dictionary attacks on W, the above solution is that e 559 = 1 / c mod q and d = -r mod q. However, the latter is not possible 560 since r is determined by X (i.e., r = H'(0x01 | U | S | bn2bin(X))) 561 and H' is a secure hash function. Therefore, the AugPAKE protocol 562 provides resistance to server compromise. 564 4. Implementation Consideration 566 As discussed in Section 3, the AugPAKE protocol is secure against 567 passive attacks, active attacks and off-line dictionary attacks, and 568 provides resistance to server compromise. However, an attacker in 569 the on-line dictionary attacks can check whether one password 570 (guessed from the password dictionary) is correct or not by 571 interacting with the honest party. Let N be a dictionary size of 572 passwords. Certainly, the attacker's success probability grows with 573 the probability of (I / N) where I is the number of interactions with 574 the honest party. In order to provide a reasonable security margin, 575 implementation SHOULD take a countermeasure to the on-line dictionary 576 attacks. For example, it would take about 90 years to test 2^(25.5) 577 passwords with one minute lock-out for 3 failed password guesses (see 578 Appendix A in [SP800-63]). 580 5. AugPAKE for TLS 582 5.1. Specification of AugPAKE Handshake 584 The TLS Handshake Protocol [RFC5246], which operates on top of the 585 TLS record layer, is responsible for negotiating a session and 586 agreeing upon security parameters (e.g., PreMasterSecret) of the 587 session state. When protecting subsequent application data, the 588 agreed security parameters are used by the record layer. The AugPAKE 589 protocol, described in Section 2, can be easily integrated into the 590 TLS Handshake Protocol as a password-only mutual authentication by 591 modifying some messages (see Figure 2). This integrated protocol 592 preserves the TLS Handshake Protocol structure and its security 593 guarantees. 595 Client Server 597 ClientHello: name, X --------> 598 ServerHello 599 ServerKeyExchange: Y 600 <-------- ServerHelloDone 601 ClientKeyExchange 602 [ChangeCipherSpec] 603 Finished: V_U --------> 604 [ChangeCipherSpec] 605 <-------- Finished: V_S 607 Application Data <-------> Application Data 609 Figure 2: Plugging AugPAKE into TLS Handshake Protocol 611 5.2. Changes from the TLS Handshake Protocol 613 The changes from the TLS Handshake Protocol are summarized as 614 follows: 616 o The X and the TLS client name (it is preferable to use a hashed 617 value for privacy protection) are included in the "ClientHello" 618 message. 620 o The Y is included in the "ServerKeyExchange" message. 622 o The V_U (resp., V_S) is inclued in the TLS client's (resp., 623 server's) "Finished" message. 625 o The PreMasterSecret in the TLS Handshake Protocol corresponds to K 626 of the AugPAKE protocol in Section 2. The leading bytes of K that 627 contain all zero bits are stripped before it is used as the 628 pre_master_secret. 630 5.2.1. Changes to Client Hello Message 632 The extension of the "ClientHello" message will be 634 enum { AugPAKE (TBD) } ExtensionType; 636 struct { 638 opaque name<1..2^8-1>; 640 opaque X<1..2^16-1>; 642 } Extension; 644 where the extension data field of the AugPAKE extension SHALL contain 645 a "name" to be used to identify the TLS client and the client's 646 Diffie-Hellman public value X. 648 If the TLS server does not find a verifier corresponding to the 649 "name" in the extension of the "ClientHello" message, the server 650 SHOULD keep running the protocol by choosing a random element Y and 651 then rejects the TLS client's "Finished" message with a 652 bad_record_mac alert. Alternatively, the TLS server MAY terminate 653 the protocol if a verifier corresponding to the "name" in the 654 extension of the "ClientHello" message is not found. 656 5.2.2. Changes to Server Key Exchange Message 657 The "ServerKeyExchange" message contains the server's computed value 658 Y (see Section 2). Also, a new value is added to the 659 KeyExchangeAlgorithm to indicate its use of AugPAKE. 661 enum { augpake } KeyExchangeAlgorithm; 663 struct { opaque Y<1..2^16-1>; } ServerAugPAKEParams; 665 6. Acknowledgement 667 The AugPAKE protocol described in Section 2 has also been specified 668 as a password-only authentication method for IKEv2. 670 7. IANA Considerations 672 This document requests IANA to assign a value. 674 IANA SHALL assign a value for "AugPAKE" from the TLS ExtensionType 675 Registry defined in [RFC5246] with the method name of "AugPAKE". 677 8. References 679 8.1. Normative References 681 [FIPS180-3] 682 Information Technology Laboratory, ., "Secure Hash 683 Standard (SHS)", NIST FIPS Publication 180-3, October 684 2008, . 687 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 688 Requirement Levels", BCP 14, RFC 2119, March 1997. 690 [RFC3454] Hoffman, P. and M. Blanchet, "Preparation of 691 Internationalized Strings ("stringprep")", RFC 3454, 692 December 2002. 694 [RFC4013] Zeilenga, K., "SASLprep: Stringprep Profile for User Names 695 and Passwords", RFC 4013, February 2005. 697 [RFC4282] Aboba, B., Beadles, M., Arkko, J., and P. Eronen, "The 698 Network Access Identifier", RFC 4282, December 2005. 700 [RFC5246] Dierks, T., Rescorla, E., , , "The Transport Layer 701 Security (TLS) Protocol Version 1.2", RFC 5246, August 702 2008. 704 [SP800-108] 705 Chen, L., "Recommendation for Key Derivation Using 706 Pseudorandom Functions (Revised)", NIST Special 707 Publication 800-108, October 2009, . 710 8.2. Informative References 712 [BJKMRSW00] 713 Bellare, M., Jablon, D., Krawczyk, H., MacKenzie, P., 714 Rogaway, P., Swaminathan, R., and T. Wu, "Proposal for 715 P1363 Study Group on Password-Based Authenticated-Key- 716 Exchange Methods", IEEE P1363.2: Password-Based Public-Key 717 Cryptography , Submissions to IEEE P1363.2 , February 718 2000, . 721 [BM92] Bellovin, S. and M. Merritt, "Encrypted Key Exchange: 722 Password-based Protocols Secure against Dictionary 723 Attacks", Proceedings of the IEEE Symposium on Security 724 and Privacy , IEEE Computer Society , 1992. 726 [BM93] Bellovin, S. and M. Merritt, "Augmented Encrypted Key 727 Exchange: A Password-based Protocol Secure against 728 Dictionary Attacks and Password File Compromise", 729 Proceedings of the 1st ACM Conference on Computer and 730 Communication Security , ACM Press , 1993. 732 [DH76] Diffie, W. and M. Hellman, "New Directions in 733 Cryptography", IEEE Transactions on Information Theory 734 Volume IT-22, Number 6, 1976. 736 [IEEEP1363.2] 737 IEEE P1363.2, . , "Password-Based Public-Key 738 Cryptography", Submissions to IEEE P1363.2 , , . 741 [ISO] ISO/IEC JTC 1/SC 27 11770-4, . , "Information technology 742 -- Security techniques -- Key management -- Part 4: 743 Mechanisms based on weak secrets", May 2006, . 747 [MOV97] Menezes, A., Oorschot, P., and S. Vanstone, "Simultaneous 748 Multiple Exponentiation", in Handbook of Applied 749 Cryptography , CRC Press , 1997. 751 [RFC2945] Wu, T. , "The SRP Authentication and Key Exchange System", 752 RFC 2945, September 2000. 754 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman 755 Groups for Use with IETF Standards", RFC 5114, January 756 2008. 758 [SKI10] Shin, S., Kobara, K., and H. Imai, "Security Proof of 759 AugPAKE", Cryptology ePrint Archive: Report 2010/334, June 760 2010, . 762 [SP800-56A] 763 Barker, E., Johnson, D., and M. Smid, "Recommendation for 764 Pair-Wise Key Establishment Schemes Using Discrete 765 Logarithm Cryptography (Revised)", NIST Special 766 Publication 800-56A, March 2007, . 770 [SP800-63] 771 Burr, W., Dodson, D., and W. Polk, "Electronic 772 Authentication Guideline", NIST Special Publication 800-63 773 Version 1.0.2, April 2006, . 776 Appendix A. Features of AugPAKE 778 Below are some features of the AugPAKE protocol. 780 Security: 782 AugPAKE is zero knowledge (password) proof. It is secure against 783 passive/active/off-line dictionary attacks. It is also resistant 784 to server-compromise impersonation attacks. 786 AugPAKE provides Perfect Forward Secrecy (PFS) and is secure 787 against Denning-Sacco attack. 789 Any cryptographically secure Diffie-Hellman groups can be used. 791 The formal security proof of AugPAKE can be found at [SKI10]. 793 AugPAKE can be easily used with strong credentials. 795 In the case of server compromise, an attacker has to perform off- 796 line dictionary attacks while computing modular exponentiation 797 with a password candidate. 799 Intellectual Property: 801 AugPAKE was publicly disclosed on Oct. 2008. 803 AIST applied for a patent in Japan on July 10, 2008. AIST would 804 provide royal-free license of AugPAKE. 806 IPR disclosure (see https://datatracker.ietf.org/ipr/2037/) 808 Miscellaneous: 810 The user needs to compute only 2 modular exponentiation 811 computations while the server needs to compute 2.17 modular 812 exponentiation computations. AugPAKE needs to exchange 2 group 813 elements and 2 hash values. This is almost the same computation/ 814 communication costs as the plain Diffie-Hellman key exchange. If 815 we use a large (e.g., 2048/3072-bits) parent group, the hash size 816 would be relatively small. 818 AugPAKE has the same performance for any type of secret. 820 Internationalization of character-based passwords can be 821 supported. 823 AugPAKE can be implemented over any ECP (Elliptic Curve Group over 824 GF[P]), EC2N (Elliptic Curve Group over GF[2^N]), and MODP 825 (Modular Exponentiation Group) groups. 827 AugPAKE has request/response nature. 829 No Trusted Third Party (TTP) and clock synchronization 831 No additional primitive (e.g., Full Domain Hash (FDH) and/or ideal 832 cipher) is needed. 834 Easy implementation. We already implemented AugPAKE and have been 835 testing in AIST. 837 Authors' Addresses 839 SeongHan Shin 840 AIST 841 Central 2, 1-1-1, Umezono 842 Tsukuba, Ibaraki 305-8568 843 JP 845 Phone: +81 29-861-5284 846 Email: seonghan.shin@aist.go.jp 847 Kazukuni Kobara 848 AIST 850 Email: kobara_conf-ml@aist.go.jp