From d4bf0d57a84a9bcdeba839b66138949be8221e17 Mon Sep 17 00:00:00 2001 From: Nicola Tuveri Date: Tue, 16 Jun 2020 20:12:13 +0300 Subject: [PATCH] Flag RSA secret BNs as consttime on keygen and checks 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 (Merged from https://github.com/openssl/openssl/pull/12167) --- crypto/bn/bn_rsa_fips186_4.c | 1 + crypto/rsa/rsa_gen.c | 6 +++++ crypto/rsa/rsa_sp800_56b_check.c | 41 ++++++++++++++++++++++++++++---- crypto/rsa/rsa_sp800_56b_gen.c | 34 +++++++++++++++++++++----- 4 files changed, 72 insertions(+), 10 deletions(-) diff --git a/crypto/bn/bn_rsa_fips186_4.c b/crypto/bn/bn_rsa_fips186_4.c index 935320ff2d..a8b0a69aee 100644 --- a/crypto/bn/bn_rsa_fips186_4.c +++ b/crypto/bn/bn_rsa_fips186_4.c @@ -109,6 +109,7 @@ static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1, if (BN_copy(p1, Xp1) == NULL) return 0; + BN_set_flags(p1, BN_FLG_CONSTTIME); /* Find the first odd number >= Xp1 that is probably prime */ for(;;) { 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) -- 2.25.1