Test-of-Time: Curve 25519 and PAKE

Test-of-Time: Curve 25519 and PAKE

When you publish a paper, you never know the impact it will have. Some papers you think are amazing, but end up getting very few citiation. Others can suprise you by getting picked-up by other researchers, and who build on your work.

This week, the IACR (International Association for Cryptologic Research) PKC (Public Key Cryptography) conference announced two Test-of-Time Awards — one for PAKE and the other for Curve 25519 [here]. This award relates to papers published at PKC over the past 15 years and which have made a significant contribution.

Curve 25519

The Curve 25519 paper was written by the mighty Daniel J Bernstein (djb) [here]:

You can tell the paper was published 15 years ago, as the tests focus on the Intel Pentium process. But Curve 25519 has stood the test of time, and is now used in many applications areas including with the Tor network, with its usage in the EdDSA signature method (Ed25519) and in X22215 for key exchange. The equation used for the curve is:

y²=x³+486662 x²+x (mod p)

and where p=2²⁵⁵−19

Daniel chose this prime as prime numbers as close as possible to a power of 2 are fast and efficient. He also considered other nearby primes such as 2²⁵⁵ + 95, 2²⁵⁵+31, 2²⁵⁴ + 79, 2²⁵³ + 51, and 2²⁵³ + 39, but selected ²²⁵⁵−19 because 19 was the smallest value.

If you want to find out more about Curve 25519, try here:

https://asecuritysite.com/curve25519/

PAKE

The traditional way for someone to log into a network is to pass their password and then use a slow hashing method such as Argon or PBKDF2 and check it against a stored hash for a given salt value. This, though, gives away the password used. An improved method is for Bob to have his password, and Alice just stores a salt value for Bob. The salt value does not reveal anything about Bob’s password. We can then use PAKE (Password-Based Authentication Key Exchange) for Bob to use his password, and Alice to use her salt value, and then for then to generate a shared secret.

And, so the second paper to be awarded at the conference is [here]:

With this Bob and Alice are able to generate the same secret, even though she listens to their communications. If she tries to spoof Bob or Alice, she will only get one chance to guess the password before she is locked out. Thus, Bob and Alice can use a weak password, as Eve only gets one chance to guess. There is also no offline analysis, as the hand-shake must occur online. Along with this, there are no derived keys from previous sessions [IETF spec]:

Elliptic curve methods (using Curve 25519) are used to provide security methods that are equivalent to 128-bit AES. Often PAKE is used to do a one-time registration, and then generate a new key which becomes the long-term key. As with SRP, we can use PAKE as a log-in method, but its usage must be carefully analysed for risks.

For SPAKE2, we have two roles: A (Alice) and B (Bob). They use two classes (SPAKE2_A and SPAKE2_B), and then pass messages to each other using these. Each time, Bob and Alice will generate a new key.

Alice takes the shared password and converts it into an integer (w). She then picks a random number (x) from 0 to p (a prime number), which is divisible by h. She then calculates:

X=x ×G and T=w ×M+X

The value of T is sent to Bob. Bob also creates w, and picks a random number (y) from 0 to p (a prime number). He then calculates:

Y=y×G, S=w×N+Y

Bob sends the value of Y to Alice.

Alice calculates K(Alice)=x(S-w×N), and Bob calculates K(Bob)=y(T-w×M). These values are basically:

K(Bob)= x (S-w×N) = x (w×N+Y-w×N)=xY = xyG

K(Alice)= y(T-w×M) = y(w ×M+X-w×N)=yX = xyG

The values of N and M for the elliptic curve are:

M =
   d048032c6ea0b6d697ddc2e86bda85a33adac920f1bf18e1b0c6d166a5cecdaf
   seed: edwards25519 point generation seed (M)
N =
   d3bfb518f44f3430f29d0c92af503865a1ed3281dc69b35dd868ba85f886c4ab
   seed: edwards25519 point generation seed (N)

The sample Python coding is [Try here]:

from spake2 import SPAKE2_A
from spake2 import SPAKE2_B
from spake2.parameters.i1024 import Params1024
from spake2.parameters.i2048 import Params2048
from spake2.parameters.i3072 import Params3072

import base64
import sys

password="qwerty"
par = ""

print "Password for Bob and Alice is:",password
if (par<>""):
	print "Security level:",par

if (par=="Params1024"): par=Params1024
if (par=="Params2048"): par=Params1024
if (par=="Params3072"): par=Params3072

if (par==""):
	alice = SPAKE2_A(password)
	bob = SPAKE2_B(password)
else:
	alice = SPAKE2_A(password,params=par)	
	bob = SPAKE2_B(password,params=par)

alice_out = alice.start()
bob_out = bob.start()

print "\nAlice passes:\t",base64.b64encode(alice_out)
print "Bob passes:\t",base64.b64encode(bob_out)



key1 = alice.finish(bob_out)
key2 = bob.finish(alice_out)

print "\nKey (Alice):\t",base64.b64encode(key1)
print "Key (Bob):\t",base64.b64encode(key2)

A sample run is [Try here]:

Password for Bob and Alice is: hello123

Alice passes:	QRXpsrdkAC0xibdqTRLCOOLbvsO7jgvwsju6t9ZF/rsg
Bob passes:	QpVNlqLPQXAvWZSHgxOce86Vzryq1mH+8w6cs9ty8yzj

Key (Alice):	7gbyqgfa5q+R513od++myShq/tC9C7NP+FEf34s8xP4=
Key (Bob):	7gbyqgfa5q+R513od++myShq/tC9C7NP+FEf34s8xP4=

The default is elliptic curve security, but we can use three integer-group parameter sets of Params1024, Params2048 and Params3072 and which gives 80-bit, 112-bit, and 128-bit security levels, respectively.

Well, here’s PAKE:

https://asecuritysite.com/pake/

Conclusions

As a researcher, you never know the impact your paper will have. Some our slow-burners, and others just have no impact at all. A good technique for a researcher is to identify the papers that are making a good impact. For Curve 25519, we see 994 citations, and for PAKE, we have 665 citations:

And, if you are interested, it is Dan Bohen (with an h-index of 124) and Ron Rivest (with an h-index of 104) who are the most citated authors in cryptography: