search

mratsim / constantine

Constantine: modular, high-performance, zero-dependency cryptography stack for verifiable computation, proof systems and blockchain protocols.
Other
413 stars 44 forks source link

Tentative fix for #345 - constant-time scalar mul with endomorphism acceleration wrong result #346

Closed mratsim closed 10 months ago

mratsim commented 10 months ago

This tentatively fixes #345 with the simple approach explained in https://github.com/mratsim/constantine/issues/345#issuecomment-1899372371 to add an extra bit to hold the decomposed miniscalars.

This will be kept as a fix if we can also relax the requirement for exact bit match for scalarMul_vartime when dispatching to endomorphism.

https://github.com/mratsim/constantine/blob/dbd2630daa6d599a9e78ad247e6858baf41664da/constantine/math/elliptic/ec_scalar_mul_vartime.nim#L353-L377

In that case, we can remove the current way to handle negative mini-scalars by negating the curve point.

mratsim commented 10 months ago

Change of fix approach,

Adding an extra bit also on scalarMul_vartime fails, which suggest the issue is not in the bit length.

When developing endomorphism years ago, the papers didn't special-case Babai's rounding for negative scalars.

Now what's curious is that it has not trigger any error so far in Google Ossfuzz.

mratsim commented 10 months ago

The CI failure is due to some Nim upstream bug when declaring {.noInit.} variables in templates image

Same issue as https://github.com/mratsim/constantine/pull/332#issuecomment-1877982286

Besides removing the {.noInit.}, it may be that using inject solves the issue as well.