AGL's Elligator Code Might be Flawed

[Daeinar]

@isislovecruft and @hdevalence notified me that AGL's Elligator code might be flawed and thus should not be used. We should follow up with them on the exact details. A good documentation for Elligator that could be used for a reimplementation is https://whispersystems.org/docs/specifications/xeddsa/#hashing-to-a-point-with-elligator-2.

[liamsi]

Interesting! Could you provide me the details about the potential flaw (later)?

In coniks-go we also use AGL's implementation... We started switching to vxeddsa anyways. But currently I kept both elligator implementations: AGL's and one I wrote that aims to follow whispersystem's specs: https://github.com/coniks-sys/coniks-go/blob/vxeddsa/crypto/internal/ed25519/extra25519/extra25519.go#L396
I didn't have the time to do more testing yet but ran against a bunch of test-vectors (and both implementations yielded the same results/hashes).

[Daeinar]

@liamsi Unfortunately, I haven't had the time yet to check the details but yes, as soon as I know more, I let you know.

[riobard]

@Daeinar Is there any progress on this issue? I found two related issues agl/ed25519#12 and Yawning/libelligator#1

[nikkolasg]

Hi, thanks for the relevant links. We haven't worked on this issue so far but it is still something we plan to address in the future. Looking at Yawning's commit, it should not be too much of a hassle.

[isislovecruft]

The issue I found was separate to Yawning's issue. The code on lines 104-107 of extra25519.go:

var inv1 edwards25519.FieldElement
edwards25519.FeSub(&inv1, &A.Z, &A.Y)
edwards25519.FeMul(&inv1, &inv1, &A.X)
edwards25519.FeInvert(&inv1, &inv1)

calculates 1/X(Z-Y) whereas the reasoning in Adam's blogpost (which seemed to check out when I worked through it) states:

By calculating just 1/(X(Y-Z)), we can get (u,v).

Although the implementation does roundtrip, so either there is a second coordinate swap somewhere or I'm wrong (and the blogpost has a minor typo). (I haven't taken the time to hunt for a second coordinate swap, but if someone does I'd be very interested to hear about it.)

The other interesting thing I noted was that both Adam's implementation uses sqrt(-A + 2) = sqrt(-486664) in two places where this should have been interpreted as being sqrt(-486660), which is perhaps related to Yawning's issue but I don't really care enough to re-read that horrid† paper.

† To be clear: I do not believe any of the "mistakes" in, or differences between, any of the existent elligator2 implementations to be the fault of any of the implementors. With no offence meant towards the sole author who eventually made a nice implementation, the original paper is quite frankly one of the worst written academic papers I've ever tried (dozens of times) to read, in any field. The student should have done better, the advisors should have done their actual fucking jobs, the peer reviewers should have demanded better, and the student should have been asked to provide an open-sourced reference implementation and test vectors.

[jeffallen]

We should remove Hiding for v3, because we suspect it is not implemented correctly. If a student needs to use point hiding in the coming year, they will need to implement it themselves correctly, and then we'll see about integrating their work back into Kyber later.