# An efficient SPEKE protocol with curve25519

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.

• 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

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).

• Note that s only depends on the password, so whether the curve or its twist is used will be the same for each authentication exchange for that password. That means an attacker will learn only a single bit of entropy in total for a password, no matter how many exchanges it witnesses. This doesn't seem like a problem to me. – Matthijs Mar 28 at 20:28
• @Matthijs: being able to discard half the dictionary entries is not a problem? Even if the adversary can't do any further halving, he still is able to do that first one... – poncho Mar 28 at 20:32
• I don't think I'd see that as a problem. Still, it is preventable. I'd also be inclined to not use the password directly but an iterated hash of the password, service identifier (i.e. that what indicates to the user what he's authenticating to) and the username, to limit the impact of a password db compromise, and that would make this information leak a much more significant problem. – Matthijs Apr 1 at 17:02