Fix low-probability arithmetic error in ECC
Fix the subtraction in fix_negative, which was incorrectly not looking
for a carry. This caused the result to be wrong when the least
significant limb of N was 0. Fix #4296.
The bug was introduced by d10e8fae9e30cac60297b1e1834002db183429e5
"Optimize fix_negative". Thanks to Philippe Antoine (catenacyber) for
reporting the bug which was found by his EC differential fuzzer.
Credit to OSS-Fuzz.
Signed-off-by: Gilles Peskine <Gilles.Peskine@arm.com>
diff --git a/library/ecp_curves.c b/library/ecp_curves.c
index bf84eff..165c315 100644
--- a/library/ecp_curves.c
+++ b/library/ecp_curves.c
@@ -1041,12 +1041,20 @@
{
size_t i;
- /* Set N := N - 2^bits */
- --N->p[0];
+ /* Set N := 2^bits - 1 - N. We know that 0 <= N < 2^bits, so
+ * set the absolute value to 0xfff...fff - N. There is no carry
+ * since we're subtracting from all-bits-one. */
for( i = 0; i <= bits / 8 / sizeof( mbedtls_mpi_uint ); i++ )
{
N->p[i] = ~(mbedtls_mpi_uint)0 - N->p[i];
}
+ /* Add 1, taking care of the carry. */
+ i = 0;
+ do
+ ++N->p[i];
+ while( N->p[i++] == 0 && i <= bits / 8 / sizeof( mbedtls_mpi_uint ) );
+ /* Invert the sign.
+ * Now N = N0 - 2^bits where N0 is the initial value of N. */
N->s = -1;
/* Add |c| * 2^bits to the absolute value. Since c and N are