Generate (EC)DSA nonces with truncate/test/reject.

Previously we generated a number that was 8 bytes too large and used a
modular reduction, which has a (tiny, tiny) bias towards zero.

Out of an excess of caution, instead truncate the generated nonce and
try again if it's out of range.

Change-Id: Ia9a7a57dd6d3e5f13d0b881b3e9b2e986d46e4ca

crypto/bn/random.c

diff --git a/crypto/bn/random.c b/crypto/bn/random.c
index 13df050..06e4c0f 100644
--- a/crypto/bn/random.c
+++ b/crypto/bn/random.c
@@ -245,15 +245,21 @@
    * ensure that we have at least |range| bits of randomness. */
   uint8_t random_bytes[64];
   uint8_t digest[SHA512_DIGEST_LENGTH];
-  size_t done, todo;
-  /* We generate |range|+8 bytes of random output. */
-  const unsigned num_k_bytes = BN_num_bytes(range) + 8;
+  size_t done, todo, attempt;
+  const unsigned num_k_bytes = BN_num_bytes(range);
+  const unsigned bits_to_mask = (8 - (BN_num_bits(range) % 8)) % 8;
   uint8_t private_bytes[96];
-  uint8_t *k_bytes;
+  uint8_t *k_bytes = NULL;
   int ret = 0;
 
+  if (BN_is_zero(range)) {
+    OPENSSL_PUT_ERROR(BN, BN_generate_dsa_nonce, BN_R_DIV_BY_ZERO);
+    goto err;
+  }
+
   k_bytes = OPENSSL_malloc(num_k_bytes);
   if (!k_bytes) {
+    OPENSSL_PUT_ERROR(BN, BN_generate_dsa_nonce, ERR_R_MALLOC_FAILURE);
     goto err;
   }
 
@@ -270,29 +276,37 @@
   memcpy(private_bytes, priv->d, todo);
   memset(private_bytes + todo, 0, sizeof(private_bytes) - todo);
 
-  for (done = 0; done < num_k_bytes;) {
-    if (RAND_pseudo_bytes(random_bytes, sizeof(random_bytes)) != 1) {
+  for (attempt = 0;; attempt++) {
+    for (done = 0; done < num_k_bytes;) {
+      if (RAND_pseudo_bytes(random_bytes, sizeof(random_bytes)) != 1) {
+        goto err;
+      }
+      SHA512_Init(&sha);
+      SHA512_Update(&sha, &attempt, sizeof(attempt));
+      SHA512_Update(&sha, &done, sizeof(done));
+      SHA512_Update(&sha, private_bytes, sizeof(private_bytes));
+      SHA512_Update(&sha, message, message_len);
+      SHA512_Update(&sha, random_bytes, sizeof(random_bytes));
+      SHA512_Final(digest, &sha);
+
+      todo = num_k_bytes - done;
+      if (todo > SHA512_DIGEST_LENGTH) {
+        todo = SHA512_DIGEST_LENGTH;
+      }
+      memcpy(k_bytes + done, digest, todo);
+      done += todo;
+    }
+
+    k_bytes[0] &= 0xff >> bits_to_mask;
+
+    if (!BN_bin2bn(k_bytes, num_k_bytes, out)) {
       goto err;
     }
-    SHA512_Init(&sha);
-    SHA512_Update(&sha, &done, sizeof(done));
-    SHA512_Update(&sha, private_bytes, sizeof(private_bytes));
-    SHA512_Update(&sha, message, message_len);
-    SHA512_Update(&sha, random_bytes, sizeof(random_bytes));
-    SHA512_Final(digest, &sha);
-
-    todo = num_k_bytes - done;
-    if (todo > SHA512_DIGEST_LENGTH) {
-      todo = SHA512_DIGEST_LENGTH;
+    if (BN_cmp(out, range) < 0) {
+      break;
     }
-    memcpy(k_bytes + done, digest, todo);
-    done += todo;
   }
 
-  if (!BN_bin2bn(k_bytes, num_k_bytes, out) ||
-      BN_mod(out, out, range, ctx) != 1) {
-    goto err;
-  }
   ret = 1;
 
 err: