idnits 2.17.1 draft-hao-jpake-02.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 doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (January 26, 2016) is 3007 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group F. Hao, Ed. 3 Internet-Draft Newcastle University (UK) 4 Intended status: Informational January 26, 2016 5 Expires: July 29, 2016 7 J-PAKE: Password Authenticated Key Exchange by Juggling 8 draft-hao-jpake-02 10 Abstract 12 This document specifies a Password Authenticated Key Exchange by 13 Juggling (J-PAKE) protocol. This protocol allows the establishment 14 of a secure end-to-end communication channel between two remote 15 parties over an insecure network solely based on a shared password, 16 without requiring a Public Key Infrastructure (PKI) or any trusted 17 third party. 19 Status of This Memo 21 This Internet-Draft is submitted in full conformance with the 22 provisions of BCP 78 and BCP 79. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF). Note that other groups may also distribute 26 working documents as Internet-Drafts. The list of current Internet- 27 Drafts is at http://datatracker.ietf.org/drafts/current/. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 This Internet-Draft will expire on July 29, 2016. 36 Copyright Notice 38 Copyright (c) 2016 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (http://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with respect 46 to this document. Code Components extracted from this document must 47 include Simplified BSD License text as described in Section 4.e of 48 the Trust Legal Provisions and are provided without warranty as 49 described in the Simplified BSD License. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 54 1.1. Requirements language . . . . . . . . . . . . . . . . . . 3 55 1.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 3 56 2. J-PAKE Protocol . . . . . . . . . . . . . . . . . . . . . . . 4 57 2.1. Protocol setup . . . . . . . . . . . . . . . . . . . . . 4 58 2.2. Two-round key exchange . . . . . . . . . . . . . . . . . 4 59 2.3. Three-pass variant . . . . . . . . . . . . . . . . . . . 6 60 2.4. Key confirmation . . . . . . . . . . . . . . . . . . . . 6 61 2.5. Computational cost . . . . . . . . . . . . . . . . . . . 7 62 3. Security Considerations . . . . . . . . . . . . . . . . . . . 8 63 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 64 5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9 65 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 66 6.1. Normative References . . . . . . . . . . . . . . . . . . 9 67 6.2. Informative References . . . . . . . . . . . . . . . . . 10 68 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 11 70 1. Introduction 72 Password-Authenticated Key Exchange (PAKE) is a technique that aims 73 to establish secure communication between two remote parties solely 74 based on their shared password, without relying on a Public Key 75 Infrastructure or any trusted third party [BM92]. The first PAKE 76 protocol, called EKE, was proposed by Steven Bellovin and Michael 77 Merrit in 1992 [BM92]. Other well-known PAKE protocols include SPEKE 78 (by David Jablon in 1996) [Jab96] and SRP (by Tom Wu in 1998) [Wu98]. 79 SRP has been revised several times to address reported security and 80 efficiency issues. In particular, the version 6 of SRP, commonly 81 known as SRP-6, is specified in [RFC5054]. 83 This document specifies a PAKE protocol called Password Authenticated 84 Key Exchange by Juggling (J-PAKE), which was designed by Feng Hao and 85 Peter Ryan in 2008 [HR08]. 87 There are a few factors that may be considered in favor of J-PAKE 88 over others. First, J-PAKE has security proofs, while equivalent 89 proofs are lacking in EKE, SPEKE and SRP-6. Second, J-PAKE is not 90 patented. It follows a completely different design approach from all 91 other PAKE protocols, and is built upon a well-established Zero 92 Knowledge Proof (ZKP) primitive: Schnorr NIZK proof [I-D-Schnorr]. 93 Third, J-PAKE is efficient. It adopts novel engineering techniques 94 to optimize the use of ZKP so that overall the protocol is 95 sufficiently efficient for practical use. Fourth, J-PAKE is designed 96 to work generically in both the finite field and elliptic curve 97 setting (i.e., DSA and ECDSA-like groups). Unlike SPEKE, it does not 98 require any extra primitive to hash passwords onto a designated 99 elliptic curve. Finally, J-PAKE has been used in real-world 100 applications at a relatively large scale, e.g., Firefox sync, Pale 101 moon browser and Google Nest products; has been included into widely 102 distributed open source libraries such as OpenSSL, Network Security 103 Services (NSS) and the Bouncy Castle; since 2015, has been included 104 into Thread as a standard key agreement mechanism for IoT (Internet 105 of Things) applications; and currently is being standardized by ISO/ 106 IEC 11770-4. 108 1.1. Requirements language 110 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 111 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 112 document are to be interpreted as described in RFC 2119 [RFC2119]. 114 1.2. Notations 116 The following notations are used in this document: 118 o Alice: the assumed identity of the first party in the protocol 120 o Bob: the assumed identity of the second party in the protocol 122 o s: a low-entropy secret shared between Alice and Bob 124 o p: a large prime 126 o q: a large prime divisor of p-1 128 o Zp*: a multiplicative group of integers modulo p 130 o Gq: a subgroup of Zp* with primer order q 132 o g: a generator of Gq 134 o g^x: g raised to the power of x 136 o a mod b: a modulo b 138 o a * b: a multiplied by b 140 o a || b: concatenation of a and b 142 o H: a secure one-way hash function 143 o KDF(a): Key Derivation Function with input a 145 o HMAC(MacKey, MacData): HMAC function with MacKey as the key and 146 MacData as the input data 148 2. J-PAKE Protocol 150 2.1. Protocol setup 152 The J-PAKE protocol uses exactly the same group setting as DSA (or 153 ECDSA). For simplicity, this document will only describe the J-PAKE 154 protocol in the DSA-like group setting. The protocol works basically 155 the same in the ECDSA-like group setting, except that the underlying 156 multiplicative group over a finite field is replaced by an additive 157 group over an elliptic curve. 159 Let Gq denote a subgroup of Zp* with prime order q, in which the 160 Decisional Diffie-Hellman problem (DDH) is intractable. The p and q 161 are large primes and q divides p-1. Let g be a generator in Gq. Any 162 non-identity element in Gq can be a generator. The two communicating 163 parties, Alice and Bob, both agree on (p, q, g). Values of (p, q, 164 g), as defined by NIST, can be found in the appendix of 165 [I-D-Schnorr]. [[Q1:: The reference is an accompanying internet 166 draft submission to IETF and it needs to be updated once it is 167 accepted by IETF. --Hao]] 169 Let s be the shared secret between Alice and Bob. The secret may be a 170 password, a hash of the password or any other derivative from a 171 password. This does not make any difference to the protocol. The 172 only assumptions are that s has low-entropy and that the value of s 173 falls within [1, q-1]. (Note that s must not be 0 for any non-empty 174 secret.) 176 2.2. Two-round key exchange 178 Round 1: Alice selects x1 uniformly at random from [0, q-1] and x2 179 from [1, q-1]. Similarly, Bob selects x3 uniformly at random from 180 [0, q-1] and x4 from [1, q-1]. 182 o Alice -> Bob: g^{x1} mod p, g^{x2} mod p and knowledge proofs for 183 x1 and x2 185 o Bob -> Alice: g^{x3} mod p, g^{x4} mod p and knowledge proofs for 186 x3 and x4 188 In this round, the sender must demonstrate the knowledge of the 189 ephemeral private keys. A suitable technique is to use the Schnorr 190 NIZK proof [I-D-Schnorr]. As an example, suppose one wishes to prove 191 the knowledge of the exponent for X = g^x mod p. The generated 192 Schnorr NIZK proof will contain: {UserID, V = g^v mod p, r = v - x * 193 h mod q} where UserID is the unique identifier for the prover, v is a 194 number chosen uniformly at random from [0, q-1] and h = H(g || V || 195 X || UserID). The "uniqueness" of UserID is defined from the user's 196 perspective -- for example, if Alice communicates with several 197 parties, she shall associate a unique identity with each party. Upon 198 receiving a Schnorr NIZK proof, Alice shall check the prover's UserID 199 is a valid identity and is different from her own identity. During 200 the key exchange process using J-PAKE, each party shall ensure that 201 the other party has been consistently using the same identity 202 throughout the protocol execution. Details about the Schnorr NIZK 203 proof, including the generation and the verification procedures, can 204 be found in [I-D-Schnorr]. 206 When this round finishes, Alice verifies the received knowledge 207 proofs as specified in [I-D-Schnorr] and also checks that g^{x4} != 1 208 mod p. Similarly, Bob verifies the received knowledge proofs and 209 also checks that g^{x2} != 1 mod p. 211 Round 2: 213 o Alice -> Bob: A=g^{(x1+x3+x4)*x2*s} mod p and a knowledge proof 214 for (x2*s) 216 o Bob -> Alice: B=g^{(x1+x2+x3)*x4*s} mod p and a knowledge proof 217 for (x4*s) 219 In this round, the Schnorr NIZK proof is computed in the same way as 220 in the previous round except that the generator is different. For 221 Alice, the generator used is g^(x1+x3+x4) instead of g; for Bob, the 222 generator is g^(x1+x2+x3) instead of g. Since any non-identity 223 element in Gq can be used as a generator, Alice and Bob just need to 224 ensure g^(x1+x3+x4) != 1 mod p and g^(x1+x2+x3) != 1 mod p. With 225 overwhelming probability, these inequalities are statistically 226 guaranteed even when the user is communicating with an adversary 227 (i.e., in an active attack). Nonetheless, for absolute guarantee, 228 the receiving party may wish to explicitly check if these 229 inequalities hold, and the cost of doing that is negligible. 231 When the second round finishes, Alice and Bob verify the received 232 knowledge proofs and then compute the key material K as follows: 234 o Alice computes K = (B/g^{x2*x4*s})^{x2} mod p = 235 g^{(x1+x3)*x2*x4*s} mod p 237 o Bob computes K = (A/g^{x2*x4*s})^{x4} mod p = g^{(x1+x3)*x2*x4*s} 238 mod p 240 With the same keying material K, both parties can derive a common 241 session key k using a Key Derivation Function (KDF). If the 242 subsequent secure communication uses a symmetric cipher in an 243 authenticated mode (say AES-GCM), then one key is sufficient, i.e., k 244 = KDF(K). Otherwise, the session key should comprise an encryption 245 key (for confidentiality) and a MAC key (for integrity), i.e., k = 246 k_enc || k_mac, where k_enc = KDF(K || "JPAKE_ENC") and k_mac = 247 KDF(K || "JPAKE_MAC"). The exact choice of the KDF is left to 248 specific applications to define. (In many cases, the KDF can simply 249 be a cryptographic hash function, e.g., SHA-256.) 251 2.3. Three-pass variant 253 The two-round J-PAKE protocol is completely symmetric, which 254 significantly simplifies the security analysis. In practice, one 255 party normally initiates the communication and the other party 256 responds. In that case, the protocol will be completed in three 257 passes instead of two rounds. The two-round J-PAKE protocol can be 258 trivially changed to three passes without losing security. Assume 259 Alice initiates the key exchange. The three-pass variant works as 260 follows: 262 1. Alice -> Bob: g^{x1} mod p, g^{x2} mod p, knowledge proofs for x1 263 and x2. 265 2. Bob -> Alice: g^{x3} mod p, g^{x4} mod p, B=g^{(x1+x2+x3)*x4*s 266 mod p, knowledge proofs for x3, x4, and x4*s. 268 3. Alice -> Bob: A=g^{(x1+x3+x4)*x2*s} mod p and a knowledge proof 269 for x2*s. 271 Both parties compute the session keys in exactly the same way as 272 before. 274 2.4. Key confirmation 276 The two-round J-PAKE protocol (or three-pass variant) provides 277 cryptographic guarantee that only the authenticated party who used 278 the same password at the other end is able to compute the same 279 session key. So far the authentication is only implicit. 281 For achieving explicit authentication, an additional key confirmation 282 procedure should be performed. This is to ensure that both parties 283 have actually obtained the same session key. 285 There are several explicit key confirmation methods available. They 286 are generically applicable to all key exchange protocols, not just 287 J-PAKE. In general, it is recommended to use a different key from 288 the session key for key confirmation, say using k' = KDF(K || 289 "JPAKE_KC"). The advantage of using a different key for key 290 confirmation is that the session key remains indistinguishable from 291 random after the key confirmation process (although this perceived 292 advantage is actually subtle and only theoretical). Two key- 293 confirmation methods are presented here. 295 The first method is based on the one used in the SPEKE protocol 296 [Jab96]. Suppose Alice initiates the key confirmation. Alice sends 297 to Bob H(H(k')), which Bob will verify. If the verification is 298 successful, Bob sends back to Alice H(k'), which Alice will verify. 299 This key confirmation procedure needs to be completed in two rounds, 300 as shown below. 302 1. Alice -> Bob: H(H(k')) 304 2. Bob -> Alice: H(k') 306 The second method is based on the unilateral key confirmation scheme 307 specified in NIST SP 800-56A Revision 1 [BJS07]. Alice and Bob send 308 to each other a MAC tag, which they will verify accordingly. This 309 key confirmation procedure can be completed in one round, as shown 310 below. 312 o Alice -> Bob: MacTagAlice = HMAC(k', "KC_1_U || Alice || Bob || 313 g^x1 || g^x2 || g^x3 || g^x4") 315 o Bob -> Alice: MacTagBob = HMAC(k', "KC_1_U || Bob || Alice || 316 g^x3 || g^x4 || g^x1 || g^x2") 318 The second method assumes an additional secure MAC function (HMAC) 319 and is slightly more complex than the first method; however, it can 320 be completed within one round and it preserves the overall symmetry 321 of the protocol implementation. This may prove desirable in some 322 applications. 324 2.5. Computational cost 326 In J-PAKE, the modular exponentiations are the predominant factors in 327 the computation. Hence, the computational cost is estimated based on 328 counting the number of such modular exponentiations. Note that it 329 takes one exponentiation to generate a Schnorr NIZK proof and two to 330 verify it [I-D-Schnorr]. For Alice, she has to perform 8 331 exponentiations in the first round, 4 in the second round, and 2 in 332 the final computation of the session key. Hence, that is 14 modular 333 exponentiations in total. Based on the symmetry, the computational 334 cost for Bob is exactly the same. 336 3. Security Considerations 338 A PAKE protocol is designed to provide two functions in one protocol 339 execution. The first one is to provide zero-knowledge authentication 340 of a password. It is called "zero knowledge" because at the end of 341 the protocol, the two communicating parties will learn nothing more 342 than one bit information: whether the passwords supplied at two ends 343 are equal. Therefore, a PAKE protocol is naturally resistant against 344 phishing attacks. The second function is to provide session key 345 establishment if the two passwords are equal. The session key will 346 be used to protect the confidentiality and integrity of the 347 subsequent communication. 349 More concretely, a secure PAKE protocol shall satisfy the following 350 security requirements [HR10]. 352 1. Off-line dictionary attack resistance: It does not leak any 353 information that allows a passive/active attacker to perform off- 354 line exhaustive search of the password. 356 2. Forward secrecy: It produces session keys that remain secure even 357 when the password is later disclosed. 359 3. Known-key security: It prevents a disclosed session key from 360 affecting the security of other sessions. 362 4. On-line dictionary attack resistance: It limits an active 363 attacker to test only one password per protocol execution. 365 First, a PAKE protocol must resist off-line dictionary attacks. A 366 password is inherently weak. Typically, it has only about 20-30 bits 367 entropy. This level of security is subject to exhaustive search. 368 Therefore, in the PAKE protocol, the communication must not reveal 369 any data that allows an attacker to learn the password through off- 370 line exhaustive search. 372 Second, a PAKE protocol must provide forward secrecy. The key 373 exchange is authenticated based on a shared password. However, there 374 is no guarantee on the long-term secrecy of the password. A secure 375 PAKE scheme shall protect past session keys even when the password is 376 later disclosed. This property also implies that if an attacker 377 knows the password but only passively observes the key exchange, he 378 cannot learn the session key. 380 Third, a PAKE protocol must provide known key security. A session 381 key lasts throughout the session. An exposed session key must not 382 cause any global impact on the system, affecting the security of 383 other sessions. 385 Finally, a PAKE protocol must resist on-line dictionary attacks. If 386 the attacker is directly engaging in the key exchange, there is no 387 way to prevent such an attacker trying a random guess of the 388 password. However, a secure PAKE scheme should mitigate the effect 389 of the on-line attack to the minimum. In the best case, the attacker 390 can only guess exactly one password per impersonation attempt. 391 Consecutively failed attempts can be easily detected and the 392 subsequent attempts can be thwarted accordingly. 394 It has been proven in [HR10] that J-PAKE satisfies all of the four 395 requirements based on the assumptions that there exists a secure 396 cryptographic hash function and that the Decisional Diffie-Hellman 397 problem is intractable. An independent study that proves security of 398 J-PAKE in a model with algebraic adversaries and random oracles can 399 be found in [ABM15]. By comparison, it has been known that EKE has 400 the problem of leaking partial information about the password to a 401 passive attacker, hence not satisfying the first requirement [Jas96]. 402 For SPEKE and SRP-6, an attacker may be able to test more than one 403 password in one on-line dictionary attack (see [Zha04] and [Hao10]), 404 hence they do not satisfy the fourth requirement in the strict 405 theoretical sense. Furthermore, SPEKE is found vulnerable to an 406 impersonation attack and a key-malleability attack [HS14]. These two 407 attacks affect the SPEKE protocol specified in Jablon's original 1996 408 paper [Jab96] as well in the latest IEEE P1363.2 standard draft D26 409 and the latest published ISO/IEC 11770-4:2006 standard. As a result, 410 the specification of SPEKE in ISO/IEC 11770-4 is being revised to 411 address the identified problems. 413 4. IANA Considerations 415 This document has no actions for IANA. 417 5. Acknowledgements 419 The editor of this document would like to thank Dylan Clarke and 420 Siamak F. Shahandashti for useful comments. This work was supported 421 by the EPSRC First Grant EP/J011541/1. 423 6. References 425 6.1. Normative References 427 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 428 Requirement Levels", BCP 14, RFC 2119, 429 DOI 10.17487/RFC2119, March 1997, 430 . 432 [RFC5054] Taylor, D., Wu, T., Mavrogiannopoulos, N., and T. Perrin, 433 "Using the Secure Remote Password (SRP) Protocol for TLS 434 Authentication", RFC 5054, DOI 10.17487/RFC5054, November 435 2007, . 437 [ABM15] Abdalla, M., Benhamouda, F., and P. MacKenzie, "Security 438 of the J-PAKE Password-Authenticated Key Exchange 439 Protocol", IEEE Symposium on Security and Privacy, May 440 2015. 442 [BM92] Bellovin, S. and M. Merrit, "Encrypted Key Exchange: 443 Password-based Protocols Secure against Dictionary 444 Attacks", IEEE Symposium on Security and Privacy, May 445 1992. 447 [HR08] Hao, F. and P. Ryan, "Password Authenticated Key Exchange 448 by Juggling", 16th Workshop on Security Protocols 449 (SPW'08), May 2008. 451 [HR10] Hao, F. and P. Ryan, "J-PAKE: Authenticated Key Exchange 452 Without PKI", Springer Transactions on Computational 453 Science XI, 2010. 455 [HS14] Hao, F. and S. Shahandashti, "The SPEKE Protocol 456 Revisited", Security Standardisation Research, December 457 2014. 459 [Jab96] Jablon, D., "Strong Password-Only Authenticated Key 460 Exchange", ACM Computer Communications Review, October 461 1996. 463 [Wu98] Wu, T., "The Secure Remote Password protocol", Symposimum 464 on Network and Distributed System Security, March 1998. 466 [I-D-Schnorr] 467 Hao, F., "Schnorr NIZK proof: Non-interactive Zero 468 Knowledge Proof for Discrete Logarithm", Internet Draft 469 submitted to IETF, 2013. 471 6.2. Informative References 473 [BJS07] Barker, E., Johnson, D., and M. Smid, "Recommendation for 474 Pair-Wise Key Establishment Schemes Using Discrete 475 Logarithm Cryptography (Revised)", NIST Special 476 Publication 800-56A, March 2007, 477 . 480 [Jas96] Jaspan, B., "Dual-Workfactor Encrypted Key Exchange: 481 Efficiently Preventing Password Chaining and Dictionary 482 Attacks", USENIX Symphosium on Security, July 1996. 484 [Zha04] Zhang, M., "Analysis of The SPEKE Password-Authenticated 485 Key Exchange Protocol", IEEE Communications Letters, 486 January 2004. 488 [Hao10] Hao, F., "On Small Subgroup Non-Confinement Attacks", 489 IEEE conference on Computer and Information Technology, 490 2010. 492 Author's Address 494 Feng Hao (editor) 495 Newcastle University (UK) 496 Claremont Tower, School of Computing Science, Newcastle University 497 Newcastle Upon Tyne 498 United Kingdom 500 Phone: +44 (0)192-208-6384 501 EMail: feng.hao@ncl.ac.uk