Merge pull request #728 from mpg/ct-varlen-hmac-2.16
[Backport 2.16] Add constant-flow variable-length HMAC function
diff --git a/ChangeLog.d/protect-base-blinding.txt b/ChangeLog.d/protect-base-blinding.txt
new file mode 100644
index 0000000..ca0600c
--- /dev/null
+++ b/ChangeLog.d/protect-base-blinding.txt
@@ -0,0 +1,6 @@
+Security
+ * Fix side channel in RSA private key operations and static (finite-field)
+ Diffie-Hellman. An adversary with precise enough timing and memory access
+ information (typically an untrusted operating system attacking a secure
+ enclave) could bypass an existing counter-measure (base blinding) and
+ potentially fully recover the private key.
diff --git a/library/dhm.c b/library/dhm.c
index f8d367e..5396deb 100644
--- a/library/dhm.c
+++ b/library/dhm.c
@@ -351,6 +351,32 @@
}
/*
+ * Pick a random R in the range [2, M) for blinding purposes
+ */
+static int dhm_random_below( mbedtls_mpi *R, const mbedtls_mpi *M,
+ int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
+{
+ int ret, count;
+
+ count = 0;
+ do
+ {
+ MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( R, mbedtls_mpi_size( M ), f_rng, p_rng ) );
+
+ while( mbedtls_mpi_cmp_mpi( R, M ) >= 0 )
+ MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( R, 1 ) );
+
+ if( count++ > 10 )
+ return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
+ }
+ while( mbedtls_mpi_cmp_int( R, 1 ) <= 0 );
+
+cleanup:
+ return( ret );
+}
+
+
+/*
* Use the blinding method and optimisation suggested in section 10 of:
* KOCHER, Paul C. Timing attacks on implementations of Diffie-Hellman, RSA,
* DSS, and other systems. In : Advances in Cryptology-CRYPTO'96. Springer
@@ -359,7 +385,10 @@
static int dhm_update_blinding( mbedtls_dhm_context *ctx,
int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
{
- int ret, count;
+ int ret;
+ mbedtls_mpi R;
+
+ mbedtls_mpi_init( &R );
/*
* Don't use any blinding the first time a particular X is used,
@@ -394,24 +423,23 @@
*/
/* Vi = random( 2, P-1 ) */
- count = 0;
- do
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &ctx->Vi, mbedtls_mpi_size( &ctx->P ), f_rng, p_rng ) );
+ MBEDTLS_MPI_CHK( dhm_random_below( &ctx->Vi, &ctx->P, f_rng, p_rng ) );
- while( mbedtls_mpi_cmp_mpi( &ctx->Vi, &ctx->P ) >= 0 )
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &ctx->Vi, 1 ) );
+ /* Vf = Vi^-X mod P
+ * First compute Vi^-1 = R * (R Vi)^-1, (avoiding leaks from inv_mod),
+ * then elevate to the Xth power. */
+ MBEDTLS_MPI_CHK( dhm_random_below( &R, &ctx->P, f_rng, p_rng ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx->Vf, &ctx->Vi, &R ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx->Vf, &ctx->Vf, &ctx->P ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &ctx->Vf, &ctx->Vf, &ctx->P ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx->Vf, &ctx->Vf, &R ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx->Vf, &ctx->Vf, &ctx->P ) );
- if( count++ > 10 )
- return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
- }
- while( mbedtls_mpi_cmp_int( &ctx->Vi, 1 ) <= 0 );
-
- /* Vf = Vi^-X mod P */
- MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &ctx->Vf, &ctx->Vi, &ctx->P ) );
MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &ctx->Vf, &ctx->Vf, &ctx->X, &ctx->P, &ctx->RP ) );
cleanup:
+ mbedtls_mpi_free( &R );
+
return( ret );
}
diff --git a/library/rsa.c b/library/rsa.c
index af1cef6..06388ad 100644
--- a/library/rsa.c
+++ b/library/rsa.c
@@ -808,6 +808,9 @@
int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
{
int ret, count = 0;
+ mbedtls_mpi R;
+
+ mbedtls_mpi_init( &R );
if( ctx->Vf.p != NULL )
{
@@ -823,18 +826,41 @@
/* Unblinding value: Vf = random number, invertible mod N */
do {
if( count++ > 10 )
- return( MBEDTLS_ERR_RSA_RNG_FAILED );
+ {
+ ret = MBEDTLS_ERR_RSA_RNG_FAILED;
+ goto cleanup;
+ }
MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &ctx->Vf, ctx->len - 1, f_rng, p_rng ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &ctx->Vi, &ctx->Vf, &ctx->N ) );
- } while( mbedtls_mpi_cmp_int( &ctx->Vi, 1 ) != 0 );
- /* Blinding value: Vi = Vf^(-e) mod N */
- MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &ctx->Vi, &ctx->Vf, &ctx->N ) );
+ /* Compute Vf^-1 as R * (R Vf)^-1 to avoid leaks from inv_mod. */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &R, ctx->len - 1, f_rng, p_rng ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx->Vi, &ctx->Vf, &R ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx->Vi, &ctx->Vi, &ctx->N ) );
+
+ /* At this point, Vi is invertible mod N if and only if both Vf and R
+ * are invertible mod N. If one of them isn't, we don't need to know
+ * which one, we just loop and choose new values for both of them.
+ * (Each iteration succeeds with overwhelming probability.) */
+ ret = mbedtls_mpi_inv_mod( &ctx->Vi, &ctx->Vi, &ctx->N );
+ if( ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
+ continue;
+ if( ret != 0 )
+ goto cleanup;
+
+ /* Finish the computation of Vf^-1 = R * (R Vf)^-1 */
+ MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx->Vi, &ctx->Vi, &R ) );
+ MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx->Vi, &ctx->Vi, &ctx->N ) );
+ } while( 0 );
+
+ /* Blinding value: Vi = Vf^(-e) mod N
+ * (Vi already contains Vf^-1 at this point) */
MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &ctx->Vi, &ctx->Vi, &ctx->E, &ctx->N, &ctx->RN ) );
cleanup:
+ mbedtls_mpi_free( &R );
+
return( ret );
}