JPAKE: Password Authenticated Key Exchange by Juggling
drafthaojpake00
The information below is for an old version of the document.
Document  Type 
This is an older version of an InternetDraft that was ultimately published as RFC 8236.
Expired & archived



Author  Feng Hao  
Last updated  20131122 (Latest revision 20130521)  
RFC stream  (None)  
Formats  
IETF conflict review  conflictreviewhaojpake, conflictreviewhaojpake, conflictreviewhaojpake, conflictreviewhaojpake, conflictreviewhaojpake, conflictreviewhaojpake, conflictreviewhaojpake  
Stream  Stream state  (No stream defined)  
Consensus boilerplate  Unknown  
RFC Editor Note  (None)  
IESG  IESG state  Became RFC 8236 (Informational)  
Telechat date  (None)  
Responsible AD  (None)  
Send notices to  (None) 
drafthaojpake00
Network Working Group F. Hao, Ed. InternetDraft Newcastle University (UK) Intended status: Informational May 21, 2013 Expires: November 22, 2013 JPAKE: Password Authenticated Key Exchange by Juggling drafthaojpake00 Abstract This document specifies a Password Authenticated Key Exchange by Juggling (JPAKE) protocol. This protocol allows the establishment of a secure endtoend communication channel between two remote parties over an insecure network solely based on a shared password, without requiring a Public Key Infrastructure (PKI) or any trusted third party. Status of This Memo This InternetDraft is submitted in full conformance with the provisions of BCP 78 and BCP 79. InternetDrafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as InternetDrafts. The list of current Internet Drafts is at http://datatracker.ietf.org/drafts/current/. InternetDrafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use InternetDrafts as reference material or to cite them other than as "work in progress." This InternetDraft will expire on November 22, 2013. Copyright Notice Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved. Hao Expires November 22, 2013 [Page 1] InternetDraft JPAKE May 2013 This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/licenseinfo) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Requirements language . . . . . . . . . . . . . . . . . . 3 1.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 3 2. JPAKE Protocol . . . . . . . . . . . . . . . . . . . . . . . 4 2.1. Protocol setup . . . . . . . . . . . . . . . . . . . . . 4 2.2. Tworound key exchange . . . . . . . . . . . . . . . . . 4 2.3. Threepass variant . . . . . . . . . . . . . . . . . . . 6 2.4. Key confirmation . . . . . . . . . . . . . . . . . . . . 6 2.5. Computational cost . . . . . . . . . . . . . . . . . . . 7 3. Security Considerations . . . . . . . . . . . . . . . . . . . 7 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.1. Normative References . . . . . . . . . . . . . . . . . . 9 6.2. Informative References . . . . . . . . . . . . . . . . . 10 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 10 1. Introduction PasswordAuthenticated Key Exchange (PAKE) is a technique that aims to establish secure communication between two remote parties solely based on their shared password, without relying on a Public Key Infrastructure or any trusted third party [BM92]. The first PAKE protocol, called EKE, was proposed by Steven Bellovin and Michael Merrit in 1992 [BM92]. Other wellknown PAKE protocols include SPEKE (by David Jablon in 1996) [Jab96] and SRP (by Tom Wu in 1998) [Wu98]. SRP has been revised several times in response to reported attacks. The last version of SRP is 6, hence it is also known as SRP6 [RFC5054]. This document specifies a PAKE protocol called Password Authenticated Key Exchange by Juggling (JPAKE), which was designed by Feng Hao and Peter Ryan in 2008 [HR08]. There are a few factors that may be considered in favor of JPAKE. First, JPAKE has security proofs, while equivalent proofs are lacking in EKE, SPEKE and SRP6. Second, JPAKE is not patented. It follows a completely different design Hao Expires November 22, 2013 [Page 2] InternetDraft JPAKE May 2013 approach from all other PAKE protocols, and is the first PAKE scheme that is built upon a wellestablished Zero Knowledge Proof (ZKP) primitive: Schnorr signature. Third, JPAKE is efficient. It adopts novel engineering techniques to optimize the use of ZKP so that overall the protocol is sufficiently efficient for practical use. Fourth, JPAKE is designed to work generically in both the finite field and elliptic curve setting (i.e., DSA and ECDSAlike groups). Unlike SPEKE, it does not require any extra primitive of hashing passwords onto a designated elliptic curve. Finally, JPAKE has already been used in realworld applications at a relatively large scale. Since 2008, it has been included into widely distributed open source libraries such as OpenSSL, OpenSSH, Network Security Services (NSS) and the Bouncy Castle. In 2010, it was adopted by Mozilla and built into the Firefox browser (version 4 and onwards) to implement the secure sync service. 1.1. Requirements language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. 1.2. Notations The following notations are used in this document: o Alice: the assumed identity of the first party in the protocol o Bob: the assumed identify of the second party in the protocol o s: a lowentropy secret shared between Alice and Bob o p: a large prime o q: a large prime divisor of p1 o Zp*: a multiplicative group of integers modulo p o Gq: a subgroup of Zp* with primer order q o g: a generator of Gq o g^x: g raised to the power of x o a mod b: a modulo b o a * b: a multiplied by b Hao Expires November 22, 2013 [Page 3] InternetDraft JPAKE May 2013 o a  b: concatenation of a and b o H: a secure oneway hash function o KDF(a): Key Derivation Function with input a o HMAC(MacKey, MacData): HMAC function with MacKey as the key and MacData as the input data 2. JPAKE Protocol 2.1. Protocol setup The JPAKE protocol uses exactly the same group setting as DSA (or ECDSA). For simplicity, this document will only describe the JPAKE protocol in the DSAlike group setting. The protocol works basically the same in the ECDSAlike group setting, except that the underlying multiplicative group over a finite field is replaced by an additive group over an elliptic curve. Let Gq denote a subgroup of Zp* with prime order q, in which the Decisional DiffieHellman problem (DDH) is intractable. The p and q are large primes and q divides p1. Let g be a generator in Gq. Any nonidentity element in Gq can be a generator. The two communicating parties, Alice and Bob, both agree on (p, q, g). Values of (p, q, g), as defined by NIST, can be found in the appendix of [IDSchnorr]. [[: Q1:The reference is an accompanying internet draft submission to IETF and it needs to be updated once it is accepted by IETF.]] Let s be the shared secret between Alice and Bob. The secret may be a password, a hash of the password or any other derivative from a password. This does not make any difference to the protocol. The only assumptions are that s has lowentropy and that the value of s falls within [1, q1]. (Note that s must not be 0 for any nonempty secret.) 2.2. Tworound key exchange Round 1: Alice selects at random x1 from [0, q1] and x2 from [1, q1]. Similarly, Bob selects at random x3 from [0, q1] and x4 from [1, q1]. o Alice > Bob: g^{x1} mod p, g^{x2} mod p and knowledge proofs for x1 and x2 o Bob > Alice: g^{x3} mod p, g^{x4} mod p and knowledge proofs for x3 and x4 Hao Expires November 22, 2013 [Page 4] InternetDraft JPAKE May 2013 In this round, the sender must demonstrate the knowledge of the ephemeral private keys. A suitable technique is to use the Schnorr signature [IDSchnorr]. As an example, suppose one wishes to prove the knowledge of the exponent for X = g^x mod p. The generated Schnorr signature will contain: {SignerID, V = g^v mod p, r = v  x * h mod q} where SignerID is the unique identifier for the signer, v is a random element chosen from [0, q1] and h = H(g  V  X  SignerID). The "uniqueness" of SignerID is defined from the user's perspective  for example, if Alice communicates with several parties, she shall associate a unique identity with each party to avoid confusion. During the key exchange process using JPAKE, each party shall ensure the two identities used by both parties are different (to prevent replaying one's signature to herself) and that the other party has been consistently using the same identity throughout the protocol execution. Details about the Schnorr signature, including the generation and the verification procedures, can be found in [IDSchnorr]. When this round finishes, Alice verifies the received knowledge proofs as specified in [IDSchnorr] and also checks that g^{x4} != 1 mod p. Similarly, Bob verifies the received knowledge proofs and also checks that g^{x2} != 1 mod p. Round 2: o Alice > Bob: A=g^{(x1+x3+x4)*x2*s} mod p and a knowledge proof for (x2*s) o Bob > Alice: B=g^{(x1+x2+x3)*x4*s} mod p and a knowledge proof for (x4*s) In this round, the Schnorr signature is computed in the same way as in the previous round except that the generator is different. For Alice, the generator used is g^(x1+x3+x4) instead of g; for Bob, the generator is g^(x1+x2+x3) instead of g. Since any nonidentity element in Gq can be used as a generator, Alice and Bob just need to ensure g^(x1+x3+x4) != 1 mod p and g^(x1+x2+x3) != 1 mod p. With overwhelming probability, these inequalities are statistically guaranteed even when the user is communicating with an adversary (i.e., in an active attack). Nonetheless, for absolute guarantee, the receiving party may wish to explicitly check if these inequalities hold, and the cost of doing that is negligible. When the second round finishes, Alice and Bob verify the received knowledge proofs and then compute key material K as follows: o Alice computes K = (B/g^{x2*x4*s})^{x2} mod p = g^{(x1+x3)*x2*x4*s} mod p Hao Expires November 22, 2013 [Page 5] InternetDraft JPAKE May 2013 o Bob computes K = (A/g^{x2*x4*s})^{x4} mod p = g^{(x1+x3)*x2*x4*s} mod p With the same keying material K, both parties can derive a common session key k using a Key Derivation Function (KDF). If the subsequent secure communication uses a symmetric cipher in an authenticated mode (say AESGCM), then one key is sufficient, i.e., k = KDF(K). Otherwise, the session key should comprise an encryption key (for confidentiality) and a MAC key (for integrity), i.e., k = k_enc  k_mac, where k_enc = KDF(K  "JPAKE_ENC") and k_mac = KDF(K  "JPAKE_MAC"). The exact choice of the KDF is left to specific applications to define. (In many cases, the KDF can simply be a cryptographic hash function, e.g., SHA256.) 2.3. Threepass variant The tworound JPAKE protocol is completely symmetric, which significantly simplifies the security analysis. In practice, one party normally initiates the communication and the other party responds. In that case, the protocol will be completed in three passes instead of two rounds. The tworound JPAKE protocol can be trivially changed to three passes without losing security. Assume Alice initiates the key exchange. The threepass variant works as follows: 1. Alice > Bob: g^{x1} mod p, g^{x2} mod p, knowledge proofs for x1 and x2. 2. Bob > Alice: g^{x3} mod p, g^{x4} mod p, B=g^{(x1+x2+x3)*x4*s mod p, knowledge proofs for x3, x4, and x4*s. 3. Alice > Bob: A=g^{(x1+x3+x4)*x2*s} mod p and a knowledge proof for x2*s. Both parties compute the session keys in exactly the same way as before. 2.4. Key confirmation The tworound JPAKE protocol (or threepass variant) provides cryptographic guarantee that only the authenticated party who used the same password at the other end is able to compute the same session key. So far the authentication is only implicit. For achieving explicit authentication, an additional key confirmation procedure should be performed. This is to ensure that both parties have actually obtained the same session key. Hao Expires November 22, 2013 [Page 6] InternetDraft JPAKE May 2013 There are several explicit key confirmation methods available. They are generically applicable to all key exchange protocols, not just JPAKE. In general, it is recommended to use a different key from the session key for key confirmation, say using k' = KDF(K  "JPAKE_KC"). The advantage of using a different key for key confirmation is that the session key remains indistinguishable from random after the key confirmation process (although this perceived advantage is actually subtle and only theoretical). Two key confirmation methods are presented here. The first method is based on the one used in the SPEKE protocol [Jab96]. 1. Alice > Bob: H(H(k')) 2. Bob > Alice: H(k') The second method is based on the unilateral key confirmation scheme specified in NIST SP 80056A Revision 1 [BJS07]. o Alice > Bob: MacTagAlice = HMAC(k', "KC_1_U  Alice  Bob  g^x1  g^x2  g^x3  g^x4") o Bob > Alice: MacTagBob = HMAC(k', "KC_1_U  Bob  Alice  g^x3  g^x4  g^x1  g^x2") The second method assumes an additional secure MAC function (HMAC) and is slightly more complex than the first method; however, it can be completed within one round and it preserves the overall symmetry of the protocol implementation. This may prove desirable in some applications. 2.5. Computational cost In JPAKE, the modular exponentiations are the predominant factors in the computation. Hence, the computational cost is estimated based on counting the number of such modular exponentiations. Note that it takes one exponentiation to generate a Schnorr signature and two to verify it [IDSchnorr]. For Alice, she has to perform 8 exponentiations in the first round, 4 in the second round, and 2 in the final computation of the session key. Hence, that is 14 modular exponentiations in total. Based on symmetry, the computational cost for Bob is exactly the same. 3. Security Considerations A PAKE protocol is designed to provide two functions in one protocol execution. The first one is to provide zeroknowledge authentication Hao Expires November 22, 2013 [Page 7] InternetDraft JPAKE May 2013 of a password. It is called "zero knowledge" because at the end of the protocol, the two communicating parties will learn nothing more than one bit information: whether the passwords supplied at two ends are equal. Therefore, a PAKE protocol is naturally resistant against phishing attacks. The second function is to provide session key establishment if the two passwords are equal. The session key will be used to protect the confidentiality and integrity of the subsequent communication. More concretely, a secure PAKE protocol shall satisfy the following security requirements [HR10]. 1. Offline dictionary attack resistance: It does not leak any information that allows a passive/active attacker to perform off line exhaustive search of the password. 2. Forward secrecy: It produces session keys that remain secure even when the password is later disclosed. 3. Knownkey security: It prevents a disclosed session key from affecting the security of other sessions. 4. Online dictionary attack resistance: It limits an active attacker to test only one password per protocol execution. First, a PAKE protocol must resist offline dictionary attacks. A password is inherently weak. Typically, it has only about 2030 bits entropy. This level of security is subject to exhaustive search. Therefore, in the PAKE protocol, the communication must not reveal any data that allows an attacker to learn the password through off line exhaustive search. Second, a PAKE protocol must provide forward secrecy. The key exchange is authenticated based on a shared password. However, there is no guarantee on the longterm secrecy of the password. A secure PAKE scheme shall protect past session keys even when the password is later disclosed. This property also implies that if an attacker knows the password but only passively observes the key exchange, he cannot learn the session key. Third, a PAKE protocol must provide known key security. A session key lasts throughout the session. An exposed session key must not cause any global impact on the system, affecting the security of other sessions. Finally, a PAKE protocol must resist online dictionary attacks. If the attacker is directly engaging in the key exchange, there is no way to prevent such an attacker trying a random guess of the Hao Expires November 22, 2013 [Page 8] InternetDraft JPAKE May 2013 password. However, a secure PAKE scheme should mitigate the effect of the online attack to the minimum. In the best case, the attacker can only guess exactly one password per impersonation attempt. Consecutively failed attempts can be easily detected and the subsequent attempts can be thwarted accordingly. It has been proven in [HR10] that JPAKE satisfies all of the four requirements based on the assumptions that there exists a secure cryptographic hash function and that the Decisional DiffieHellman problem is intractable. By comparison, it has been known that EKE has the problem of leaking partial information about the password to a passive attacker, hence not satisfying the first requirement [Jas96]. For SPEKE and SRP6, an attacker may be able to test more than one password in one online dictionary attack (see [Zha04] and [Hao10]), hence they do not satisfy the fourth requirement in the strict theoretical sense. 4. IANA Considerations This document has no actions for IANA. 5. Acknowledgements The editor of this document would like to thank Dr Dylan Clarke for useful comments. This work was supported by the EPSRC First Grant EP /J011541/1. 6. References 6.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC5054] Taylor, D., Wu, T., Mavrogiannopoulos, N., and T. Perrin, "Using the Secure Remote Password (SRP) Protocol for TLS Authentication", RFC 5054, November 2007. [BM92] Bellovin, S. and M. Merrit, "Encrypted Key Exchange: Passwordbased Protocols Secure against Dictionary Attacks", IEEE Symposium on Security and Privacy, May 1992. [HR08] Hao, F. and P. Ryan, "Password Authenticated Key Exchange by Juggling", 16th Workshop on Security Protocols (SPW'08), May 2008. Hao Expires November 22, 2013 [Page 9] InternetDraft JPAKE May 2013 [HR10] Hao, F. and P. Ryan, "JPAKE: Authenticated Key Exchange Without PKI", Springer Transactions on Computational Science XI, 2010. [Jab96] Jablon, D., "Strong PasswordOnly Authenticated Key Exchange", ACM Computer Communications Review, October 1996. [Wu98] Wu, T., "The Secure Remote Password protocol", Symposimum on Network and Distributed System Security, March 1998. [IDSchnorr] Hao, F., "Schnorr Signature: Noninteractive Zero Knowledge Proof for Discrete Logarithm", Internet Draft submitted to IETF, 2013. 6.2. Informative References [BJS07] Barker, E., Johnson, D., and M. Smid, "Recommendation for PairWise Key Establishment Schemes Using Discrete Logarithm Cryptography (Revised)", NIST Special Publication 80056A, March 2007, <http://csrc.nist.gov/ publications/nistpubs/80056A/ SP80056A_Revision1_Mar082007.pdf>. [Jas96] Jaspan, B., "DualWorkfactor Encrypted Key Exchange: Efficiently Preventing Password Chaining and Dictionary Attacks", USENIX Symphosium on Security, July 1996. [Zha04] Zhang, M., "Analysis of The SPEKE PasswordAuthenticated Key Exchange Protocol", IEEE Communications Letters, January 2004. [Hao10] Hao, F., "On Small Subgroup NonConfinement Attacks", IEEE conference on Computer and Information Technology, 2010. Author's Address Feng Hao (editor) Newcastle University (UK) Claremont Tower, School of Computing Science, Newcastle University Newcastle Upon Tyne United Kingdom Phone: +44 (0)1922226384 EMail: feng.hao@ncl.ac.uk Hao Expires November 22, 2013 [Page 10]