An efficient PACE protocol with curve25519

Question

The PACE protocol is a password authenticated key agreement which is widely used. For instance, in the electronic ICAO passports as the so called SAC protocol. PACE is standardised in ICAO DOC9303 Part 11.
PACE is rather complicated. For instance, it needs 2 Diffie-Hellman exchanges and a specific $G' = s*G+H$ mapping function. The complexity stems form the fact that PACE needs a function, which hashes a random value into a curve point. The function must also be timing invariant and may not lead to offline dictionary attacks.

Now I think with Curve25519 and Montgomery arithmetic we can remove all those difficulties and make a very simple PACE variant. The main reason for simplicity is that mapping a random value in the curve is easy on Curve25519. First, one can simply using that random value as the x-coordinate, because one does not have to find an x-coordinate lying on the curve. Second, Curve25519 uses the x-coordinate only. So, one does not have to calculate a corresponding y-coordinate. And finally, Curve25519 arithmetic is timing invariant.

Now let's construct the simple PACE protocol:

Let $Enc_k(x)$ be an encryption function (e.g. AES) , where k is somehow derived form a password. The same for $Dec_k(x)$ as decryption function.

\begin{array}{lcr} Terminal & & Passport \\ & & s \xleftarrow{$} \{0,1\}^{128} \\ s \leftarrow Dec_k(s') & \xleftarrow{\hspace{1cm} s' \hspace{1cm} } & s' \leftarrow Enc_k(s) \\ x \xleftarrow{$} \{0,1\}^{256} & & y \xleftarrow{$} \{0,1\}^{256}\\ 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}

Looks too good to be true!
So, do you see any problem here?

P.S. As Poncho made clear, this doesn’t work. But maybe someone sees an advantage of using curve22519 for PACE or any other related PAKE protocol (e.g. SPEKE).

Answer 1

Sorry, but this doesn't quite work; it allows the adversary with a dictionary of possible passwords to eliminate large parts of his dictionary efficiently.

Here's how a terminal who doesn't know the $k$ can eliminate half of the possible values in his dictionary per exchange:

• The terminal receives $Enc_k(s)$; he remembers it

• The terminal sends a random $h_x$ value; doesn't matter what it is

• The terminal receives $h_y = s^x$; he determines whether $h_y$ is on the curve or on the twist.

Then, for every $k'$ that is in his dictionary, he computes $Dec_{k'}(Enc_k(s))$, and determines if that is on curve or on the twist.

If $k' = k$, then $y_h$ and $Dec_{k'}(Enc_k(s))$ will both be either on the curve, or on the twist; hence if one is on the curve, and the other is on the twist, he knows that wasn't the correct value of $k$.

This logic will allow him to eliminate about half of his values in the dictionary; going through this process 20 times will reduce a 1 million entry dictionary to the 1 correct entry (and perhaps 1 false hit).

Now, this sort of thing could be made to work over a MODP group; we just pick a Sophie-Germain prime (that is, one where $(p-1)/2$ is also prime) that's just under (say) $2^{2048}$; there we have an efficient mapping between random bit strings to members of the subgroup of quadratic residues (and so testing which subgroup $h_x, h_y$ are in doesn't yield any information...)