An efficient SPEKE protocol with curve25519

Question

SPEKE is a very simple and elegant PAKE protocol. I think one of the reasons why PACE was invented and is now the ICAO protocol is that SPEKE was patented. Fortunately, the SPEKE patent expired in March 2017 and therefore we can now 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 $\operatorname{Hash}(\pi \mathbin\| c)$ is an appropriate 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} \mathit{Terminal} & & \mathit{Passport} \\ s = \operatorname{Hash}(\pi) & & s = \operatorname{Hash}(\pi) \\ x' \xleftarrow{$} \{0,1\}^{252} & & y' \xleftarrow{$} \{0,1\}^{252}\\ x \leftarrow x' \mathbin\| (000)_b & & y \leftarrow y' \mathbin\| (000)_b\\ h_x = s^x & \xrightarrow{\quad h_x\quad} & h_y = s^y \\ z \leftarrow h_y^x & \xleftarrow{\quad h_y\quad} & z \leftarrow h_x^y \\ \end{array}

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

Does that make sense regarding security and efficiency?

Updated according to comments from Thomas and poncho.

Answer 1

One small issue is that it can be detected if the x-coordinate lives on the base curve or on its twist.

There's not a small issue; this allows a passive attacker to halve his dictionary by listening into a single exchange.

That is, if $s$ is on the curve, then so will be $s^x$; if $s$ is on the twist, so will be $s^x$.

So, what the attacker can do is listen in, and see if the exchanged $s^x$ and $s^y$ values are on the curve or not. If they are, he can discard the half of his password dictionary that would place $s$ on the twist. If they aren't, he can discard the half of his dictionary that places $s$ on the curve.

SPEKE can be done security based on X25519; however you can't just select $s$ arbitrarily; you have to make sure that it's consistently on the curve (or on the twist).