J-PAKE (Password Authenticated Key Exchange by Juggling) was created by Hao and Ryan [1] and fully defined in RFC 8236 [2]. It is a Password Authentication Key Exchange method, and where Bob and Alice share the same secret password. They can then generate a shared secret key. It involves two stages: a one-time key establishment; and a key confirmation stage. Overall, it does not need access to the PKI infrastructure, and uses Non-Interactive Zero Knowledge (NI-ZKP) for proving secret values [J-PAKE (Discrete logs)] [J-PAKE (Elliptic Curve)] [RFC 8238].
Key exchange (J-PAKE) - Discrete Logs |
Theory
J-PAKE is a Password Authentication Key Exchange method, and where Bob and Alice share the same secret password. They can then generate a shared secret key. It involves two stages: a one-time key establishment; a key confirmation stage. Initally Alice and Bob share a secret (\(s\)).
Round 1
Alice then generates two random values: \(x_1\) and \(x_2\). These are kept secret, and where Alice will send the following to Bob:
\(g^{x_1} \pmod p\)
\(g^{x_2} \pmod p\)
Alice will also provide a Non-Interactive Zero Knowledge (NI-ZKP) that she knows \(x_1\) and \(x_2\). Bob then generates two random values: \(x_3\) and \(x_4\). These are kept secret, and where Bob will send the following to Alice:
\(g^{x_3} \pmod p\)
\(g^{x_4} \pmod p\)
Alice will also provide a Non-Interactive Zero Knowledge (NI-ZKP) Proof that she knows \(x_3\) and \(x_4\).
Round 2
Alice then calculates the following and sends to Bob:
\(A = {(g^{x_1}g^{x_3}g^{x_4})}^{x_2 s} \pmod p\)
Bob then calculates the following and sends to Alice:
\(B = {(g^{x_1}g^{x_2}g^{x_3})}^{x_4 s} \pmod p\)
Alice then calculates the shared key as:
\(K={\left(\frac{B}{ { (g^{x_4} ) }^{x_2 s} }\right)}^{x_2} \)
Bob then calculates the shared key as:
\(K={\left(\frac{A}{ { (g^{x_2} ) }^{x_4 s} }\right)}^{x_4} \)
Coding
The following is the code:
import sys import random import hashlib from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes from libnum import invmod primebits=64 secret="Hello" s=int(hashlib.md5(secret.encode()).hexdigest(),16) if (len(sys.argv)>1): primebits=int(sys.argv[1]) p = getPrime(primebits, randfunc=get_random_bytes) g=3 x1 = random.randint(0, p-1) x2 = random.randint(0, p-1) x3 = random.randint(0, p-1) x4 = random.randint(0, p-1) g_x1 = pow(g,x1,p) g_x2 = pow(g,x2,p) g_x3 = pow(g,x3,p) g_x4 = pow(g,x4,p) A=pow(g_x1*g_x3*g_x4,x2*s,p) B=pow(g_x1*g_x2*g_x3,x4*s,p) K_inv1 = invmod(pow(g_x4,x2*s,p),p) K_inv2 = invmod(pow(g_x2,x4*s,p),p) print ("===Alice parameters=== ") print (f"Alice x1={x1}, x2={x2}\nAlice sends: g^x1 (mod p)={g_x1}, g^x2 (mod p)={g_x2}") print ("\n===Bob parameters=== ") print (f"Bob x3={x3}, x4={x4}\nBob sends: g^x3 (mod p)={g_x3}, g^x4 (mod p)={g_x4}") print ("\n===Alice parameters=== ") print (f"Alice sends A={A}") print ("\n===Bob parameters=== ") print (f"Bob sends B={B}") print ("\nKey Alice:\t",pow(B*K_inv1,x2,p)) print ("Key Bob:\t",pow(A*K_inv2,x4,p)) print ("\n\nNow let's prove that Alice knows x_1 with Fiat Shamir") chal=str(g)+str(x1)+str(g_x1) h=hashlib.md5() h.update(chal.encode()) v= random.randint(0, p-1) t=pow(g,v,p) c=int(h.hexdigest(),16) r=(v-c*x1) % (p-1) check=(pow(g,r,p)*pow(g_x1,c,p)) %p if (t==check): print("It has been proven") else: print("Not proven")
And a sample run:
===Alice parameters=== Alice x1=106524968, x2=1011982416 Alice sends: g^x1 (mod p)=88093860, g^x2 (mod p)=1070144538 ===Bob parameters=== Bob x3=78875672, x4=35308790 Bob sends: g^x3 (mod p)=953632599, g^x4 (mod p)=380536516 ===Alice parameters=== Alice sends A=1237521573 ===Bob parameters=== Bob sends B=1678602022 Key Alice: 591343300 Key Bob: 591343300 Now let's prove that Alice knows x_1 with Fiat Shamir It has been proven
References
[1] Hao, F., & Ryan, P. Y. (2008, April). Password authenticated key exchange by juggling. In International Workshop on Security Protocols (pp. 159-171). Springer, Berlin, Heidelberg [here].
[2] F. Hao, J-PAKE: Password-Authenticated Key Exchange by Juggling. RFC 8236.