commit ac12767ff3b8fabd033770015cdb029b12ec24e5
author Manuel Pégourié-Gonnard <manuel.pegourie-gonnard@arm.com> Tue Jun 01 12:06:57 2021 +0200
committer Manuel Pégourié-Gonnard <manuel.pegourie-gonnard@arm.com> Tue Jun 01 12:06:57 2021 +0200
tree c98e69c1625d4647d44c1c8940a2cff526b4456b
parent 7f3f02d2300106d83b2674912a55a8bf41c46550

Fix non-constant-time comparison in mbedtls_ecp_gen_privkey

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: Manuel Pégourié-Gonnard <manuel.pegourie-gonnard@arm.com>

library/ecp.c

diff --git a/library/ecp.c b/library/ecp.c
index 2168981..9db6988 100644
--- a/library/ecp.c
+++ b/library/ecp.c
@@ -3059,6 +3059,11 @@
 {
     int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
     size_t n_size;
+#if defined(ECP_SHORTWEIERSTRASS)
+    mbedtls_mpi one;
+
+    mbedtls_mpi_init( &one );
+#endif
 
     ECP_VALIDATE_RET( grp   != NULL );
     ECP_VALIDATE_RET( d     != NULL );
@@ -3099,7 +3104,10 @@
     {
         /* SEC1 3.2.1: Generate d such that 1 <= n < N */
         int count = 0;
-        unsigned cmp = 0;
+        unsigned lt_lower = 1, lt_upper = 0;
+
+        MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &one, grp->N.n ) );
+        MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &one, 1 ) );
 
         /*
          * Match the procedure given in RFC 6979 (deterministic ECDSA):
@@ -3123,19 +3131,22 @@
              * such as secp224k1 are actually very close to the worst case.
              */
             if( ++count > 30 )
-                return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
-
-            ret = mbedtls_mpi_lt_mpi_ct( d, &grp->N, &cmp );
-            if( ret != 0 )
             {
+                ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
                 goto cleanup;
             }
+
+            MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( d, &grp->N, &lt_upper ) );
+            MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( d, &one, &lt_lower ) );
         }
-        while( mbedtls_mpi_cmp_int( d, 1 ) < 0 || cmp != 1 );
+        while( lt_lower != 0 || lt_upper == 0 );
     }
 #endif /* ECP_SHORTWEIERSTRASS */
 
 cleanup:
+#if defined(ECP_SHORTWEIERSTRASS)
+    mbedtls_mpi_free( &one );
+#endif
     return( ret );
 }