Elligator 2 for indistinguishable from random points

[covert-encryption]

I don't know to which extent you plan to document less well known algorithms, but here is one that is crucial for designing cryptographic formats that do not reveal that they are encrypted text but can still have public key encryption.

While there is some documentation on the Elligator 2 itself, namely a research paper, and while the use of the algorithm is somewhat general knowledge among cryptographic circles, almost no-one knows how to actually implement it securely.

The background is that most formats need to store an ephemeral public key in plain text, and if this is a Curve25519 point, what is stored is a 32-byte value, where the highest bit is always zero, only half of the remaining 255 bit values encode valid points, only 1/8 of those are in the prime group. All these combined, 32 bytes of random data have only 1/32 chance of being a normal public key. An adversary can quickly test for all these things and thus keys can be easily distinguished from random bytes.

Fixing it is a whole lot more complicated than just using Elligator 2 and inserting a few random bits to fill in the blanks. One also has to randomise the subgroups, to avoid only using the prime group, which fortunately stays compatible with standard ECDH (no need to project back to prime group first).

The existing documentation is within Monocypher source code, Covert Encryption source code, and in some Github discussions and old Reddit comments. It would be quite valuable if someone created proper documentation for it, so that not everybody else needs to do the same trial and error that we had to. Let me know if you are interested and I'll collect you the relevant links to get started.

Such documentation could work as a good primer to Ed25519/Curve25519 in general, as all the points can be visualised as a simple rectangle with 8 columns and q rows (~2**252), the low order points on the top row and the prime group on the left column. The neutral element (zero point) is at the top left corner. To hide points, we want to make use of all the columns but still correspond to the standard point on the left column on that same row. It turns out that point add/scalarmult are just adding or multiplying vectors in these rectangle coordinates (columns mod 8, rows mod q), so it can be visualised neatly. The base point is (row 1, column 0) so multiplying it by any number goes to row by that number but stays in the left column.

[fcasal]

Hi @covert-encryption,
At the moment, we are focusing on zero-knowledge proofs and related primitives, but this is something that we would include in our future roadmap.
As you say, Elligator is not the most well known or documented elliptic curve primitive, but there are some excellent resources, namely

• https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve/
• https://www.imperialviolet.org/2013/12/25/elligator.html

[covert-encryption]

Both of those only appear to cover the Elligator 2 itself. Namely, they appear to miss the injection of (possibly randomised) sign and two random padding bits, and more importantly they lack the subgroup randomisation, meaning that even with this encoding the points are just as well if not better distinguishable from random than plain points are (two high bits always zero, sign always zero unless either the Ed25519 sign or a random sign is used in Elligator 2, and even if you do inject three random bits for those, still only subgroup 0 is used and the 7 other subgroups that Elligator 2 also encodes remain unused and easily tested for). As said, nearly no-one understands the real problem. Loup Vaillant, the Monocypher author, did his own research about two years ago to figure all this out.

[covert-encryption]

Testing for subgroup: unhash the Elligator 2 to get the public point, or just skip the Elligator encode/decode cycle. Scalarmult the public key by

q = 2**252 + 27742317777372353535851937790883648493

For any standard point the result is a big fat ZERO (the neutral element). Note that you cannot use libsodium for this test because crypto_scalarmult_ed25519_noclamp bails out when the result is a low order point and won't give you its value. You need a plain scalar multiplication that does no clamping and no error checking. For random bytes, each of the low order points shown below in Ed25519 hex bytes and (x, y) coordinates should be equally common:

0100000000000000000000000000000000000000000000000000000000000000 (0, 1)    # The neutral element (subgroup 0)
26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05 (lx, ly)  # The L generator (subgroup 1)
0000000000000000000000000000000000000000000000000000000000000000 (√-1, 0)
c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a (lx, -ly)
ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff (-0, -1)  # or ...7f (the sign of -0 is irrelevant)
c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa (-lx, -ly)
0000000000000000000000000000000000000000000000000000000000000080 (-√-1, 0)
26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc85 (-lx, ly) # Subgroup 7

# Where the low order generator coordinates (in decimal) are:
lx = 14399317868200118260347934320527232580618823971194345261214217575416788799818
ly = 2707385501144840649318225287225658788936804267575313519463743609750303402022

For any standard point, no matter which scalar (secret key clamped or not) and which sign (randomised or not), you will always get the neutral element. By instead using dirty points (a term coined by Loup Vaillant) with the Elligator 2 (a combination of which, also injecting the extra padding bits, is coined Dirty Elligator 2 by me), you get 32 bytes that actually look random.

In Curve25519 some of the low point values are different (or inencodeable depending on implementation) and because the signs are missing you may only find five possible byte strings but the same principle holds. And the dirty points convert between Ed25519 and Curve25519 just fine using the standard birational equivalency mapping.

And importantly, such dirty points are 100 % compatible with standard ECDH and other algorithms, avoiding the need to undirty them first (by scalar multiplication by q and then subtracting of the dirty point the resulting low order point).