Accurate RFC 8032 EdDSA verification

[LoupVaillant]

EdDSA signatures are finicky. The basic properties are there, and pretty much every libraries agree on the following:

• Signatures produced in the normal way are always accepted as "valid".
• Signatures produced without knowledge of the private key nor of a previous signature, are always rejected.

Some other details however can cause libraries to disagree about the validity of a signature, and this has caused problems in existing systems & protocols (hoping I’m not forgetting anything):

1. When the public key is low-order, or has a non-trivial low-order component.
2. When the first half of the signature R is low-order, or has a low-order component.
3. When the second half of the signature S is above the prime order L.
4. When the verification equation [8S]B = [8]R + [8h]A is true, but the simplified [S]B = R + [h]A one is false.

Currently, Monocypher:

1. Accepts any public keys as long as they’re on the curve.
2. Accepts any R as long as it’s on the curve.
3. Rejects any S that is above the prime order L.
4. Rejects signatures when [S]B = R + [h]A one is false, even if [8S]B = [8]R + [8h]A is true.

According to section 3.4 of RFC 8032, Monocypher complies with points (1), (2), and (3). The carefully paranoid reader will note that the current code does not include explicit check about R, but the final comparison can only fail if R is not on the curve: that’s because [S]B - [h]A definitely is on the curve, and when serialised will necessarily be different from any R that isn’t.

We do however have a problem with respect to point (4), and I wanted to take the opportunity of the upcoming major version change to correct that. See, we’re a little more strict here than we need to be: with the simplified equation we’re using, if R or A (or both) have a low-order component, that low-order component isn’t supposed to influence the final result. We’re supposed to project everything to the prime-order subgroup and then verify the signature. Or verify the official equation, this has the same effect. Complying here will bring 2 advantages:

1. Full compliance with the RFC, which means full, no-questions-asked interoperability with other libraries that make the same effort. This makes Monocypher easier to replace, and therefore easier to adopt.
2. Performance improvements. I’m thinking of Thomas Pornin’s Lattice based optimisation, which could improve signature verification speed by quite a bit: this optimisation is not possible if we commit to verify the simplified, stricter equation. With the looser equation, we could. Also note that the fastest implementations will likely use this trick, making RFC compliance all the more attractive.

TODO:

• Comply with the RFC and check the official, looser equation.
• Add a carefully crafted set of weird signatures that should be accepted, but currently aren’t.

[fscoto]

Further reading:

• https://hdevalence.ca/blog/2020-10-04-its-25519am
• this entire thread: https://mailarchive.ietf.org/arch/msg/cfrg/fFCiAZiIFAXZP7hjN3KrwwNLJWo/

The entire space is kind of chaotic and apparently no two libraries agree on anything except the most strict checks. It looks like libsodium got more strict and actually caused breakage in some cryptocurrency in doing so. From an end-user perspective (as much as it is inconvenient to depend on someone else's upstream), it would be at least useful to do something any other library does. The spec leaving this much room seems to have ended up being an actual issue.

[LoupVaillant]

Okay, I should have read that piece from Henry de Valance sooner (I knew about it , but was too lazy to find it).

Turns out I was wrong on 2 counts:

• The RFC does not mandate the use of the batched equation described in its section 3.4: sections 5.1.7 and 5.2.7 both explicitly allow the use of the stricter equation.
• There is such a thing as "non-canonical encodings" of A and R, which I have missed. Only 25 points have a non-canonical encoding, and among them only the 6 low-order ones can be used nefariously (exploiting the other 19 requires solving the discrete logarithm problem, good luck with that). The RFC mandates canonical encodings.

Reading de Valence’s article, I see that my points (1), (2), and (3) above are fairly consensual:

• Everyone nowadays stops malleability by mandating that S is below the prime order.
• No one ever checks for low-order components in A and R
• One the other hand, some do reject A if it is low-order.

Divergence & choice then boils down to 3 criteria:

• Reject or accept non-canonical encodings.
• Reject or accept low-order A.
• Use the batch or the strict verification equation.

For our purposes, I believe we must use the batch equation. Yes, it comes at an initial cost (one point addition and 3 points doublings, or perhaps just the addition if we’re clever with comparisons), but the potential optimisation (both Pornin’s and genuine batch optimisation) is in my opinion to important to pass up.

Then there’s whether we should reject low-order A. Libsodium does. The RFC doesn’t. Great.

Finally, the RFC mandates canonical encodings for A and R. Monocypher currently mandates canonical R by accident, as do many other libraries, but that comes from our use of the strict equation. And dammit, explicitly checking for canonical encodings is cumbersome.

Overall, I see 3 option:

1. Batch equation, mandate canonical A and R, reject low-order A (libsodium).
2. Batch equation, mandate canonical A and R, accept low-order A (RFC).
3. Batch equation, allow non-canonical A and R, accept low-order A (Zebra).

I think this is the death knell for the RFC: nobody actually follows it (Bouncy castle does, but it uses the strict equation). This leaves us with libsodium and Zebra. The way I see it, the winner here would be Zebra: allowing non-canonical encodings and low-order keys has absolutely zero impact on security, it’s simpler, and marginally faster. And if compatibility is an issue, it’s probably better to start accepting signatures that were previously rejected, than start rejecting signatures that were previously accepted.

Unless there’s an objection, I think it is best to go for the maximally permissive option (3).

[LoupVaillant]

We still need the test vectors to make sure we're Zebra compatible.