# An efficient SPEKE protocol with curve25519

SPEKE is a very simple and elegant PAKE protocol. I think, one of the reasons why PACE has been invented and is now the ICAO protocol, is because SPEKE was patented. Fortunately, the SPEKE patent expired in March 2017 and therefor we now can freely use it.

In SPEKE, one needs to hash a password into an elliptic curve. That can be done by hashing into the x-coordinate and the calculate the corresponding y-coordinate. The tricky part is that not every x-coordinate has an y-coordinate in the base field. So, the following or a related method is used.

1. Search an integer value $c$ starting from zero, such that $Hash(\pi | c)$ is an appropiate x-coordinate on the curve.
2. calculate the corresponding y-coordinate.

With curve25519 we can simplify both steps, because

1. Every x-coordinate is defined
2. y-coordinates are not necessary

SPEKE with curve25519

\begin{array}{lcr} Terminal & & Passport \\ s = Hash(\pi) & & s = Hash(\pi) \\ x‘ \xleftarrow{$} \{0,1\}^{252} & & y‘ \xleftarrow{$} \{0,1\}^{252}\\ x \leftarrow x‘ \| (000)_b & & y \leftarrow y‘ \| (000)_b\\ h_x = s^x & \xrightarrow{h_x} & h_y = s^y \\ z \leftarrow h_y^x & \xleftarrow{h_y} & z \leftarrow h_x^y \\ \end{array}

One small issue is that it can be detected if the x-ccordinate lives on the base curve or on its twist. That means, one looses 1 bit of entropy from the password. I think, one can live with that small loss.

The question is if that makes sense regarding security and efficiency.

Updated according to comments from Thomas and poncho.

• What's the question? Is that the generic "is this secure?" (and my answer to that one would be "no" because not only of the leak of 1 bit due to the curve you fall on, but also the 2 or 3 more bits you lose with points of low order) – Thomas Pornin Sep 28 '17 at 21:20
• The points of low order issue that Thomas raises can be fixed by making sure that $x, y$ are multiple of 8 (i.e. 3 lsbits are 0). – poncho Sep 28 '17 at 21:28