jedisct1 / libhydrogen

A lightweight, secure, easy-to-use crypto library suitable for constrained environments.
https://libhydrogen.org
Other
631 stars 94 forks source link

Fix the `sub` function so it computes the correct result even if the inputs are not the result of a `propagate`. #128

Closed chrisnc closed 2 years ago

chrisnc commented 2 years ago

The way sub is used in STROBE and libhydrogen does not encounter this case because sub is always used on results which have been fully propagated, but if the field arithmetic code were copied and used in another context, this bug may surface.

This was fixed in STROBE here: https://sourceforge.net/p/strobe/code/ci/7d7f605380f573d06484accb61d08c5f4674b35a/

chrisnc commented 2 years ago

The simplest case which fails on the current implementation is 0 - (2^256 - 1). The correct answer is 2^255 - 56, but the code as it is now gives a value that depends on the limb size, as the argument to propagate overflows, and the error depends on the effect of this overflow. For 32-bit limbs, the answer is 4294967259, or 2^32 - 37.

jedisct1 commented 2 years ago

Thank you!