Clear some more false positives from constant-time validation
Mostly bits of DSA and RSA keygen, flagged when we make the PRNG output
secret by default. There's still a ton of RSA to resolve, mostly because
our constant-time bignum strategy does not interact well with valgrind
when handling RSA's secret-value / public-bit-length situation. Also
RSA's ASN.1 serialization is unavoidably leaky.
Bug: 676
Change-Id: I08d273959065c4db6fd44180a6ac56a82f862fe8
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/65447
Auto-Submit: David Benjamin <davidben@google.com>
Reviewed-by: Bob Beck <bbe@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
diff --git a/crypto/dsa/dsa.c b/crypto/dsa/dsa.c
index 1881e6a..a35b384 100644
--- a/crypto/dsa/dsa.c
+++ b/crypto/dsa/dsa.c
@@ -274,6 +274,8 @@
if (!RAND_bytes(seed, qsize)) {
goto err;
}
+ // DSA parameters are public.
+ CONSTTIME_DECLASSIFY(seed, qsize);
} else {
// If we come back through, use random seed next time.
seed_in = NULL;
@@ -513,6 +515,9 @@
goto err;
}
+ // The public key is computed from the private key, but is public.
+ bn_declassify(pub_key);
+
dsa->priv_key = priv_key;
dsa->pub_key = pub_key;
ok = 1;
@@ -649,6 +654,10 @@
goto err;
}
+ // The signature is computed from the private key, but is public.
+ bn_declassify(r);
+ bn_declassify(s);
+
// Redo if r or s is zero as required by FIPS 186-3: this is
// very unlikely.
if (BN_is_zero(r) || BN_is_zero(s)) {
@@ -900,15 +909,19 @@
ctx) ||
// Compute r = (g^k mod p) mod q
!BN_mod_exp_mont_consttime(r, dsa->g, &k, dsa->p, ctx,
- dsa->method_mont_p) ||
- // Note |BN_mod| below is not constant-time and may leak information about
- // |r|. |dsa->p| may be significantly larger than |dsa->q|, so this is not
- // easily performed in constant-time with Montgomery reduction.
- //
- // However, |r| at this point is g^k (mod p). It is almost the value of
- // |r| revealed in the signature anyway (g^k (mod p) (mod q)), going from
- // it to |k| would require computing a discrete log.
- !BN_mod(r, r, dsa->q, ctx) ||
+ dsa->method_mont_p)) {
+ OPENSSL_PUT_ERROR(DSA, ERR_R_BN_LIB);
+ goto err;
+ }
+ // Note |BN_mod| below is not constant-time and may leak information about
+ // |r|. |dsa->p| may be significantly larger than |dsa->q|, so this is not
+ // easily performed in constant-time with Montgomery reduction.
+ //
+ // However, |r| at this point is g^k (mod p). It is almost the value of |r|
+ // revealed in the signature anyway (g^k (mod p) (mod q)), going from it to
+ // |k| would require computing a discrete log.
+ bn_declassify(r);
+ if (!BN_mod(r, r, dsa->q, ctx) ||
// Compute part of 's = inv(k) (m + xr) mod q' using Fermat's Little
// Theorem.
!bn_mod_inverse_prime(kinv, &k, dsa->q, ctx, dsa->method_mont_q)) {
diff --git a/crypto/dsa/dsa_asn1.c b/crypto/dsa/dsa_asn1.c
index 1985bb4..1caf4ae 100644
--- a/crypto/dsa/dsa_asn1.c
+++ b/crypto/dsa/dsa_asn1.c
@@ -119,8 +119,9 @@
if (dsa->priv_key != NULL) {
// The private key is a non-zero element of the scalar field, determined by
// |q|.
- if (BN_is_negative(dsa->priv_key) || BN_is_zero(dsa->priv_key) ||
- BN_cmp(dsa->priv_key, dsa->q) >= 0) {
+ if (BN_is_negative(dsa->priv_key) ||
+ constant_time_declassify_int(BN_is_zero(dsa->priv_key)) ||
+ constant_time_declassify_int(BN_cmp(dsa->priv_key, dsa->q) >= 0)) {
OPENSSL_PUT_ERROR(DSA, DSA_R_INVALID_PARAMETERS);
return 0;
}
diff --git a/crypto/fipsmodule/bn/gcd_extra.c b/crypto/fipsmodule/bn/gcd_extra.c
index b4fe00e..76f337c 100644
--- a/crypto/fipsmodule/bn/gcd_extra.c
+++ b/crypto/fipsmodule/bn/gcd_extra.c
@@ -314,7 +314,10 @@
}
assert(BN_is_zero(v));
- if (!BN_is_one(u)) {
+ // While the inputs and output are secret, this function considers whether the
+ // input was invertible to be public. It is used as part of RSA key
+ // generation, where inputs are chosen to already be invertible.
+ if (constant_time_declassify_int(!BN_is_one(u))) {
*out_no_inverse = 1;
OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE);
goto err;
diff --git a/crypto/fipsmodule/bn/prime.c b/crypto/fipsmodule/bn/prime.c
index fb30768..5af6387 100644
--- a/crypto/fipsmodule/bn/prime.c
+++ b/crypto/fipsmodule/bn/prime.c
@@ -487,7 +487,10 @@
static int bn_trial_division(uint16_t *out, const BIGNUM *bn) {
const size_t num_primes = num_trial_division_primes(bn);
for (size_t i = 1; i < num_primes; i++) {
- if (bn_mod_u16_consttime(bn, kPrimes[i]) == 0) {
+ // During RSA key generation, |bn| may be secret, but only if |bn| was
+ // prime, so it is safe to leak failed trial divisions.
+ if (constant_time_declassify_int(bn_mod_u16_consttime(bn, kPrimes[i]) ==
+ 0)) {
*out = kPrimes[i];
return 1;
}
@@ -573,7 +576,8 @@
// To avoid leaking |a|, we run the loop to |w_bits| and mask off all
// iterations once |j| = |a|.
for (int j = 1; j < miller_rabin->w_bits; j++) {
- if (constant_time_eq_int(j, miller_rabin->a) & ~is_possibly_prime) {
+ if (constant_time_declassify_w(constant_time_eq_int(j, miller_rabin->a) &
+ ~is_possibly_prime)) {
// If the loop is done and we haven't seen z = 1 or z = w-1 yet, the
// value is composite and we can break in variable time.
break;
@@ -593,12 +597,14 @@
// Step 4.5.3. If z = 1 and the loop is not done, the previous value of z
// was not -1. There are no non-trivial square roots of 1 modulo a prime, so
// w is composite and we may exit in variable time.
- if (BN_equal_consttime(z, miller_rabin->one_mont) & ~is_possibly_prime) {
+ if (constant_time_declassify_w(
+ BN_equal_consttime(z, miller_rabin->one_mont) &
+ ~is_possibly_prime)) {
break;
}
}
- *out_is_possibly_prime = is_possibly_prime & 1;
+ *out_is_possibly_prime = constant_time_declassify_w(is_possibly_prime) & 1;
ret = 1;
err:
@@ -736,8 +742,9 @@
crypto_word_t uniform_iterations = 0;
// Using |constant_time_lt_w| seems to prevent the compiler from optimizing
// this into two jumps.
- for (int i = 1; (i <= BN_PRIME_CHECKS_BLINDED) |
- constant_time_lt_w(uniform_iterations, checks);
+ for (int i = 1; constant_time_declassify_w(
+ (i <= BN_PRIME_CHECKS_BLINDED) |
+ constant_time_lt_w(uniform_iterations, checks));
i++) {
// Step 4.1-4.2
int is_uniform;
diff --git a/crypto/fipsmodule/ec/ec_key.c b/crypto/fipsmodule/ec/ec_key.c
index 7b7d396..3b650d7 100644
--- a/crypto/fipsmodule/ec/ec_key.c
+++ b/crypto/fipsmodule/ec/ec_key.c
@@ -242,7 +242,10 @@
return 0;
}
if (!ec_bignum_to_scalar(key->group, &scalar->scalar, priv_key) ||
- ec_scalar_is_zero(key->group, &scalar->scalar)) {
+ // Zero is not a valid private key, so it is safe to leak the result of
+ // this comparison.
+ constant_time_declassify_int(
+ ec_scalar_is_zero(key->group, &scalar->scalar))) {
OPENSSL_PUT_ERROR(EC, EC_R_INVALID_PRIVATE_KEY);
ec_wrapped_scalar_free(scalar);
return 0;
diff --git a/crypto/fipsmodule/ec/scalar.c b/crypto/fipsmodule/ec/scalar.c
index a86ee0f..b05d508 100644
--- a/crypto/fipsmodule/ec/scalar.c
+++ b/crypto/fipsmodule/ec/scalar.c
@@ -23,8 +23,12 @@
int ec_bignum_to_scalar(const EC_GROUP *group, EC_SCALAR *out,
const BIGNUM *in) {
+ // Scalars, which are often secret, must be reduced modulo the order. Those
+ // that are not will be discarded, so leaking the result of the comparison is
+ // safe.
if (!bn_copy_words(out->words, group->order.N.width, in) ||
- !bn_less_than_words(out->words, group->order.N.d, group->order.N.width)) {
+ !constant_time_declassify_int(bn_less_than_words(
+ out->words, group->order.N.d, group->order.N.width))) {
OPENSSL_PUT_ERROR(EC, EC_R_INVALID_SCALAR);
return 0;
}
diff --git a/crypto/fipsmodule/rsa/rsa.c b/crypto/fipsmodule/rsa/rsa.c
index 1a9f050..b524e77 100644
--- a/crypto/fipsmodule/rsa/rsa.c
+++ b/crypto/fipsmodule/rsa/rsa.c
@@ -758,7 +758,8 @@
static int check_mod_inverse(int *out_ok, const BIGNUM *a, const BIGNUM *ainv,
const BIGNUM *m, unsigned m_min_bits,
BN_CTX *ctx) {
- if (BN_is_negative(ainv) || BN_cmp(ainv, m) >= 0) {
+ if (BN_is_negative(ainv) ||
+ constant_time_declassify_int(BN_cmp(ainv, m) >= 0)) {
*out_ok = 0;
return 1;
}
@@ -772,7 +773,7 @@
bn_mul_consttime(tmp, a, ainv, ctx) &&
bn_div_consttime(NULL, tmp, tmp, m, m_min_bits, ctx);
if (ret) {
- *out_ok = BN_is_one(tmp);
+ *out_ok = constant_time_declassify_int(BN_is_one(tmp));
}
BN_CTX_end(ctx);
return ret;
@@ -831,8 +832,10 @@
// bounds, to avoid a DoS vector in |bn_mul_consttime| below. Note that
// n was bound by |rsa_check_public_key|. This also implicitly checks p and q
// are odd, which is a necessary condition for Montgomery reduction.
- if (BN_is_negative(key->p) || BN_cmp(key->p, key->n) >= 0 ||
- BN_is_negative(key->q) || BN_cmp(key->q, key->n) >= 0) {
+ if (BN_is_negative(key->p) ||
+ constant_time_declassify_int(BN_cmp(key->p, key->n) >= 0) ||
+ BN_is_negative(key->q) ||
+ constant_time_declassify_int(BN_cmp(key->q, key->n) >= 0)) {
OPENSSL_PUT_ERROR(RSA, RSA_R_N_NOT_EQUAL_P_Q);
goto out;
}
@@ -863,7 +866,8 @@
goto out;
}
- if (!BN_is_one(&tmp) || !BN_is_one(&de)) {
+ if (constant_time_declassify_int(!BN_is_one(&tmp)) ||
+ constant_time_declassify_int(!BN_is_one(&de))) {
OPENSSL_PUT_ERROR(RSA, RSA_R_D_E_NOT_CONGRUENT_TO_1);
goto out;
}
diff --git a/crypto/fipsmodule/rsa/rsa_impl.c b/crypto/fipsmodule/rsa/rsa_impl.c
index f2dc7fe..6f9c3bb 100644
--- a/crypto/fipsmodule/rsa/rsa_impl.c
+++ b/crypto/fipsmodule/rsa/rsa_impl.c
@@ -1003,20 +1003,25 @@
// retrying. That is, we reject a negligible fraction of primes that are
// within the FIPS bound, but we will never accept a prime outside the
// bound, ensuring the resulting RSA key is the right size.
- if (BN_cmp(out, sqrt2) <= 0) {
+ //
+ // Values over the threshold are discarded, so it is safe to leak this
+ // comparison.
+ if (constant_time_declassify_int(BN_cmp(out, sqrt2) <= 0)) {
continue;
}
// RSA key generation's bottleneck is discarding composites. If it fails
// trial division, do not bother computing a GCD or performing Miller-Rabin.
if (!bn_odd_number_is_obviously_composite(out)) {
- // Check gcd(out-1, e) is one (steps 4.5 and 5.6).
+ // Check gcd(out-1, e) is one (steps 4.5 and 5.6). Leaking the final
+ // result of this comparison is safe because, if not relatively prime, the
+ // value will be discarded.
int relatively_prime;
- if (!BN_sub(tmp, out, BN_value_one()) ||
+ if (!bn_usub_consttime(tmp, out, BN_value_one()) ||
!bn_is_relatively_prime(&relatively_prime, tmp, e, ctx)) {
goto err;
}
- if (relatively_prime) {
+ if (constant_time_declassify_int(relatively_prime)) {
// Test |out| for primality (steps 4.5.1 and 5.6.1).
int is_probable_prime;
if (!BN_primality_test(&is_probable_prime, out,
@@ -1174,8 +1179,9 @@
}
// Retry if |rsa->d| <= 2^|prime_bits|. See appendix B.3.1's guidance on
- // values for d.
- } while (BN_cmp(rsa->d, pow2_prime_bits) <= 0);
+ // values for d. When we retry, p and q are discarded, so it is safe to leak
+ // this comparison.
+ } while (constant_time_declassify_int(BN_cmp(rsa->d, pow2_prime_bits) <= 0));
assert(BN_num_bits(pm1) == (unsigned)prime_bits);
assert(BN_num_bits(qm1) == (unsigned)prime_bits);
@@ -1189,6 +1195,9 @@
}
bn_set_minimal_width(rsa->n);
+ // |rsa->n| is computed from the private key, but is public.
+ bn_declassify(rsa->n);
+
// Sanity-check that |rsa->n| has the specified size. This is implied by
// |generate_prime|'s bounds.
if (BN_num_bits(rsa->n) != (unsigned)bits) {
