commit 5b0589e9ab121ceb9fe19ede92d15fe86653b921
author Gilles Peskine <Gilles.Peskine@arm.com> Tue Apr 13 21:09:10 2021 +0200
committer Gilles Peskine <Gilles.Peskine@arm.com> Fri Jun 04 14:47:24 2021 +0200
tree 734e6ecd9e63cdcadcc750952458df2d2021476f
parent 0c1a42a14754d97d3a1acf23e337b630f560c8f6

Fix non-constant-time comparison in mbedtls_mpi_random

Calling mbedtls_mpi_cmp_int reveals the number of leading zero limbs
to an adversary who is capable of very fine-grained timing
measurements. This is very little information, but could be practical
with secp521r1 (1/512 chance of the leading limb being 0) if the
adversary can measure the precise timing of a large number of
signature operations.

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

library/bignum.c

diff --git a/library/bignum.c b/library/bignum.c
index c49d63e..b09e8e8 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -2466,9 +2466,10 @@
 {
     int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
     int count;
-    unsigned cmp = 0;
+    unsigned lt_lower = 1, lt_upper = 0;
     size_t n_bits = mbedtls_mpi_bitlen( N );
     size_t n_bytes = ( n_bits + 7 ) / 8;
+    mbedtls_mpi lower_bound;
 
     if( min < 0 )
         return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
@@ -2494,10 +2495,14 @@
      */
     count = ( n_bytes > 4 ? 30 : 250 );
 
+    mbedtls_mpi_init( &lower_bound );
+
     /* Ensure that target MPI has exactly the same number of limbs
      * as the upper bound, even if the upper bound has leading zeros.
      * This is necessary for the mbedtls_mpi_lt_mpi_ct() check. */
     MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, N->n ) );
+    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &lower_bound, N->n ) );
+    MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &lower_bound, min ) );
 
     /*
      * Match the procedure given in RFC 6979 §3.3 (deterministic ECDSA)
@@ -2518,11 +2523,13 @@
             goto cleanup;
         }
 
-        MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, N, &cmp ) );
+        MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, &lower_bound, &lt_lower ) );
+        MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, N, &lt_upper ) );
     }
-    while( mbedtls_mpi_cmp_int( X, min ) < 0 || cmp != 1 );
+    while( lt_lower != 0 || lt_upper == 0 );
 
 cleanup:
+    mbedtls_mpi_free( &lower_bound );
     return( ret );
 }