Make ossl_gen_deterministic_nonce_rfc6979() constant time

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 2d285fa873028f6cff9484a0cdf690fe05d7fb16)

7 files changed, 78 insertions, 11 deletions

diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c
index 85698885ed..cab87d9959 100644
--- a/crypto/bn/bn_lib.c
+++ b/crypto/bn/bn_lib.c
@@ -859,6 +859,7 @@ int ossl_bn_mask_bits_fixed_top(BIGNUM *a, int n)
         a->top = w + 1;
         a->d[w] &= ~(BN_MASK2 << b);
     }
+    a->flags |= BN_FLG_FIXED_TOP;
     return 1;
 }
 
@@ -1046,6 +1047,22 @@ int BN_is_word(const BIGNUM *a, const BN_ULONG w)
     return BN_abs_is_word(a, w) && (!w || !a->neg);
 }
 
+int ossl_bn_is_word_fixed_top(const BIGNUM *a, const BN_ULONG w)
+{
+    int res, i;
+    const BN_ULONG *ap = a->d;
+
+    if (a->neg || a->top == 0)
+        return 0;
+
+    res = constant_time_select_int(constant_time_eq_bn(ap[0], w), 1, 0);
+
+    for (i = 1; i < a->top; i++)
+        res = constant_time_select_int(constant_time_is_zero_bn(ap[i]),
+                                       res, 0);
+    return res;
+}
+
 int BN_is_odd(const BIGNUM *a)
 {
     return (a->top > 0) && (a->d[0] & 1);
diff --git a/crypto/bn/bn_local.h b/crypto/bn/bn_local.h
index 8dbf773c73..b5be37ba97 100644
--- a/crypto/bn/bn_local.h
+++ b/crypto/bn/bn_local.h
@@ -679,6 +679,5 @@ 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 f0bac810b4..6be0c5e941 100644
--- a/crypto/bn/bn_rand.c
+++ b/crypto/bn/bn_rand.c
@@ -320,7 +320,7 @@ int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range,
             goto end;
 
         /* Clear out the top bits and rejection filter into range */
-        BN_set_flags(out, BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP);
+        BN_set_flags(out, BN_FLG_CONSTTIME);
         ossl_bn_mask_bits_fixed_top(out, BN_num_bits(range));
 
         if (BN_ucmp(out, range) < 0) {
diff --git a/crypto/bn/bn_shift.c b/crypto/bn/bn_shift.c
index 8fcb04324e..a6976c7130 100644
--- a/crypto/bn/bn_shift.c
+++ b/crypto/bn/bn_shift.c
@@ -156,6 +156,9 @@ int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)
         return 0;
     }
 
+    bn_check_top(r);
+    bn_check_top(a);
+
     ret = bn_rshift_fixed_top(r, a, n);
 
     bn_correct_top(r);
@@ -177,9 +180,6 @@ int bn_rshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n)
     BN_ULONG *t, *f;
     BN_ULONG l, m, mask;
 
-    bn_check_top(r);
-    bn_check_top(a);
-
     assert(n >= 0);
 
     nw = n / BN_BITS2;
diff --git a/crypto/deterministic_nonce.c b/crypto/deterministic_nonce.c
index 60af7f6ab6..a37edea2a1 100644
--- a/crypto/deterministic_nonce.c
+++ b/crypto/deterministic_nonce.c
@@ -7,11 +7,13 @@
  * https://www.openssl.org/source/license.html
  */
 
+#include <string.h>
 #include <openssl/bn.h>
 #include <openssl/evp.h>
 #include <openssl/core_names.h>
 #include <openssl/kdf.h>
 #include "internal/deterministic_nonce.h"
