Reviewing carry propagation in elliptic curves

[LoupVaillant]

Elliptic curves in Monocypher have a couple loose ends. The invariants of the different operations, as well as their respective delayed carry chains, have not been ascertained. I initially leaned on the ref10 implementation to ensure correctness, but Monocypher is now sufficiently different that an independent review is needed.

Ideally, we need a proof of correctness just like the one for Poly1305. Realistically, limiting the analysis to carry propagation is probably sufficient. Two points stand out:

• The multiplication by 973324 uses the same carry than the multiplication by 121666, but since a bigger number is involved, the carry must be double checked.
• The data flow of EdDSA, has not been reviewed for addition chains. The ref10 invariants mean we should not have more than 2 additions before a multiplication. We should ensure that this is the case.

I am sufficiently uncertain about the utter absence of carry related bugs that I hereby suspend the Bounty program for carry propagation bugs on elliptic curves. This partial suspension will lift when the verification is done, and this issue closed.

[LoupVaillant]

The suspicion of possible carry propagation bug is greater than ever before…

I've just added a full pre-computed table for EdDSA signatures. You will note that elements 7, 10, and 13 look odd. This is because unlike the rest of the table, I did not perform full carry propagation.

When I do fully carry-propagate any one of those elements, signatures fail catastrophically. I have two hypotheses:

• EdDSA code does not respect the invariants of field arithmetic. Like, too many additions before a multiplication (and subsequent carry propagation).
• Field arithmetic need constants & inputs to go through a special kind of carry propagation, that minimises the absolute value of the limb, instead of making sure it is always positive like I do.

Either way, the current code cannot be tagged into any kind of official release. More analysis is needed first. (And if it turns out the constants are to blame, we need to revert this patch as well).

[LoupVaillant]

OK, turned out the problem was constants with bogus carry propagation. It's corrected now.

Now the multiplication by 973324 is gone, but we still need to analyse the addition chains.

[LoupVaillant]

Carry propagation has now been mechanically checked in the carry-propagation branch. We rely on the invariant documented in the ref10 implementation, the checks just verify we do not exceed boundaries.

If public key cryptography changes again, those changes must be merged to the carry-propagation branch, so we can check them.

At last, we can close this.