commit 67986d06135c2edcb911123461ee84b2ee639347
author Gilles Peskine <Gilles.Peskine@arm.com> Wed Mar 24 12:25:59 2021 +0100
committer Gilles Peskine <Gilles.Peskine@arm.com> Thu Jun 03 18:10:04 2021 +0200
tree f72d5aa7cde9f74fcf3f7bf32af50a73aac91c57
parent 96449ceebeb3024123ff41bc88a6f275bb602eac

mbedtls_ecp_gen_privkey_mx: make bit manipulations unconditional

Don't calculate the bit-size of the initially generated random number.
This is not necessary to reach the desired distribution of private
keys, and creates a (tiny) side channel opportunity.

This changes the way the result is derived from the random number, but
does not affect the resulting distribution.

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

library/ecp.c

diff --git a/library/ecp.c b/library/ecp.c
index 1592e87..81ba933 100644
--- a/library/ecp.c
+++ b/library/ecp.c
@@ -3065,18 +3065,14 @@
                                 void *p_rng )
 {
     int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
-    size_t b;
     size_t n_bytes = ( high_bit + 7 ) / 8;
 
     /* [Curve25519] page 5 */
     MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( d, n_bytes, f_rng, p_rng ) );
 
-    /* Make sure the most significant bit is high_bit */
-    b = mbedtls_mpi_bitlen( d ); /* mbedtls_mpi_bitlen is one-based */
-    if( b > high_bit + 1 )
-        MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, b - 1 - high_bit ) );
-    else
-        MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, high_bit, 1 ) );
+    /* Make sure the most significant bit is exactly at high_bit */
+    MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( d, 8 * n_bytes - high_bit - 1 ) );
+    MBEDTLS_MPI_CHK( mbedtls_mpi_set_bit( d, high_bit, 1 ) );
 
     /* Make sure the last two bits are unset for Curve448, three bits for
        Curve25519 */

tests/suites/test_suite_ecp.data

diff --git a/tests/suites/test_suite_ecp.data b/tests/suites/test_suite_ecp.data
index 21a7192..5f92ca4 100644
--- a/tests/suites/test_suite_ecp.data
+++ b/tests/suites/test_suite_ecp.data
@@ -277,17 +277,13 @@
 mbedtls_ecp_gen_key:MBEDTLS_ECP_DP_SECP192R1
 
 ECP generate Montgomery key: Curve25519, random in range
-genkey_mx_known_answer:254:"4f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1ef8":"4f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1ef8"
-
-ECP generate Montgomery key: Curve25519, set high bit
-genkey_mx_known_answer:254:"0f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1ef8":"4f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1ef8"
+genkey_mx_known_answer:254:"9e020406080a0c0e10121416181a1c1e20222426282a2c2e30323436383a3df0":"4f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1ef8"
 
 ECP generate Montgomery key: Curve25519, clear higher bit
-## If the bit 255 is set, the library shifts the random number right.
 genkey_mx_known_answer:254:"ff0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1ef8":"7f808101820283038404850586068707880889098a0a8b0b8c0c8d0d8e0e8f78"
 
 ECP generate Montgomery key: Curve25519, clear low bits
-genkey_mx_known_answer:254:"4f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1eff":"4f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1ef8"
+genkey_mx_known_answer:254:"9e020406080a0c0e10121416181a1c1e20222426282a2c2e30323436383a3dff":"4f0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1ef8"
 
 ECP generate Montgomery key: Curve25519, random = all-bits-zero
 genkey_mx_known_answer:254:"0000000000000000000000000000000000000000000000000000000000000000":"4000000000000000000000000000000000000000000000000000000000000000"