(DEPRECATED) A mostly drop in elligator2 for ed25519-donna.

elligator2.h

There used to be something that resembled an Elligator2 implementation here ported from agl's
Go code.  The implementation is unmaintained and has severe issues (as pointed out in a comment),
and should not be used for anything.

Hi,

Can't post an issue in libelligator (it's archived), so here it goes.

The problem

There's a critical bug in libelligator, that defeats the entire purpose of using Elligator to begin with: the inverse map only generates points in the prime order subgroup of the curve (cofactor index zero), and that bias is easily detectable. See, Elligator maps to all points in the curve, including those that are not on the prime order subgroup. (Recall that Curve25519 has order 8×L, where L is a big freaking prime number, and 8 is the "cofactor". We often say the curve has order L because L determines the security of the curve, but that's kind of a misnomer in group theory.)

The current file avoids the issue by taking an X25519 public key directly, but that just pushes the problem onto your users: by default, X25519 public keys have a cleared cofactor, and the same bias will apply. They need a random public key where the cofactor is not cleared, and that requires some dedicated code.

The cofactor index of a point in the curve is easily found with a scalar multiplication by L. This clears the main factor, and only a point of low order remains (the cofactor is 8, so there are 8 possibilities). Since all the points you generate have cofactor zero, that scalar multiplication will yield the zero point, every time. Such a verification is more expensive than just checking whether the v coordinate of the point is a square, but it yields 3 bits of information instead of just one.

In addition, the clamped scalar multiplication causes you to explore only half the key space. That is arguably not a big deal, but you may want to flip the sign of the v coordinate at random to cover (almost) all points on the prime order subgroup.

The solution

Enough grim news, here comes salvation.

Covering the whole curve is easy: just add a low order point at random after the scalar multiplication. Alternatively, you could change the base point for one that has order 8*L (the canonical base point only has order L), and don't clamp the 3 least significant bits of the scalar (so you don't clear the cofactor). Both methods are equivalent, and can even be compared. The final addition has the advantage of leveraging Fixed based scalar multiplication in Edwards space (much faster), and changing the base point allows us to reuse the Montgomery ladder, and significantly reduce code footprint (for users who don't do signatures).

You may also want to select the sign of the v coordinate at random, instead of computing it. It will allow you to cover the whole curve (instead of just half of it, though there is no known fast method to detect that bias), and avoid some conversion work (you can ignore the Edwards x coordinate altogether).

Note that regular X22519 key exchange clears the cofactor, so those weird public keys will still be compatible with it.

---

Some simplifications are possible.

• The comparison to (p-1)/2 can be replaced by a field addition, then you just check whether the result is odd. This is a neat effect with overflow, where the only way for 2x to be odd is for x to exceed (p-1)/2.
• You could have an "inverse square root" function and leverage it. The details are a bit complicated, but long story short, you don't need to implement chi(), everything becomes much simpler, and the direct map (from representative to point) can be computed with a single exponentiation.

---

Note for outsiders: I'm working on Monocypher, a general purpose crypto library that will very soon have Elligator2 support (we already have working code in the GitHub repository).

Thanks for letting me know. I don't really have the time or energy to fix this, and I'm no longer doing circumvention work, but I'll edit the gist or something to a warning label a la what agl did.

Works for me, thanks.