commit fa85cc2da530ce887e22af3aed04a88b4fa3ba9d
author Gilles Peskine <Gilles.Peskine@arm.com> Mon Jun 08 22:50:35 2020 +0200
committer Gilles Peskine <Gilles.Peskine@arm.com> Tue Jun 09 11:54:20 2020 +0200
tree 0dd6dd2554bcf469b4871f0b3a80d0bf225703c7
parent cc6a6bfda75f0b93f9efe79edebbfd8d0e441e36

mbedtls_mpi_sub_abs: check the range of the result when it happens

The function mbedtls_mpi_sub_abs first checked that A >= B and then
performed the subtraction, relying on the fact that A >= B to
guarantee that the carry propagation would stop, and not taking
advantage of the fact that the carry when subtracting two numbers can
only be 0 or 1. This made the carry propagation code a little hard to
follow.

Write an ad hoc loop for the carry propagation, checking the size of
the result. This makes termination obvious.

The initial check that A >= B is no longer needed, since the function
now checks that the carry propagation terminates, which is equivalent.
This is a slight performance gain.

Signed-off-by: Gilles Peskine <Gilles.Peskine@arm.com>

library/bignum.c

diff --git a/library/bignum.c b/library/bignum.c
index 65f20b3..db46a0e 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -1136,17 +1136,17 @@
 }
 
 /*
- * Unsigned subtraction: X = |A| - |B|  (HAC 14.9)
+ * Unsigned subtraction: X = |A| - |B|  (HAC 14.9, 14.10)
  */
 int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
 {
     mbedtls_mpi TB;
     int ret;
     size_t n;
-    mbedtls_mpi_uint c, z;
+    mbedtls_mpi_uint carry;
 
-    if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
-        return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
+    /* if( mbedtls_mpi_cmp_abs( A, B ) < 0 ) */
+    /*     return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE ); */
 
     mbedtls_mpi_init( &TB );
 
@@ -1170,11 +1170,17 @@
         if( B->p[n - 1] != 0 )
             break;
 
-    c = mpi_sub_hlp( n, X->p, B->p );
-    while( c != 0 )
+    carry = mpi_sub_hlp( n, X->p, B->p );
+    if( carry != 0 )
     {
-        z = ( X->p[n] < c ); X->p[n] -= c;
-        c = z; n++;
+        /* Propagate the carry to the first nonzero limb of X. */
+        for( ; n < X->n && X->p[n] == 0; n++ )
+            --X->p[n];
+        /* If we ran out of space for the carry, it means that the result
+         * is negative. */
+        if( n == X->n )
+            return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
+        --X->p[n];
     }
 
 cleanup: