Use constant-time look-up for modular exponentiation
Signed-off-by: Manuel Pégourié-Gonnard <manuel.pegourie-gonnard@arm.com>
diff --git a/library/bignum.c b/library/bignum.c
index 2c36456..20ab4de 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -2126,6 +2126,32 @@
mpi_montmul( A, &U, N, mm, T );
}
+/**
+ * Select an MPI from a table without leaking the index.
+ *
+ * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it
+ * reads the entire table in order to avoid leaking the value of idx to an
+ * attacker able to observe memory access patterns.
+ *
+ * \param[out] R Where to write the selected MPI.
+ * \param[in] T The table to read from.
+ * \param[in] T_size The number of elements in the table.
+ * \param[in] idx The index of the element to select;
+ * this must satisfy 0 <= idx < T_size.
+ *
+ * \return \c 0 on success, or a negative error code.
+ */
+static int mpi_select( mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx )
+{
+ int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
+
+ for( size_t i = 0; i < T_size; i++ )
+ MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( R, &T[i], i == idx ) );
+
+cleanup:
+ return( ret );
+}
+
/*
* Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
*/
@@ -2138,7 +2164,7 @@
size_t i, j, nblimbs;
size_t bufsize, nbits;
mbedtls_mpi_uint ei, mm, state;
- mbedtls_mpi RR, T, W[ 1 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
+ mbedtls_mpi RR, T, W[ 1 << MBEDTLS_MPI_WINDOW_SIZE ], WW, Apos;
int neg;
MPI_VALIDATE_RET( X != NULL );
@@ -2162,6 +2188,7 @@
mpi_montg_init( &mm, N );
mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
mbedtls_mpi_init( &Apos );
+ mbedtls_mpi_init( &WW );
memset( W, 0, sizeof( W ) );
i = mbedtls_mpi_bitlen( E );
@@ -2302,7 +2329,8 @@
/*
* X = X * W[wbits] R^-1 mod N
*/
- mpi_montmul( X, &W[wbits], N, mm, &T );
+ MBEDTLS_MPI_CHK( mpi_select( &WW, W, 1 << wsize, wbits ) );
+ mpi_montmul( X, &WW, N, mm, &T );
state--;
nbits = 0;
@@ -2340,6 +2368,7 @@
mbedtls_mpi_free( &W[i] );
mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
+ mbedtls_mpi_free( &WW );
if( _RR == NULL || _RR->p == NULL )
mbedtls_mpi_free( &RR );