Remove potential timing leak in ecdsa_sign()
diff --git a/ChangeLog b/ChangeLog
index 417b37f..a6bcdf1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -2,6 +2,10 @@
= PolarSSL 1.3 branch
+Security
+ * Avoid potential timing leak in ecdsa_sign() by blinding modular division.
+ (Found by Watson Ladd.)
+
Bugfix
* The length of various ClientKeyExchange messages was not properly checked.
* Some example server programs were not sending the close_notify alert.
diff --git a/include/polarssl/ecp.h b/include/polarssl/ecp.h
index 61d6a1d..1cafc46 100644
--- a/include/polarssl/ecp.h
+++ b/include/polarssl/ecp.h
@@ -118,6 +118,9 @@
* short weierstrass, this subgroup is actually the whole curve, and its
* cardinal is denoted by N.
*
+ * In the case of Short Weierstrass curves, our code requires that N is an odd
+ * prime. (Use odd in ecp_mul() and prime in ecdsa_sign() for blinding.)
+ *
* In the case of Montgomery curves, we don't store A but (A + 2) / 4 which is
* the quantity actualy used in the formulas. Also, nbits is not the size of N
* but the required size for private keys.
diff --git a/library/ecdsa.c b/library/ecdsa.c
index 94522a4..c9ab62f 100644
--- a/library/ecdsa.c
+++ b/library/ecdsa.c
@@ -99,17 +99,16 @@
const mpi *d, const unsigned char *buf, size_t blen,
int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
{
- int ret, key_tries, sign_tries;
+ int ret, key_tries, sign_tries, blind_tries;
ecp_point R;
- mpi k, e;
+ mpi k, e, t;
/* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
if( grp->N.p == NULL )
return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
ecp_point_init( &R );
- mpi_init( &k );
- mpi_init( &e );
+ mpi_init( &k ); mpi_init( &e ); mpi_init( &t );
sign_tries = 0;
do
@@ -138,10 +137,30 @@
MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
/*
- * Step 6: compute s = (e + r * d) / k mod n
+ * Generate a random value to blind inv_mod in next step,
+ * avoiding a potential timing leak.
+ */
+ blind_tries = 0;
+ do
+ {
+ size_t n_size = (grp->nbits + 7) / 8;
+ MPI_CHK( mpi_fill_random( &t, n_size, f_rng, p_rng ) );
+ MPI_CHK( mpi_shift_r( &t, 8 * n_size - grp->nbits ) );
+
+ /* See ecp_gen_keypair() */
+ if( ++blind_tries > 30 )
+ return( POLARSSL_ERR_ECP_RANDOM_FAILED );
+ }
+ while( mpi_cmp_int( &t, 1 ) < 0 ||
+ mpi_cmp_mpi( &t, &grp->N ) >= 0 );
+
+ /*
+ * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n
*/
MPI_CHK( mpi_mul_mpi( s, r, d ) );
MPI_CHK( mpi_add_mpi( &e, &e, s ) );
+ MPI_CHK( mpi_mul_mpi( &e, &e, &t ) );
+ MPI_CHK( mpi_mul_mpi( &k, &k, &t ) );
MPI_CHK( mpi_inv_mod( s, &k, &grp->N ) );
MPI_CHK( mpi_mul_mpi( s, s, &e ) );
MPI_CHK( mpi_mod_mpi( s, s, &grp->N ) );
@@ -156,8 +175,7 @@
cleanup:
ecp_point_free( &R );
- mpi_free( &k );
- mpi_free( &e );
+ mpi_free( &k ); mpi_free( &e ); mpi_free( &t );
return( ret );
}