Bug 660394: when generating an ECDSA signature, use a scalar that is
authorwtc%google.com
Wed, 28 Sep 2011 17:50:00 +0000 (2011-09-28)
changeset 10147 079cfc4710c7193ef73888394f4d4f935e03f241
parent 10146 fdac5f73b9e2b510df5fec486b54763a534f33ea
child 10148 9b202f597812bb9df13ea3c58a3b37abf42cf909
push idunknown
push userunknown
push dateunknown (unknown)
bugs660394
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.
security/nss/lib/freebl/ec.c
--- 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) ||