Flag RSA secret BNs as consttime on keygen and checks

<https://github.com/openssl/openssl/pull/11765> switched the default
code path for keygen.

External testing through TriggerFlow highlighted that in several places
we failed (once more!) to set the `BN_FLG_CONSTTIME` flag on critical
secret values (either long term or temporary values).

This commit tries to make sure that the secret BN values inside the
`rsa struct` are always flagged on creation, and that temporary values
derived from these secrets are flagged when allocated from a BN_CTX.

Acknowledgments
---------------

Thanks to @Voker57, @bbbrumley, @sohhas, @cpereida for the
[OpenSSL Triggerflow CI] ([paper]) through which this defect was detected and
tested, and for providing early feedback to fix the issue!

[OpenSSL Triggerflow CI]: https://gitlab.com/nisec/openssl-triggerflow-ci
[paper]: https://eprint.iacr.org/2019/366

Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/12167)

3 files changed, 71 insertions, 10 deletions

diff --git a/crypto/rsa/rsa_gen.c b/crypto/rsa/rsa_gen.c
index 1495cefa83..e391f6419a 100644
--- a/crypto/rsa/rsa_gen.c
+++ b/crypto/rsa/rsa_gen.c
@@ -126,18 +126,24 @@ static int rsa_multiprime_keygen(RSA *rsa, int bits, int primes,
         goto err;
     if (!rsa->d && ((rsa->d = BN_secure_new()) == NULL))
         goto err;
+    BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
     if (!rsa->e && ((rsa->e = BN_new()) == NULL))
         goto err;
     if (!rsa->p && ((rsa->p = BN_secure_new()) == NULL))
         goto err;
+    BN_set_flags(rsa->p, BN_FLG_CONSTTIME);
     if (!rsa->q && ((rsa->q = BN_secure_new()) == NULL))
         goto err;
+    BN_set_flags(rsa->q, BN_FLG_CONSTTIME);
     if (!rsa->dmp1 && ((rsa->dmp1 = BN_secure_new()) == NULL))
         goto err;
+    BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME);
     if (!rsa->dmq1 && ((rsa->dmq1 = BN_secure_new()) == NULL))
         goto err;
+    BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME);
     if (!rsa->iqmp && ((rsa->iqmp = BN_secure_new()) == NULL))
         goto err;
