Fuzzing #54
Description
A a minimum we need to add fuzzing to Hash-To-Curve as we might receive forged messages that might trigger edge cases.
One nice thing is that Milagro is using Exception-Free Addition formulas that fail to handle infinity points and for a point P(x, y) that needs special handling of Q(x, y) or Q(x, -y)
The issue stems from Short Weierstrass Addition law
P + Q = R (Px, Py) + (Qx, Qy) = (Rx, Ry) with Rx = λ² - Px - Qx Ry = λ(Px - Rx) - Py with `λ = (Qy - Py) / (Px - Qx)` which would divide by 0 if Px == Qx
For actual elliptic curve testing, it's quite probably the a fuzzer won't be able to create valid elliptic curve points (though AFL learned to create valid jpegs from nothing but fuzzing https://lcamtuf.blogspot.com/2014/11/pulling-jpegs-out-of-thin-air.html) so we will need to turn to differential fuzzing.
Thankfully there is a host of alternative implementations that we can use and that are sufficiently fast:
- Herumi's MCL - https://github.com/herumi/mcl
- Milagro Rust - https://github.com/sigp/milagro_bls
- Goff - https://github.com/ConsenSys/goff
- Algorand pairing (fork of Zcash that is 100x faster?? - https://github.com/algorand/pairing-plus
And somewhat slower:
- Zcash BLS12-381 - https://github.com/zcash/librustzcash
- Formally-verified BLS12-381 from fiat-crypto: https://github.com/mratsim/constantine/blob/ff9dec48/formal_verification/bls12_381_q_64.c