2
$\begingroup$

I've been looking into implementing cPace, and I saw that two cipher suites defined for it refered to draft-irtf-cfrg-hash-to-curve for its protocol definition. Part of cPace requires mapping a string hash to a point on the elliptic curve, so it uses the other standard's methods for doing that, in particular its choice of map_to_curve for each curve.

Looking through draft-irtf-cfrg-hash-to-curve, its provided options for map_to_curve, such as Simplified SWU and Elligator 2, seem rather complicated to me. It seems to me that, for example, Elligator 2 is performing a lot of steps to be able to perform this mapping. There is also the issues of (some implementations of) map_to_curve that require additional steps, such as summing two calls to map_to_curve to even the distribution and having to remove the cofactor from the result.

It seems to me that it should be simple enough to map an integer/field element $u$ to a curve point by just using $uG$ with $G$ being the generator for the curve. I can't figure out why this method wasn't used instead. Through my research into Elligator 2, I found that it was originally designed to be a two-way mapping, but the (draft) specification is using it in a one-way context.

What is (or might be) the reason why algorithms like Elligator 2 are being used for this instead of just using $uG$? My best guess so far is for efficiency because Elligator 2 is faster than computing $uG$, but I haven't found any evidence that was the consideration, and I don't know if it even is faster.

As a follow-up question, would it be wrong to replace Elligator 2 with $uG$? I.E. would it result in making the protocol cryptographically weaker? I was looking to implement cPace, but the library I'm using (OpenSSL) doesn't provide an implementation of Elligator 2 nor provide an interface for working directly with curve points on X25519 to help with my own implementation, but it does provide access to performing $uG$ as part of its DH implementation.

$\endgroup$
3
$\begingroup$

It seems to me that it should be simple enough to map an integer/field element $u$ to a curve point by just using $uG$ with $G$ being the generator for the curve.

That is indeed simple; however using it would forfeit the security properties of cPace.

Here's why; cPace essentially works by having both sides map the secret password (and some nonces) to an elliptic curve point, and then having both sides perform a DH operation with the elliptic curve point. The general idea is that if you are an active attacker who has a guess of the password (and that guess is wrong), you won't know the secret the valid system (who does know the password) will use, and so you won't be able to predict the shared secret (or even be able to recognize it).

However, here is what an attacker could do with your password hashing scheme; the attacker can pick a password, and implement the protocol assuming that password was correct; that is, he generates a point $H = hash(password)G$, generates a random value $x$, computes $xH$, sends that to the system under attack; that system sends a point $J$ (which is his $yH$ value) and you compute $xJ$; the system under attack then sends a message encrypted based on the secret he computed.

If the attacker's guess of the password were correct, then both sides will generate the same secret, and so the attacker can decrypt the message - no surprise there. However, suppose the initial password guess was wrong. Then, what the attacker could do is takes a second password guess, and compute $H' = hash(password')G$ and compute $x' = hash(password) hash(password')^{-1} x$. Note that the values $x'H' = xH$, and so with this password (and modified $x'$) we would have sent the exact same DH public value; so, we can then compute $x'J$ (based on the point the other side sent), and use that to compute the shared secret and then decrypt the encrypted message - if he second guess to the password was correct, then that would work.

He can perform the same procedure to allow him to check every password in his password dictionary; this is a violation of the security properties cPace is supposed to have, which is that, after a single exchange, the attacker can learn whether one guess to the password is valid, and absolutely nothing else.

The map_to_curve procedures are designed to avoid this - given two points generated by two different passwords, you are unable to determine the relationship between the two (and hence the above attack does not work).

$\endgroup$
3
  • $\begingroup$ That makes sense. I was thinking it should be secure based on the 3-way DH procedure, but I didn't account for the lower entropy of a hashed password. I guess doing this could be made more secure if the hash was replaced with a KDF, but that would be putting a lot of trust into the KDF and be a much less optimal solution. Thanks $\endgroup$ – LRFLEW Dec 20 '20 at 4:38
  • $\begingroup$ After messing with Elligator 2, I have some follow-up questions. I was under the impression that Elligator 2 was used to make make sure points are valid generators, but that isn't the case. Notably, Elligator2(0) = (0, 0), which becomes $I$ in $J$. a) Wouldn't allowing these points weaken the security property? b) Why not just use the modulo-reduced hash as the u-coordinate? $\endgroup$ – LRFLEW Dec 21 '20 at 21:32
  • $\begingroup$ I found the answer to question (b). For anybody coming across this: while all 32-byte u-coordinate encodings are valid for use in ECDH, not all of them encode a point on the curve, but instead encode a point on its twist. $xP$ is a point on the twist iff $P$ is a point on the twist, and it's trivial to test if a point is on the twist. Allowing these points when mapping to the curve leaks information about the password, weakening the security property. I'm still not sure about question (a) yet, though, and even found a few more inputs that result in points of low order. $\endgroup$ – LRFLEW Dec 23 '20 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.