+    BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
 
     /* initialize multi-prime components */
     if (primes > RSA_DEFAULT_PRIME_NUM) {
diff --git a/crypto/rsa/rsa_sp800_56b_check.c b/crypto/rsa/rsa_sp800_56b_check.c
index df9b7bf054..9840d08285 100644
--- a/crypto/rsa/rsa_sp800_56b_check.c
+++ b/crypto/rsa/rsa_sp800_56b_check.c
@@ -37,7 +37,15 @@ int rsa_check_crt_components(const RSA *rsa, BN_CTX *ctx)
     r = BN_CTX_get(ctx);
     p1 = BN_CTX_get(ctx);
     q1 = BN_CTX_get(ctx);
-    ret = (q1 != NULL)
+    if (q1 != NULL) {
+        BN_set_flags(r, BN_FLG_CONSTTIME);
+        BN_set_flags(p1, BN_FLG_CONSTTIME);
+        BN_set_flags(q1, BN_FLG_CONSTTIME);
+        ret = 1;
+    } else {
+        ret = 0;
+    }
+    ret = ret
           /* p1 = p -1 */
           && (BN_copy(p1, rsa->p) != NULL)
           && BN_sub_word(p1, 1)
@@ -62,6 +70,7 @@ int rsa_check_crt_components(const RSA *rsa, BN_CTX *ctx)
           /* (f) 1 = (qInv . q) mod p */
           && BN_mod_mul(r, rsa->iqmp, rsa->q, rsa->p, ctx)
           && BN_is_one(r);
+    BN_clear(r);
     BN_clear(p1);
     BN_clear(q1);
     BN_CTX_end(ctx);
@@ -138,7 +147,14 @@ int rsa_check_prime_factor(BIGNUM *p, BIGNUM *e, int nbits, BN_CTX *ctx)
     BN_CTX_start(ctx);
     p1 = BN_CTX_get(ctx);
     gcd = BN_CTX_get(ctx);
-    ret = (gcd != NULL)
+    if (gcd != NULL) {
+        BN_set_flags(p1, BN_FLG_CONSTTIME);
+        BN_set_flags(gcd, BN_FLG_CONSTTIME);
+        ret = 1;
+    } else {
+        ret = 0;
+    }
+    ret = ret
           /* (Step 5d) GCD(p-1, e) = 1 */
           && (BN_copy(p1, p) != NULL)
           && BN_sub_word(p1, 1)
@@ -172,7 +188,18 @@ int rsa_check_private_exponent(const RSA *rsa, int nbits, BN_CTX *ctx)
     lcm = BN_CTX_get(ctx);
     p1q1 = BN_CTX_get(ctx);
     gcd = BN_CTX_get(ctx);
-    ret = (gcd != NULL
+    if (gcd != NULL) {
+        BN_set_flags(r, BN_FLG_CONSTTIME);
+        BN_set_flags(p1, BN_FLG_CONSTTIME);
+        BN_set_flags(q1, BN_FLG_CONSTTIME);
+        BN_set_flags(lcm, BN_FLG_CONSTTIME);
+        BN_set_flags(p1q1, BN_FLG_CONSTTIME);
+        BN_set_flags(gcd, BN_FLG_CONSTTIME);
+        ret = 1;
+    } else {
+        ret = 0;
+    }
+    ret = (ret
           /* LCM(p - 1, q - 1) */
           && (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) == 1)
           /* (Step 6a) d < LCM(p - 1, q - 1) */
@@ -181,6 +208,7 @@ int rsa_check_private_exponent(const RSA *rsa, int nbits, BN_CTX *ctx)
           && BN_mod_mul(r, rsa->e, rsa->d, lcm, ctx)
           && BN_is_one(r));
 
+    BN_clear(r);
     BN_clear(p1);
     BN_clear(q1);
     BN_clear(lcm);
@@ -236,7 +264,12 @@ int rsa_check_pminusq_diff(BIGNUM *diff, const BIGNUM *p, const BIGNUM *q,
     return (BN_num_bits(diff) > bitlen);
 }
 
-/* return LCM(p-1, q-1) */
+/*
+ * return LCM(p-1, q-1)
+ *
+ * Caller should ensure that lcm, gcd, p1, q1, p1q1 are flagged with
+ * BN_FLG_CONSTTIME.
+ */
 int rsa_get_lcm(BN_CTX *ctx, const BIGNUM *p, const BIGNUM *q,
                 BIGNUM *lcm, BIGNUM *gcd, BIGNUM *p1, BIGNUM *q1,
                 BIGNUM *p1q1)
diff --git a/crypto/rsa/rsa_sp800_56b_gen.c b/crypto/rsa/rsa_sp800_56b_gen.c
index 9d7e1f1ebf..df15b8ce87 100644
--- a/crypto/rsa/rsa_sp800_56b_gen.c
+++ b/crypto/rsa/rsa_sp800_56b_gen.c
@@ -108,6 +108,8 @@ int rsa_fips186_4_gen_prob_primes(RSA *rsa, RSA_ACVP_TEST *test, int nbits,
     Xqo = (Xqout != NULL) ? Xqout : BN_CTX_get(ctx);
     if (tmp == NULL || Xpo == NULL || Xqo == NULL)
         goto err;
+    BN_set_flags(Xpo, BN_FLG_CONSTTIME);
+    BN_set_flags(Xqo, BN_FLG_CONSTTIME);
 
     if (rsa->p == NULL)
         rsa->p = BN_secure_new();
@@ -115,6 +117,8 @@ int rsa_fips186_4_gen_prob_primes(RSA *rsa, RSA_ACVP_TEST *test, int nbits,
         rsa->q = BN_secure_new();
     if (rsa->p == NULL || rsa->q == NULL)
         goto err;
+    BN_set_flags(rsa->p, BN_FLG_CONSTTIME);
+    BN_set_flags(rsa->q, BN_FLG_CONSTTIME);
 
     /* (Step 4) Generate p, Xp */
     if (!bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
@@ -217,6 +221,12 @@ int rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
     if (gcd == NULL)
         goto err;
 
+    BN_set_flags(p1, BN_FLG_CONSTTIME);
+    BN_set_flags(q1, BN_FLG_CONSTTIME);
+    BN_set_flags(lcm, BN_FLG_CONSTTIME);
+    BN_set_flags(p1q1, BN_FLG_CONSTTIME);
+    BN_set_flags(gcd, BN_FLG_CONSTTIME);
+
     /* LCM((p-1, q-1)) */
     if (rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
         goto err;
@@ -230,7 +240,10 @@ int rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
     BN_clear_free(rsa->d);
     /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
     rsa->d = BN_secure_new();
-    if (rsa->d == NULL || BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
+    if (rsa->d == NULL)
+        goto err;
+    BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
+    if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
         goto err;
 
     /* (Step 3) return an error if d is too small */
@@ -247,21 +260,29 @@ int rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
 
     /* (Step 5a) dP = d mod (p-1) */
     if (rsa->dmp1 == NULL)
-        rsa->dmp1 = BN_new();
-    if (rsa->dmp1 == NULL || !BN_mod(rsa->dmp1, rsa->d, p1, ctx))
+        rsa->dmp1 = BN_secure_new();
+    if (rsa->dmp1 == NULL)
+	    goto err;
+    BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME);
+    if (!BN_mod(rsa->dmp1, rsa->d, p1, ctx))
         goto err;
 
     /* (Step 5b) dQ = d mod (q-1) */
     if (rsa->dmq1 == NULL)
         rsa->dmq1 = BN_secure_new();
-    if (rsa->dmq1 == NULL || !BN_mod(rsa->dmq1, rsa->d, q1, ctx))
+    if (rsa->dmq1 == NULL)
+	    goto err;
+    BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME);
+    if (!BN_mod(rsa->dmq1, rsa->d, q1, ctx))
         goto err;
 
     /* (Step 5c) qInv = (inverse of q) mod p */
     BN_free(rsa->iqmp);
     rsa->iqmp = BN_secure_new();
-    if (rsa->iqmp == NULL
-            || BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
+    if (rsa->iqmp == NULL)
+	    goto err;
+    BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
+    if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
         goto err;
 
     rsa->dirty_cnt++;
@@ -379,6 +400,7 @@ int rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
     k = BN_CTX_get(ctx);
     if (k == NULL)
         goto err;
+    BN_set_flags(k, BN_FLG_CONSTTIME);
 
     ret = (BN_set_word(k, 2)
           && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)