Make BN_generate_dsa_nonce() constant time and non-biased

Co-authored-by: Paul Dale <ppzgs1@gmail.com>

Reviewed-by: Paul Dale <ppzgs1@gmail.com>
Reviewed-by: Neil Horman <nhorman@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/24265)

(cherry picked from commit d7d1bdcb6aa3d5000bf7f5ebc5518be5c91fd5a5)

4 files changed, 89 insertions, 36 deletions

diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c
index 9070647b35..85698885ed 100644
--- a/crypto/bn/bn_lib.c
+++ b/crypto/bn/bn_lib.c
@@ -708,14 +708,29 @@ int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
     int i;
     BN_ULONG t1, t2, *ap, *bp;
 
+    ap = a->d;
+    bp = b->d;
+
+    if (BN_get_flags(a, BN_FLG_CONSTTIME)
+            && a->top == b->top) {
+        int res = 0;
+
+        for (i = 0; i < b->top; i++) {
+            res = constant_time_select_int(constant_time_lt_bn(ap[i], bp[i]),
+                                           -1, res);
+            res = constant_time_select_int(constant_time_lt_bn(bp[i], ap[i]),
+                                           1, res);
+        }
+        return res;
+    }
+
     bn_check_top(a);
     bn_check_top(b);
 
     i = a->top - b->top;
     if (i != 0)
         return i;
-    ap = a->d;
-    bp = b->d;
+
     for (i = a->top - 1; i >= 0; i--) {
         t1 = ap[i];
         t2 = bp[i];
@@ -827,11 +842,10 @@ int BN_is_bit_set(const BIGNUM *a, int n)
     return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
 }
 
-int BN_mask_bits(BIGNUM *a, int n)
+int ossl_bn_mask_bits_fixed_top(BIGNUM *a, int n)
 {
     int b, w;
 
-    bn_check_top(a);
     if (n < 0)
         return 0;
 
@@ -845,10 +859,20 @@ int BN_mask_bits(BIGNUM *a, int n)
         a->top = w + 1;
         a->d[w] &= ~(BN_MASK2 << b);
     }
-    bn_correct_top(a);
     return 1;
 }
 
