Fix Edge Case when H = 0 in Shamir-Strauss

[nlordell]

This PR fixes an edge case in Shamir-Strauss when H = 0. This can happen for a very specific private key (n - 1).

Previously, the loop would continue when T4 == 0, i.e. when both u and v bits were 0 at the current index. The proposed change is to first compute the T1 and T2

I also changed the code to be branchless - which should improve gas consumption and code size (PUSH + IF + JUMP + JUMPDEST is 3 + 2 + 8 + 1 gas while MUL + MUL is only 5 + 5); however, if there are a lot of 0s to skip, then the previous implementation would have slightly better characteristics as it would continue from the loop sooner.

Added a test case to verify the fix works.

[rdubois-crypto]

Hey, thx a lot for the Dbl fix, i spotted it but you were the fastest !

For the H=0, i was thinking to replace uG+vQ = uG - vG= (u-v mod n).G, ie replacing u by u-v, and v by 0 by testing value of H: if(H[0]=0&&H[1]==0) u=addmod(u, n-v,n) v=0 (no need to reaffect H as it will never be selected then).

Cause i'm not sure fixing the index is enough, as the Neutral Point is problematic when not specifically adressed in the loop.

[rdubois-crypto]

As an interesting fact if you ever looked at the precomputations version, it also means that 256 keys are 'flawed keys' that would make the use of precomputation fail. I will modify the precomputation generation accordingly (handled by the front)

Those value cannot be reached by fuzzing cause they imply multiples of (2^128)G and (2^128)Q. While i'm already stunned by the fact that forge fuzzer was able to spot edge cases while wychproof cannot, it is a bit too much to ask here.

While solving H=0 is only two lines of code and worth being handled, testing all 256 precomputed value would end up as a nightmare. In any case a predictible value for a public key shall be forbidden.

[nlordell]

Ooo, clever fix.

As an interesting fact if you ever looked at the precomputations version

🙈, I just checked (as I didn't look into the precomputed versions originally) and I think I missed the ecZZ_Dbl fix for the other addaddmul implementations. Just letting you know as I think there is some drift right now between the different versions of the function. I can propose a PR but only be able to do so sometime next week, so feel free to front-run me in the meantime.

[rdubois-crypto]

I will. As a note to avoid to just cover your PR with a stupid lint, there is a make lint-write in the commands making sure that lint gonna be ok (i forgot it myself half of the time).

[rdubois-crypto]

Handled with above trick in PR#56