J-PAKE (Password Authenticated Key Exchange by Juggling) was created by Hao and Ryan [1] and fully defined in RFC 8238 [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 [J-PAKE (Discrete logs)] [J-PAKE (Elliptic Curve)] [RFC 8238].
Key exchange (J-PAKE) - Elliptic Curve method |
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:
\({x_1}G\)
\({x_2}G\)
Bob then generates two random values: \(x_3\) and \(x_4\). These are kept secret, and where Bob will send the following to Alice:
\({x_3}G \)
\({x_4}G \)
Round 2
Alice then calculates the following and sends to Bob:
\(A = {x_2 s} \times {({x_1}G+{x_3}G+{x_4}G)} \)
Bob then calculates the following and sends to Alice:
\(B = {x_4 s} \times {({x_1}G+{x_2}G+{x_3}G)} \)
Alice then calculates the shared key as:
\(K_a= x_2 \times (B - (x_2s) x_4G )) \)
Bob then calculates the shared key as:
\(K_b= x_4 \times (A - (x_4s) x_2G )) \)
Non-interactive Zero-knowledge proof
We use a Fiat Shamir method to prove that Alice knows \(x_1\). As we are using a non-interative method, Alice will create her own challenge with:
\(c=Hash((G) || (x_1) || (x_1G))\)
Alice then creates a random value (\(v\)) and computes:
\(V = vG\)
and:
\(r=(v-c x_1) % n\)
She sends the value of \(V\), \(r\) and \(c\) to Bob, and who computes:
\(V_{check} = rG + c (x_1 G)\)
If \(V\) is equal to \(V_{check}\) Alice has proven that she knows \(x_1\).
Coding
The following is the code:
from secp256k1 import curve,scalar_mult, point_add,point_neg import random import hashlib import sys secret="Hello" if (len(sys.argv)>1): secret=sys.argv[1] s=int(hashlib.md5(secret.encode()).hexdigest(),16) # Alice generates x1 = random.randint(0, curve.n-1) x2 = random.randint(0, curve.n-1) # Bob generates x3 = random.randint(0, curve.n-1) x4 = random.randint(0, curve.n-1) # Alice generates x1G = scalar_mult(x1, curve.g) x2G = scalar_mult(x2, curve.g) # Alice generates x3G = scalar_mult(x3, curve.g) x4G = scalar_mult(x4, curve.g) # A= (G1 + G3 + G4) x [x2*s] A = point_add(x1G,x3G) A = point_add(A,x4G) A = scalar_mult(x2*s,A) # B=(G1 + G2 + G3) x [x4*s] B = point_add(x1G,x2G) B = point_add(B,x3G) B = scalar_mult(x4*s,B) # Ka = (B - (G4 x [x2*s])) x [x2] Ka = scalar_mult(x2,point_add(B,point_neg(scalar_mult(x2*s,x4G)))) # Bob computes Kb = (A - (G2 x [x4*s])) x [x4] Kb = scalar_mult(x4,point_add(A,point_neg(scalar_mult(x4*s,x2G)))) print (f"Shared password: {secret}") print ("===Alice parameters=== ") print (f"Alice x1={x1}, x2={x2}\nAlice sends: x1G ={x1G}, x2G (mod p)={x2G}") print ("\n===Bob parameters=== ") print (f"Bob x3={x3}, x4={x4}\nBob sends: x3G ={x3G}, x4G ={x4G}") print ("\n===Alice parameters=== ") print (f"Alice sends A={A}") print ("\n===Bob parameters=== ") print (f"Bob sends B={B}") print (f"\nAlice key: {Ka[0]}") print (f"Bob key: {Kb[0]}") print ("\n\nNow let's prove that Alice knows x_1 with Fiat Shamir") chal=str(curve.g)+str(x1)+str(x1G) h=hashlib.md5() h.update(chal.encode()) v= random.randint(0, curve.n-1) V = scalar_mult(v, curve.g) c=int(h.hexdigest(),16) r=(v-c*x1) % (curve.n) Vcheck = point_add(scalar_mult(r,curve.g),scalar_mult(c,x1G)) if (V==Vcheck): print("It has been proven") else: print("Not proven")
And a sample run:
Shared password: Hello ===Alice parameters=== Alice x1=78397092304740574576107958499364882318732028200925758632687232240072388291316, x2=37703292127007497378952942470068877221566322506080892570580352921610166749861 Alice sends: x1G =(92762139762810346257055556604580623304994764469418188267656968718559566362695, 46813956701020797788698580145254503333591120986752800190841586404807197273025), x2G (mod p)=(69412465657632519238196370625536720398140619599020428468713249325337894574704, 68634241711578360709475108750587182031911570250043615155230916469113509764464) ===Bob parameters=== Bob x3=33967246462239956163283556850063422872664629224250781818243388093392731239921, x4=44526421723702671580644861971665591734086378275262697524347833602347282035685 Bob sends: x3G =(51091083314414709808012513017993952539396317705714047846012230251802682988298, 96913591558745622107288348049884968103495488574798320737231695092387895188335), x4G =(51676623213980961163969659711077774845495069951875379779990177661828206192187, 43676298137663973094534332654115415153518597785305028849290010849699897570909) ===Alice parameters=== Alice sends A=(15454852367162069542957138372782762305395823502762283356556185943757775140409, 105612415449959441005189970442190526374313119224194594421512468341289149736502) ===Bob parameters=== Bob sends B=(78858484477324495957749761221513915613750468185385073709752561588499098484014, 23089512326527982045402177903536113948943722936464069520379147278777955212444) Alice key: 10966678858361918560916419082448454024529619681427339796459004118733349541854 Bob key: 10966678858361918560916419082448454024529619681427339796459004118733349541854 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].