Incompatibilities

[fscoto]

The TODO still requires a page outlining incompatibilities between libsodium, I-D.draft-irtf-cfrg-hash-to-curve, Monocypher and Kleshni's implementation.

[LoupVaillant]

The current "known implementations" vaguely points at this incompatibility by noting that Kleshni is incomplete, and libsodium maps to Ed (not curve) 25519.

Another possibility is expanding the page and classify known implementations (and the RFC) by curve, and specifying the parameters of the implementation (Choice for Z, the set of non-negative field elements, and whether representatives are randomly negated or the sign bit randomised).

Note though that the RFC has an unmotivated oddity: for some reason it insists that all bits be used for something "significant". So for Curve25519, instead of ignoring the highest bit they use it to flip the sign of the point, even though it is completely useless (if P has a representative, so does -P). They make it look like this flipping achieves something, while in fact it does not —especially if you consider the fact that the representative comes from a hash.

[LoupVaillant]

Okay, I've looked a libdecaf some, and… if the documentation in its source code is to be believed, it implements a variant of Elligator. The mathematical properties of this new thing however are very close, so it might as well be "Elligator 2 with weird parameters".

A major difference from Monocypher is that the public API directly maps to (and from!) the Ristretto (255 or 448) group. Like Monocypher, the inverse map has a tweak parameter and randomises bits that need to be randomised. Unlike Monocypher, it also adds a random low order point before mapping it, so it does not need a special public key derivation routine. On the plus side, this removes a huge footgun (forgetting to use a "dirty" public key). On the flip side it only works with Ristretto, so you'll have to do your key exchanges in Ristretto space.

[LoupVaillant]

Oops, @fscoto mentioned I forgot about Dalek

[LoupVaillant]

Now that I think of it, Dalek and Libsodium use Elligator, they do not expose it. I genuinely wonder whether they deserved to be mentioned. Libdecaf at least exposes a reversible interface: it may not use Elligator, but what it exposes has basically the same properties.

Now I reckon omitting them would likely be frowned upon, but I believe we need 3 categories instead of the 2 I originally outlined:

• Complete implementations of Elligator: Monocypher, libdecaf.
• Map/Hash to curve implementations: libdecaf, Libsodium, Dalek.
• Incomplete implementations: Kleshni (because it does not provide a way to map from the whole curve).