Password Authenticated Key Exchange by Juggling

The Password Authenticated Key Exchange by Juggling (or J-PAKE) is a password-authenticated key agreement protocol, proposed by Feng Hao and Peter Ryan. This protocol allows two parties to establish private and authenticated communication solely based on their shared (low-entropy) password without requiring a Public Key Infrastructure. It provides mutual authentication to the key exchange, a feature that is lacking in the Diffie–Hellman key exchange protocol.
Description.
Two parties, Alice and Bob, agree on a group formula_1 with generator formula_2 of prime order formula_3 in which the discrete log problem is hard. Typically a Schnorr group is used. In general, J-PAKE can use any prime order group that is suitable for public key cryptography, including Elliptic curve cryptography. Let formula_4 be their shared (low-entropy) secret, which can be a password or a hash of a password (formula_5). The protocol executes in two rounds.
After Round 2, Alice computes formula_24. Similarly, Bob computes formula_25. With the same keying material formula_26, Alice and Bob can derive a session key using a Cryptographic hash function: formula_27.
The two-round J-PAKE protocol is completely symmetric. This helps significantly simplify the security analysis. For example, the proof that one party does not leak any password information in the data exchange must hold true for the other party based on the symmetry. This reduces the number of the needed security proofs by half.
In practice, it is more likely to implement J-PAKE in three flows since one party shall normally take the initiative. This can be done trivially without loss of security. Suppose Alice initiates the communication by sending to Bob: formula_28 and Zero-knowledge proofs. Then Bob replies with: formula_29 and Zero-knowledge proofs. Finally, Alice sends to Bob: formula_19 and a Zero-knowledge proof. Both parties can now derive the same session key.
Depending on the application requirement, Alice and Bob may perform an optional key confirmation step. There are several ways to do it. A simple method described in SPEKE works as follows: Alice sends to Bob formula_31, and then Bob replies with formula_32. Alternatively, Alice and Bob can realize explicit key confirmation by using the newly constructed session key to encrypt a known value (or a random challenge). EKE, Kerberos and Needham-Schroeder all attempt to provide explicit key confirmation by exactly this method.
Security properties.
Given that the underlying Schnorr non-interactive zero-knowledge proof is secure, the J-PAKE protocol is proved to satisfy the following properties:
In 2015, Abdalla, Benhamouda and MacKenzie conducted an independent formal analysis of J-PAKE to prove its security in a random oracle model assuming algebraic adversaries.
The protocol design.
The J-PAKE protocol is designed by combining random public keys in such a structured way to achieve a vanishing effect if both parties supplied exactly the same passwords. This is somehow similar to the Anonymous veto network protocol design. The essence of the idea, however, can be traced back to David Chaum's original Dining Cryptographers network protocol, where binary bits are combined in a structured way to achieve a vanishing effect.
The implementation.
J-PAKE has been implemented in OpenSSL and OpenSSH as an experimental authentication protocol. It was removed from the OpenSSH source code at the end of January 2014. It has also been implemented in Smoke Crypto Chat Messenger, in NSS and was used by Firefox Sync version 1.1 but discontinued in 1.5 which uses a different key exchange and storage method. Mozilla's J-PAKE server was shut down along with the Sync 1.1 storage servers on 30 September 2015. Pale Moon continues to use J-PAKE as part of its Sync service. Since February 2013, J-PAKE has been added to the lightweight API in Bouncycastle (1.48 and onwards). J-PAKE is also used in the Thread (network protocol)
Standardization.
J-PAKE has been included in ISO/IEC 11770-4 (2017) as an international standard. It is also published in RFC 8236.