+#include "crypto/bn.h"
 
 /*
  * Convert a Bit String to an Integer (See RFC 6979 Section 2.3.2)
@@ -39,6 +41,36 @@ static int bits2int(BIGNUM *out, int qlen_bits,
 }
 
 /*
+ * Convert as above a Bit String in const time to an Integer w fixed top
+ *
+ * Params:
+ *     out The returned Integer as a BIGNUM
+ *     qlen_bits The maximum size of the returned integer in bits. The returned
+ *        Integer is shifted right if inlen is larger than qlen_bits..
+ *     in, inlen The input Bit String (in bytes). It has sizeof(BN_ULONG) bytes
+ *               prefix with all bits set that needs to be cleared out after
+ *               the conversion.
+ * Returns: 1 if successful, or  0 otherwise.
+ */
+static int bits2int_consttime(BIGNUM *out, int qlen_bits,
+                              const unsigned char *in, size_t inlen)
+{
+    int blen_bits = (inlen - sizeof(BN_ULONG)) * 8;
+    int shift;
+
+    if (BN_bin2bn(in, (int)inlen, out) == NULL)
+        return 0;
+
+    BN_set_flags(out, BN_FLG_CONSTTIME);
+    ossl_bn_mask_bits_fixed_top(out, blen_bits);
+
+    shift = blen_bits - qlen_bits;
+    if (shift > 0)
+        return bn_rshift_fixed_top(out, out, shift);
+    return 1;
+}
+
+/*
  * Convert an Integer to an Octet String (See RFC 6979 2.3.3).
  * The value is zero padded if required.
  *
@@ -155,8 +187,9 @@ int ossl_gen_deterministic_nonce_rfc6979(BIGNUM *out, const BIGNUM *q,
 {
     EVP_KDF_CTX *kdfctx = NULL;
     int ret = 0, rlen = 0, qlen_bits = 0;
-    unsigned char *entropyx = NULL, *nonceh = NULL, *T = NULL;
+    unsigned char *entropyx = NULL, *nonceh = NULL, *rbits = NULL, *T = NULL;
     size_t allocsz = 0;
+    const size_t prefsz = sizeof(BN_ULONG);
 
     if (out == NULL)
         return 0;
@@ -167,15 +200,18 @@ int ossl_gen_deterministic_nonce_rfc6979(BIGNUM *out, const BIGNUM *q,
 
     /* Note rlen used here is in bytes since the input values are byte arrays */
     rlen = (qlen_bits + 7) / 8;
-    allocsz = 3 * rlen;
+    allocsz = prefsz + 3 * rlen;
 
     /* Use a single alloc for the buffers T, nonceh and entropyx */
     T = (unsigned char *)OPENSSL_zalloc(allocsz);
     if (T == NULL)
         return 0;
-    nonceh = T + rlen;
+    rbits = T + prefsz;
+    nonceh = rbits + rlen;
     entropyx = nonceh + rlen;
 
+    memset(T, 0xff, prefsz);
+
     if (!int2octets(entropyx, priv, rlen)
             || !bits2octets(nonceh, q, qlen_bits, rlen, hm, hmlen))
         goto end;
@@ -185,10 +221,12 @@ int ossl_gen_deterministic_nonce_rfc6979(BIGNUM *out, const BIGNUM *q,
         goto end;
 
     do {
-        if (!EVP_KDF_derive(kdfctx, T, rlen, NULL)
-                || !bits2int(out, qlen_bits, T, rlen))
+        if (!EVP_KDF_derive(kdfctx, rbits, rlen, NULL)
+                || !bits2int_consttime(out, qlen_bits, T, rlen + prefsz))
             goto end;
-    } while (BN_is_zero(out) || BN_is_one(out) || BN_cmp(out, q) >= 0);
+    } while (ossl_bn_is_word_fixed_top(out, 0)
+            || ossl_bn_is_word_fixed_top(out, 1)
+            || BN_ucmp(out, q) >= 0);
     ret = 1;
 
 end:
diff --git a/include/crypto/bn.h b/include/crypto/bn.h
index 48859683fe..8f0664420a 100644
--- a/include/crypto/bn.h
+++ b/include/crypto/bn.h
@@ -87,6 +87,8 @@ int bn_lshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n);
 int bn_rshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n);
 int bn_div_fixed_top(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
                      const BIGNUM *d, BN_CTX *ctx);
+int ossl_bn_mask_bits_fixed_top(BIGNUM *a, int n);
+int ossl_bn_is_word_fixed_top(const BIGNUM *a, BN_ULONG w);
 
 #define BN_PRIMETEST_COMPOSITE                    0
 #define BN_PRIMETEST_COMPOSITE_WITH_FACTOR        1
diff --git a/include/internal/constant_time.h b/include/internal/constant_time.h
index e8244cd57b..f2572ded51 100644
--- a/include/internal/constant_time.h
+++ b/include/internal/constant_time.h
@@ -150,6 +150,17 @@ 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)));
 }
+
+static ossl_inline BN_ULONG constant_time_is_zero_bn(BN_ULONG a)
+{
+    return constant_time_msb_bn(~a & (a - 1));
+}
+
+static ossl_inline BN_ULONG constant_time_eq_bn(BN_ULONG a,
+                                                BN_ULONG b)
+{
+    return constant_time_is_zero_bn(a ^ b);
+}
 #endif
 
 static ossl_inline unsigned int constant_time_ge(unsigned int a,