Coordinate conditions

2013-12-29T21:39:04Z

78.50.89.223:

In cryptography, the '''Password Authenticated Key Exchange by Juggling''' (or J-PAKE) is a [[password-authenticated key agreement]] protocol.<ref>F. Hao, P. Ryan. [http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf Password Authenticated Key Exchange by Juggling]. ''Proceedings of the 16th International Workshop on Security Protocols, 2008.</ref> This technique 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. The authors suggest that J-PAKE may be helpful in avoiding patents in the field.

==Description==

Two parties, Alice and Bob, agree on a group <math>G</math> with generator <math>g</math> of prime order <math>q</math> 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 <math>s</math> be their shared (low-entropy) secret, which can be a password or a hash of a password (<math>s \neq 0</math>). The protocol executes in two rounds.

;Round 1: Alice selects <math>x_1 \in_R [0, q-1]</math>, <math>x_2 \in_R (0, q-1]</math> and sends out <math>g^{x_1}</math>, <math>g^{x_2}</math> together with the [[Zero-knowledge proofs]] (using for example [[Schnorr signature]]) for the proof of the exponents <math>x_1</math> and <math>x_2</math>. Similarly, Bob selects <math>x_3 \in_R [0, q-1]</math>, <math>x_4 \in_R (0, q-1]</math> and sends out <math>g^{x_3}</math>, <math>g^{x_4}</math> together with the [[Zero-knowledge proofs]] for the proof of the exponents <math>x_3</math> and <math>x_4</math>. The above communication can be completed in one round as neither party depends on the other. When it finishes, Alice and Bob verify the received [[Zero-knowledge proofs]] and also check <math>g^{x_2}, g^{x_4} \neq 1</math>.

;Round 2: Alice sends out <math>A = g^{(x_1 + x_3 + x_4) x_2 s}</math> and a [[Zero-knowledge proof]] for the proof of the exponent <math>x_2 s</math>. (Note Alice actually derives a new public key using <math>g^{x_1 + x_3 + x_4}</math> as the generator). Similarly, Bob sends out <math>B = g^{(x_1 + x_2 + x_3) x_4 s}</math> and a [[Zero-knowledge proof]] for the proof of the exponent <math>x_4 s</math>.

After Round 2, Alice computes <math>K = (B/g^{x_2 x_4 s})^{x_2} = g^{(x_1 + x_3) x_2 x_4 s}</math>. Similarly, Bob computes <math>K = (A/g^{x_2 x_4 s})^ {x_4} = g^{(x_1 + x_3) x_2 x_4 s}</math>. With the same keying material <math>K</math>, Alice and Bob can derive a session key using a [[Cryptographic hash function]]: <math>\kappa = H(K)</math>.

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: <math>g^{x_1}, g^{x_2}</math> and Zero-knowledge proofs. Then Bob replies with: <math>g^{x_3}, g^{x_4}, B = g^{(x_1 + x_2 + x_3) x_4 s}</math> and Zero-knowledge proofs. Finally, Alice sends to Bob: <math>A = g^{(x_1 + x_3 + x_4) x_2 s}</math> 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 (cryptography)|SPEKE]] works as follows: Alice sends to Bob <math>H(H(\kappa))</math>, and then Bob replies with <math>H(\kappa)</math>.<ref>{{cite journal | first = David | last = Jablon | title = Strong Password-Only Authenticated Key Exchange | journal = Computer Communication Review | publisher = ACM SIGCOMM | volume = 26 | issue = 5 | pages = 5–26 |date=October 1996 | url = http://www.jablon.org/passwordlinks.html#Jab96 | doi = 10.1145/242896.242897}}</ref> 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). [[Encrypted key exchange|EKE]], [[Kerberos (protocol)|Kerberos]] and [[Needham-Schroeder]] all attempt to provide explicit key confirmation by exactly this method.

==Security properties==

The J-PAKE protocol is provably secure, fulfilling the following properties<ref>F. Hao, P. Ryan. [http://eprint.iacr.org/2010/190.pdf J-PAKE: Authenticated Key Exchange Without PKI]. ''Springer Transactions on Computational Science XI, Special Issue on Security in Computing, Part II, Vol. 6480, pp. 192-206, 2010.</ref>.

# Off-line dictionary attack resistance - It does not leak any password verification information to a passive/active attacker.
# Forward secrecy - It produces session keys that remain secure even when the password is later disclosed.
# Known-key security - It prevents a disclosed session key from affecting the security of other sessions.
# On-line dictionary attack resistance - It limits an active attacker to test only one password per protocol execution.

==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 problem | Dining Cryptographers]] network protocol,<ref>David Chaum. [http://dx.doi.org/10.1007/BF00206326 The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability] Journal of Cryptology, vol. 1, No, 1, pp. 65-75, 1988</ref> 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 has also been implemented in [[Network Security Services|NSS]] and is used by [[Firefox Sync]]. Since February 2013, J-PAKE has been added to the lightweight API in [[Bouncycastle]] (1.48 and onwards).

==References==
{{reflist}}

==External links==
* [http://www.links.org/?p=393 A prototype demo of J-PAKE in C]
* [http://haofeng66.googlepages.com/JPAKEDemo.java A prototype demo of J-PAKE in Java]
* [http://homepages.cs.ncl.ac.uk/feng.hao/files/EllipticCurveJPAKEDemo.java An example of implementing J-PAKE using Elliptic Curve]
* [http://www.lightbluetouchpaper.org/2008/05/29/j-pake J-PAKE: From Dining Cryptographers to Jugglers]

{{DEFAULTSORT:Password Authenticated Key Exchange By Juggling}}
[[Category:Cryptography]]
[[Category:Cryptographic protocols]]

formulasearchengine - User contributions [en]

Coordinate conditions