Merge remote-tracking branch 'origin/mbedtls-2.16' into mbedtls-2.16-restricted
* origin/mbedtls-2.16:
Fix some pylint warnings
Enable more test cases without MBEDTLS_MEMORY_DEBUG
More accurate test case description
Clarify that the "FATAL" message is expected
Note that mbedtls_ctr_drbg_seed() must not be called twice
Fix CTR_DRBG benchmark
Changelog entry for xxx_drbg_set_entropy_len before xxx_drbg_seed
CTR_DRBG: support set_entropy_len() before seed()
CTR_DRBG: Don't use functions before they're defined
HMAC_DRBG: support set_entropy_len() before seed()
diff --git a/ChangeLog b/ChangeLog
index 2f2afb7..b8dc65c 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,6 +1,29 @@
mbed TLS ChangeLog (Sorted per branch, date)
-= mbed TLS 2.16.x branch released xxxx-xx-xx
+= mbed TLS 2.16.4 branch released 2020-01-15
+
+Security
+ * Fix side channel vulnerability in ECDSA. Our bignum implementation is not
+ constant time/constant trace, so side channel attacks can retrieve the
+ blinded value, factor it (as it is smaller than RSA keys and not guaranteed
+ to have only large prime factors), and then, by brute force, recover the
+ key. Reported by Alejandro Cabrera Aldaya and Billy Brumley.
+ * Zeroize local variables in mbedtls_internal_aes_encrypt() and
+ mbedtls_internal_aes_decrypt() before exiting the function. The value of
+ these variables can be used to recover the last round key. To follow best
+ practice and to limit the impact of buffer overread vulnerabilities (like
+ Heartbleed) we need to zeroize them before exiting the function.
+ Issue reported by Tuba Yavuz, Farhaan Fowze, Ken (Yihang) Bai,
+ Grant Hernandez, and Kevin Butler (University of Florida) and
+ Dave Tian (Purdue University).
+ * Fix side channel vulnerability in ECDSA key generation. Obtaining precise
+ timings on the comparison in the key generation enabled the attacker to
+ learn leading bits of the ephemeral key used during ECDSA signatures and to
+ recover the private key. Reported by Jeremy Dubeuf.
+ * Catch failure of AES functions in mbedtls_ctr_drbg_random(). Uncaught
+ failures could happen with alternative implementations of AES. Bug
+ reported and fix proposed by Johan Uppman Bruce and Christoffer Lauri,
+ Sectra.
Bugfix
* Remove redundant line for getting the bitlen of a bignum, since the variable
diff --git a/include/mbedtls/bignum.h b/include/mbedtls/bignum.h
index 1c86072..22b3731 100644
--- a/include/mbedtls/bignum.h
+++ b/include/mbedtls/bignum.h
@@ -184,7 +184,7 @@
*/
typedef struct mbedtls_mpi
{
- int s; /*!< integer sign */
+ int s; /*!< Sign: -1 if the mpi is negative, 1 otherwise */
size_t n; /*!< total # of limbs */
mbedtls_mpi_uint *p; /*!< pointer to limbs */
}
@@ -560,6 +560,24 @@
int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y );
/**
+ * \brief Check if an MPI is less than the other in constant time.
+ *
+ * \param X The left-hand MPI. This must point to an initialized MPI
+ * with the same allocated length as Y.
+ * \param Y The right-hand MPI. This must point to an initialized MPI
+ * with the same allocated length as X.
+ * \param ret The result of the comparison:
+ * \c 1 if \p X is less than \p Y.
+ * \c 0 if \p X is greater than or equal to \p Y.
+ *
+ * \return 0 on success.
+ * \return MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the allocated length of
+ * the two input MPIs is not the same.
+ */
+int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X, const mbedtls_mpi *Y,
+ unsigned *ret );
+
+/**
* \brief Compare an MPI with an integer.
*
* \param X The left-hand MPI. This must point to an initialized MPI.
diff --git a/library/aes.c b/library/aes.c
index aff0a99..02a7986 100644
--- a/library/aes.c
+++ b/library/aes.c
@@ -918,6 +918,18 @@
PUT_UINT32_LE( X2, output, 8 );
PUT_UINT32_LE( X3, output, 12 );
+ mbedtls_platform_zeroize( &X0, sizeof( X0 ) );
+ mbedtls_platform_zeroize( &X1, sizeof( X1 ) );
+ mbedtls_platform_zeroize( &X2, sizeof( X2 ) );
+ mbedtls_platform_zeroize( &X3, sizeof( X3 ) );
+
+ mbedtls_platform_zeroize( &Y0, sizeof( Y0 ) );
+ mbedtls_platform_zeroize( &Y1, sizeof( Y1 ) );
+ mbedtls_platform_zeroize( &Y2, sizeof( Y2 ) );
+ mbedtls_platform_zeroize( &Y3, sizeof( Y3 ) );
+
+ mbedtls_platform_zeroize( &RK, sizeof( RK ) );
+
return( 0 );
}
#endif /* !MBEDTLS_AES_ENCRYPT_ALT */
@@ -986,6 +998,18 @@
PUT_UINT32_LE( X2, output, 8 );
PUT_UINT32_LE( X3, output, 12 );
+ mbedtls_platform_zeroize( &X0, sizeof( X0 ) );
+ mbedtls_platform_zeroize( &X1, sizeof( X1 ) );
+ mbedtls_platform_zeroize( &X2, sizeof( X2 ) );
+ mbedtls_platform_zeroize( &X3, sizeof( X3 ) );
+
+ mbedtls_platform_zeroize( &Y0, sizeof( Y0 ) );
+ mbedtls_platform_zeroize( &Y1, sizeof( Y1 ) );
+ mbedtls_platform_zeroize( &Y2, sizeof( Y2 ) );
+ mbedtls_platform_zeroize( &Y3, sizeof( Y3 ) );
+
+ mbedtls_platform_zeroize( &RK, sizeof( RK ) );
+
return( 0 );
}
#endif /* !MBEDTLS_AES_DECRYPT_ALT */
diff --git a/library/bignum.c b/library/bignum.c
index 7a700bc..6713bcb 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -1071,6 +1071,107 @@
return( 0 );
}
+/** Decide if an integer is less than the other, without branches.
+ *
+ * \param x First integer.
+ * \param y Second integer.
+ *
+ * \return 1 if \p x is less than \p y, 0 otherwise
+ */
+static unsigned ct_lt_mpi_uint( const mbedtls_mpi_uint x,
+ const mbedtls_mpi_uint y )
+{
+ mbedtls_mpi_uint ret;
+ mbedtls_mpi_uint cond;
+
+ /*
+ * Check if the most significant bits (MSB) of the operands are different.
+ */
+ cond = ( x ^ y );
+ /*
+ * If the MSB are the same then the difference x-y will be negative (and
+ * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
+ */
+ ret = ( x - y ) & ~cond;
+ /*
+ * If the MSB are different, then the operand with the MSB of 1 is the
+ * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
+ * the MSB of y is 0.)
+ */
+ ret |= y & cond;
+
+
+ ret = ret >> ( biL - 1 );
+
+ return (unsigned) ret;
+}
+
+/*
+ * Compare signed values in constant time
+ */
+int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X, const mbedtls_mpi *Y,
+ unsigned *ret )
+{
+ size_t i;
+ /* The value of any of these variables is either 0 or 1 at all times. */
+ unsigned cond, done, X_is_negative, Y_is_negative;
+
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( Y != NULL );
+ MPI_VALIDATE_RET( ret != NULL );
+
+ if( X->n != Y->n )
+ return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
+
+ /*
+ * Set sign_N to 1 if N >= 0, 0 if N < 0.
+ * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
+ */
+ X_is_negative = ( X->s & 2 ) >> 1;
+ Y_is_negative = ( Y->s & 2 ) >> 1;
+
+ /*
+ * If the signs are different, then the positive operand is the bigger.
+ * That is if X is negative (X_is_negative == 1), then X < Y is true and it
+ * is false if X is positive (X_is_negative == 0).
+ */
+ cond = ( X_is_negative ^ Y_is_negative );
+ *ret = cond & X_is_negative;
+
+ /*
+ * This is a constant-time function. We might have the result, but we still
+ * need to go through the loop. Record if we have the result already.
+ */
+ done = cond;
+
+ for( i = X->n; i > 0; i-- )
+ {
+ /*
+ * If Y->p[i - 1] < X->p[i - 1] then X < Y is true if and only if both
+ * X and Y are negative.
+ *
+ * Again even if we can make a decision, we just mark the result and
+ * the fact that we are done and continue looping.
+ */
+ cond = ct_lt_mpi_uint( Y->p[i - 1], X->p[i - 1] );
+ *ret |= cond & ( 1 - done ) & X_is_negative;
+ done |= cond;
+
+ /*
+ * If X->p[i - 1] < Y->p[i - 1] then X < Y is true if and only if both
+ * X and Y are positive.
+ *
+ * Again even if we can make a decision, we just mark the result and
+ * the fact that we are done and continue looping.
+ */
+ cond = ct_lt_mpi_uint( X->p[i - 1], Y->p[i - 1] );
+ *ret |= cond & ( 1 - done ) & ( 1 - X_is_negative );
+ done |= cond;
+ }
+
+ return( 0 );
+}
+
/*
* Compare signed values
*/
diff --git a/library/ctr_drbg.c b/library/ctr_drbg.c
index 32b34e4..ad0a193 100644
--- a/library/ctr_drbg.c
+++ b/library/ctr_drbg.c
@@ -512,7 +512,7 @@
exit:
mbedtls_platform_zeroize( add_input, sizeof( add_input ) );
mbedtls_platform_zeroize( tmp, sizeof( tmp ) );
- return( 0 );
+ return( ret );
}
int mbedtls_ctr_drbg_random( void *p_rng, unsigned char *output, size_t output_len )
diff --git a/library/ecdsa.c b/library/ecdsa.c
index 2b48006..3cf3d7c 100644
--- a/library/ecdsa.c
+++ b/library/ecdsa.c
@@ -363,6 +363,7 @@
MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &e, &e, s ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &e, &e, &t ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( pk, pk, &t ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( pk, pk, &grp->N ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( s, pk, &grp->N ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, s, &e ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( s, s, &grp->N ) );
diff --git a/library/ecp.c b/library/ecp.c
index db36191..040c20b 100644
--- a/library/ecp.c
+++ b/library/ecp.c
@@ -2724,6 +2724,7 @@
{
/* SEC1 3.2.1: Generate d such that 1 <= n < N */
int count = 0;
+ unsigned cmp = 0;
/*
* Match the procedure given in RFC 6979 (deterministic ECDSA):
@@ -2748,9 +2749,14 @@
*/
if( ++count > 30 )
return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
+
+ ret = mbedtls_mpi_lt_mpi_ct( d, &grp->N, &cmp );
+ if( ret != 0 )
+ {
+ goto cleanup;
+ }
}
- while( mbedtls_mpi_cmp_int( d, 1 ) < 0 ||
- mbedtls_mpi_cmp_mpi( d, &grp->N ) >= 0 );
+ while( mbedtls_mpi_cmp_int( d, 1 ) < 0 || cmp != 1 );
}
#endif /* ECP_SHORTWEIERSTRASS */
diff --git a/tests/suites/test_suite_mpi.data b/tests/suites/test_suite_mpi.data
index 425e93a..4d46ca7 100644
--- a/tests/suites/test_suite_mpi.data
+++ b/tests/suites/test_suite_mpi.data
@@ -163,6 +163,93 @@
Base test mbedtls_mpi_cmp_mpi (Mixed values) #6
mbedtls_mpi_cmp_mpi:10:"-2":10:"31231231289798":-1
+Base test mbedtls_mpi_lt_mpi_ct #1
+mbedtls_mpi_lt_mpi_ct:1:"2B5":1:"2B5":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct #2
+mbedtls_mpi_lt_mpi_ct:1:"2B5":1:"2B4":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct #3
+mbedtls_mpi_lt_mpi_ct:1:"2B5":1:"2B6":1:0
+
+Base test mbedtls_mpi_lt_mpi_ct (Negative values) #1
+mbedtls_mpi_lt_mpi_ct:1:"-2":1:"-2":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (Negative values) #2
+mbedtls_mpi_lt_mpi_ct:1:"-2":1:"-3":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (Negative values) #3
+mbedtls_mpi_lt_mpi_ct:1:"-2":1:"-1":1:0
+
+Base test mbedtls_mpi_lt_mpi_ct (Mixed values) #1
+mbedtls_mpi_lt_mpi_ct:1:"-3":1:"2":1:0
+
+Base test mbedtls_mpi_lt_mpi_ct (Mixed values) #2
+mbedtls_mpi_lt_mpi_ct:1:"2":1:"-3":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (Mixed values) #3
+mbedtls_mpi_lt_mpi_ct:2:"-2":2:"1C67967269C6":1:0
+
+Base test mbedtls_mpi_lt_mpi_ct (X is longer in storage)
+mbedtls_mpi_lt_mpi_ct:3:"2B5":2:"2B5":0:MBEDTLS_ERR_MPI_BAD_INPUT_DATA
+
+Base test mbedtls_mpi_lt_mpi_ct (Y is longer in storage)
+mbedtls_mpi_lt_mpi_ct:3:"2B5":4:"2B5":0:MBEDTLS_ERR_MPI_BAD_INPUT_DATA
+
+Base test mbedtls_mpi_lt_mpi_ct (corner case - 64 bit) #1
+mbedtls_mpi_lt_mpi_ct:2:"7FFFFFFFFFFFFFFF":2:"FF":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (corner case - 64 bit) #2
+mbedtls_mpi_lt_mpi_ct:2:"8000000000000000":2:"7FFFFFFFFFFFFFFF":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (corner case - 64 bit) #3
+mbedtls_mpi_lt_mpi_ct:2:"8000000000000000":2:"1":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (corner case - 64 bit) #4
+mbedtls_mpi_lt_mpi_ct:2:"8000000000000000":2:"0":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (corner case - 64 bit) #5
+mbedtls_mpi_lt_mpi_ct:2:"FFFFFFFFFFFFFFFF":2:"FF":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (corner case - 32 bit) #1
+mbedtls_mpi_lt_mpi_ct:1:"7FFFFFFF":1:"FF":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (corner case - 32 bit) #2
+mbedtls_mpi_lt_mpi_ct:1:"80000000":1:"7FFFFFFF":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (corner case - 32 bit) #3
+mbedtls_mpi_lt_mpi_ct:1:"80000000":1:"1":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (corner case - 32 bit) #4
+mbedtls_mpi_lt_mpi_ct:1:"80000000":1:"0":0:0
+
+Base test mbedtls_mpi_lt_mpi_ct (corner case - 32 bit) #5
+mbedtls_mpi_lt_mpi_ct:1:"FFFFFFFF":1:"FF":0:0
+
+Multi-limb mbedtls_mpi_lt_mpi_ct (X<Y, zero vs non-zero MS limb)
+mbedtls_mpi_lt_mpi_ct:2:"0FFFFFFFFFFFFFFFF":2:"1FFFFFFFFFFFFFFFF":1:0
+
+Multi-limb mbedtls_mpi_lt_mpi_ct (X>Y, equal MS limbs)
+mbedtls_mpi_lt_mpi_ct:2:"-EEFFFFFFFFFFFFFFF1":2:"-EEFFFFFFFFFFFFFFFF":0:0
+
+Multi-limb mbedtls_mpi_lt_mpi_ct (X=Y)
+mbedtls_mpi_lt_mpi_ct:2:"EEFFFFFFFFFFFFFFFF":2:"EEFFFFFFFFFFFFFFFF":0:0
+
+Multi-limb mbedtls_mpi_lt_mpi_ct (X=-Y)
+mbedtls_mpi_lt_mpi_ct:2:"-EEFFFFFFFFFFFFFFFF":2:"EEFFFFFFFFFFFFFFFF":1:0
+
+Multi-limb mbedtls_mpi_lt_mpi_ct (Alternating limbs) #1
+mbedtls_mpi_lt_mpi_ct:2:"11FFFFFFFFFFFFFFFF":2:"FF1111111111111111":1:0
+
+Multi-limb mbedtls_mpi_lt_mpi_ct (Alternating limbs) #2
+mbedtls_mpi_lt_mpi_ct:2:"FF1111111111111111":2:"11FFFFFFFFFFFFFFFF":0:0
+
+Multi-limb mbedtls_mpi_lt_mpi_ct (Alternating limbs) #3
+mbedtls_mpi_lt_mpi_ct:2:"-11FFFFFFFFFFFFFFFF":2:"-FF1111111111111111":0:0
+
+Multi-limb mbedtls_mpi_lt_mpi_ct (Alternating limbs) #4
+mbedtls_mpi_lt_mpi_ct:2:"-FF1111111111111111":2:"-11FFFFFFFFFFFFFFFF":1:0
+
Base test mbedtls_mpi_cmp_abs #1
mbedtls_mpi_cmp_abs:10:"693":10:"693":0
diff --git a/tests/suites/test_suite_mpi.function b/tests/suites/test_suite_mpi.function
index f982385..97c338b 100644
--- a/tests/suites/test_suite_mpi.function
+++ b/tests/suites/test_suite_mpi.function
@@ -538,6 +538,31 @@
/* END_CASE */
/* BEGIN_CASE */
+void mbedtls_mpi_lt_mpi_ct( int size_X, char * input_X,
+ int size_Y, char * input_Y,
+ int input_ret, int input_err )
+{
+ unsigned ret;
+ unsigned input_uret = input_ret;
+ mbedtls_mpi X, Y;
+ mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y );
+
+ TEST_ASSERT( mbedtls_mpi_read_string( &X, 16, input_X ) == 0 );
+ TEST_ASSERT( mbedtls_mpi_read_string( &Y, 16, input_Y ) == 0 );
+
+ mbedtls_mpi_grow( &X, size_X );
+ mbedtls_mpi_grow( &Y, size_Y );
+
+ TEST_ASSERT( mbedtls_mpi_lt_mpi_ct( &X, &Y, &ret ) == input_err );
+ if( input_err == 0 )
+ TEST_ASSERT( ret == input_uret );
+
+exit:
+ mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y );
+}
+/* END_CASE */
+
+/* BEGIN_CASE */
void mbedtls_mpi_cmp_abs( int radix_X, char * input_X, int radix_Y,
char * input_Y, int input_A )
{