+int BN_mask_bits(BIGNUM *a, int n)
+{
+    int ret;
+
+    bn_check_top(a);
+    ret = ossl_bn_mask_bits_fixed_top(a, n);
+    if (ret)
+        bn_correct_top(a);
+    return ret;
+}
+
 void BN_set_negative(BIGNUM *a, int b)
 {
     if (b && !BN_is_zero(a))
diff --git a/crypto/bn/bn_local.h b/crypto/bn/bn_local.h
index b5be37ba97..8dbf773c73 100644
--- a/crypto/bn/bn_local.h
+++ b/crypto/bn/bn_local.h
@@ -679,5 +679,6 @@ static ossl_inline BIGNUM *bn_expand(BIGNUM *a, int bits)
 
 int ossl_bn_check_prime(const BIGNUM *w, int checks, BN_CTX *ctx,
                         int do_trial_division, BN_GENCB *cb);
+int ossl_bn_mask_bits_fixed_top(BIGNUM *a, int n);
 
 #endif
diff --git a/crypto/bn/bn_rand.c b/crypto/bn/bn_rand.c
index a94dfcecdf..f0bac810b4 100644
--- a/crypto/bn/bn_rand.c
+++ b/crypto/bn/bn_rand.c
@@ -258,20 +258,22 @@ int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range,
     unsigned char random_bytes[64];
     unsigned char digest[SHA512_DIGEST_LENGTH];
     unsigned done, todo;
-    /* We generate |range|+8 bytes of random output. */
-    const unsigned num_k_bytes = BN_num_bytes(range) + 8;
+    /* We generate |range|+1 bytes of random output. */
+    const unsigned num_k_bytes = BN_num_bytes(range) + 1;
     unsigned char private_bytes[96];
     unsigned char *k_bytes = NULL;
+    const int max_n = 64;           /* Pr(failure to generate) < 2^max_n */
+    int n;
     int ret = 0;
     EVP_MD *md = NULL;
     OSSL_LIB_CTX *libctx = ossl_bn_get_libctx(ctx);
 
     if (mdctx == NULL)
-        goto err;
+        goto end;
 
     k_bytes = OPENSSL_malloc(num_k_bytes);
     if (k_bytes == NULL)
-        goto err;
+        goto end;
 
     /* We copy |priv| into a local buffer to avoid exposing its length. */
     if (BN_bn2binpad(priv, private_bytes, sizeof(private_bytes)) < 0) {
@@ -281,41 +283,55 @@ int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range,
          * length of the private key.
          */
         ERR_raise(ERR_LIB_BN, BN_R_PRIVATE_KEY_TOO_LARGE);
-        goto err;
+        goto end;
     }
 
     md = EVP_MD_fetch(libctx, "SHA512", NULL);
     if (md == NULL) {
         ERR_raise(ERR_LIB_BN, BN_R_NO_SUITABLE_DIGEST);
-        goto err;
-    }
-    for (done = 0; done < num_k_bytes;) {
-        if (RAND_priv_bytes_ex(libctx, random_bytes, sizeof(random_bytes), 0) <= 0)
-            goto err;
-
-        if (!EVP_DigestInit_ex(mdctx, md, NULL)
-                || !EVP_DigestUpdate(mdctx, &done, sizeof(done))
-                || !EVP_DigestUpdate(mdctx, private_bytes,
-                                     sizeof(private_bytes))
-                || !EVP_DigestUpdate(mdctx, message, message_len)
-                || !EVP_DigestUpdate(mdctx, random_bytes, sizeof(random_bytes))
-                || !EVP_DigestFinal_ex(mdctx, digest, NULL))
-            goto err;
-
-        todo = num_k_bytes - done;
-        if (todo > SHA512_DIGEST_LENGTH)
-            todo = SHA512_DIGEST_LENGTH;
-        memcpy(k_bytes + done, digest, todo);
-        done += todo;
+        goto end;
     }
+    for (n = 0; n < max_n; n++) {
+        for (done = 0; done < num_k_bytes;) {
+            if (RAND_priv_bytes_ex(libctx, random_bytes, sizeof(random_bytes),
+                                   0) <= 0)
+                goto end;
+
+            if (!EVP_DigestInit_ex(mdctx, md, NULL)
+                    || !EVP_DigestUpdate(mdctx, &done, sizeof(done))
+                    || !EVP_DigestUpdate(mdctx, private_bytes,
+                                         sizeof(private_bytes))
+                    || !EVP_DigestUpdate(mdctx, message, message_len)
+                    || !EVP_DigestUpdate(mdctx, random_bytes,
+                                         sizeof(random_bytes))
+                    || !EVP_DigestFinal_ex(mdctx, digest, NULL))
+                goto end;
+
+            todo = num_k_bytes - done;
+            if (todo > SHA512_DIGEST_LENGTH)
+                todo = SHA512_DIGEST_LENGTH;
+            memcpy(k_bytes + done, digest, todo);
+            done += todo;
+        }
 
-    if (!BN_bin2bn(k_bytes, num_k_bytes, out))
-        goto err;
-    if (BN_mod(out, out, range, ctx) != 1)
-        goto err;
-    ret = 1;
+        /* Ensure top byte is set to avoid non-constant time in bin2bn */
+        k_bytes[0] = 0x80;
+        if (!BN_bin2bn(k_bytes, num_k_bytes, out))
+            goto end;
 
- err:
+        /* Clear out the top bits and rejection filter into range */
+        BN_set_flags(out, BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP);
+        ossl_bn_mask_bits_fixed_top(out, BN_num_bits(range));
+
+        if (BN_ucmp(out, range) < 0) {
+            ret = 1;
+            goto end;
+        }
+    }
+    /* Failed to generate anything */
+    ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
+
+ end:
     EVP_MD_CTX_free(mdctx);
     EVP_MD_free(md);
     OPENSSL_clear_free(k_bytes, num_k_bytes);
diff --git a/include/internal/constant_time.h b/include/internal/constant_time.h
index 0ed6f823c1..e8244cd57b 100644
--- a/include/internal/constant_time.h
+++ b/include/internal/constant_time.h
@@ -140,6 +140,18 @@ static ossl_inline uint64_t constant_time_lt_64(uint64_t a, uint64_t b)
     return constant_time_msb_64(a ^ ((a ^ b) | ((a - b) ^ b)));
 }
 
+#ifdef BN_ULONG
+static ossl_inline BN_ULONG constant_time_msb_bn(BN_ULONG a)
+{
+    return 0 - (a >> (sizeof(a) * 8 - 1));
+}
+
+static ossl_inline BN_ULONG constant_time_lt_bn(BN_ULONG a, BN_ULONG b)
+{
+    return constant_time_msb_bn(a ^ ((a ^ b) | ((a - b) ^ b)));
+}
+#endif
+
 static ossl_inline unsigned int constant_time_ge(unsigned int a,
                                                  unsigned int b)
 {