Bug 660394: when generating an ECDSA signature, use a scalar that is
equivalent to k but has a fixed bit length to avoid leaking the length of
k in timing information. The patch is contributed by Douglas Stebila
<douglas@stebila.ca>. r=wtc.
--- a/security/nss/lib/freebl/ec.c
+++ b/security/nss/lib/freebl/ec.c
@@ -708,16 +708,37 @@ ECDSA_SignDigestWithSeed(ECPrivateKey *k
printf("k : %s \n", mpstr);
mp_tohex(&n, mpstr);
printf("n : %s \n", mpstr);
#endif
PORT_SetError(SEC_ERROR_NEED_RANDOM);
goto cleanup;
}
+ /*
+ ** We do not want timing information to leak the length of k,
+ ** so we compute k*G using an equivalent scalar of fixed
+ ** bit-length.
+ ** Fix based on patch for ECDSA timing attack in the paper
+ ** by Billy Bob Brumley and Nicola Tuveri at
+ ** http://eprint.iacr.org/2011/232
+ **
+ ** How do we convert k to a value of a fixed bit-length?
+ ** k starts off as an integer satisfying 0 <= k < n. Hence,
+ ** n <= k+n < 2n, which means k+n has either the same number
+ ** of bits as n or one more bit than n. If k+n has the same
+ ** number of bits as n, the second addition ensures that the
+ ** final value has exactly one more bit than n. Thus, we
+ ** always end up with a value that exactly one more bit than n.
+ */
+ CHECK_MPI_OK( mp_add(&k, &n, &k) );
+ if (mpl_significant_bits(&k) <= mpl_significant_bits(&n)) {
+ CHECK_MPI_OK( mp_add(&k, &n, &k) );
+ }
+
/*
** ANSI X9.62, Section 5.3.2, Step 2
**
** Compute kG
*/
kGpoint.len = 2*flen + 1;
kGpoint.data = PORT_Alloc(2*flen + 1);
if ((kGpoint.data == NULL) ||