Split BN_prime_checks into two constants for generation and validation. Although (somewhat) documented in prose, it is not obvious from the name that BN_prime_checks only works for randomly-selected candidate primes. Split into BN_prime_checks_for_generation and BN_prime_checks_for_validation. Fix internal call sites. Notably, DH_check now uses more iterations. Consistently call the parameter 'checks' rather than 'iterations', to match BN_prime_checks. This is in preparation for importing the Wycheproof primality testing vectors, some of which include Miller-Rabin worst case values. (Realistically the blinding mechanism meant, even for those inputs, our false positive rate was at most ~2^-64 anyway, but best to keep the use cases clear.) Update-Note: DH_check may be slower after this change. Change-Id: Ic13d03d8631e74bf2958979ee5ef45a69e603f46 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/39195 Commit-Queue: Adam Langley <agl@google.com> Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/dh/check.c b/crypto/dh/check.c index 454ad44..5b6e03a 100644 --- a/crypto/dh/check.c +++ b/crypto/dh/check.c
@@ -151,7 +151,7 @@ *out_flags |= DH_CHECK_NOT_SUITABLE_GENERATOR; } } - r = BN_is_prime_ex(dh->q, BN_prime_checks, ctx, NULL); + r = BN_is_prime_ex(dh->q, BN_prime_checks_for_validation, ctx, NULL); if (r < 0) { goto err; } @@ -188,7 +188,7 @@ *out_flags |= DH_CHECK_UNABLE_TO_CHECK_GENERATOR; } - r = BN_is_prime_ex(dh->p, BN_prime_checks, ctx, NULL); + r = BN_is_prime_ex(dh->p, BN_prime_checks_for_validation, ctx, NULL); if (r < 0) { goto err; } @@ -198,7 +198,7 @@ if (!BN_rshift1(t1, dh->p)) { goto err; } - r = BN_is_prime_ex(t1, BN_prime_checks, ctx, NULL); + r = BN_is_prime_ex(t1, BN_prime_checks_for_validation, ctx, NULL); if (r < 0) { goto err; }
diff --git a/crypto/fipsmodule/bn/bn_test.cc b/crypto/fipsmodule/bn/bn_test.cc index ea3967b..4793d24 100644 --- a/crypto/fipsmodule/bn/bn_test.cc +++ b/crypto/fipsmodule/bn/bn_test.cc
@@ -1986,16 +1986,17 @@ ASSERT_TRUE(BN_set_word(p.get(), i)); ASSERT_TRUE(BN_primality_test( - &is_probably_prime_1, p.get(), BN_prime_checks, ctx(), + &is_probably_prime_1, p.get(), BN_prime_checks_for_generation, ctx(), false /* do_trial_division */, nullptr /* callback */)); EXPECT_EQ(is_prime ? 1 : 0, is_probably_prime_1); ASSERT_TRUE(BN_primality_test( - &is_probably_prime_2, p.get(), BN_prime_checks, ctx(), + &is_probably_prime_2, p.get(), BN_prime_checks_for_generation, ctx(), true /* do_trial_division */, nullptr /* callback */)); EXPECT_EQ(is_prime ? 1 : 0, is_probably_prime_2); if (i > 3 && i % 2 == 1) { ASSERT_TRUE(BN_enhanced_miller_rabin_primality_test( - &result_3, p.get(), BN_prime_checks, ctx(), nullptr /* callback */)); + &result_3, p.get(), BN_prime_checks_for_generation, ctx(), + nullptr /* callback */)); EXPECT_EQ(is_prime, result_3 == bn_probably_prime); } } @@ -2003,13 +2004,13 @@ // Negative numbers are not prime. ASSERT_TRUE(BN_set_word(p.get(), 7)); BN_set_negative(p.get(), 1); - ASSERT_TRUE(BN_primality_test(&is_probably_prime_1, p.get(), BN_prime_checks, - ctx(), false /* do_trial_division */, - nullptr /* callback */)); + ASSERT_TRUE(BN_primality_test( + &is_probably_prime_1, p.get(), BN_prime_checks_for_generation, ctx(), + false /* do_trial_division */, nullptr /* callback */)); EXPECT_EQ(0, is_probably_prime_1); - ASSERT_TRUE(BN_primality_test(&is_probably_prime_2, p.get(), BN_prime_checks, - ctx(), true /* do_trial_division */, - nullptr /* callback */)); + ASSERT_TRUE(BN_primality_test( + &is_probably_prime_2, p.get(), BN_prime_checks_for_generation, ctx(), + true /* do_trial_division */, nullptr /* callback */)); EXPECT_EQ(0, is_probably_prime_2); static const char *kComposites[] = { @@ -2068,17 +2069,18 @@ EXPECT_NE(0, DecimalToBIGNUM(&p, str)); ASSERT_TRUE(BN_primality_test( - &is_probably_prime_1, p.get(), BN_prime_checks, ctx(), + &is_probably_prime_1, p.get(), BN_prime_checks_for_generation, ctx(), false /* do_trial_division */, nullptr /* callback */)); EXPECT_EQ(0, is_probably_prime_1); ASSERT_TRUE(BN_primality_test( - &is_probably_prime_2, p.get(), BN_prime_checks, ctx(), + &is_probably_prime_2, p.get(), BN_prime_checks_for_generation, ctx(), true /* do_trial_division */, nullptr /* callback */)); EXPECT_EQ(0, is_probably_prime_2); ASSERT_TRUE(BN_enhanced_miller_rabin_primality_test( - &result_3, p.get(), BN_prime_checks, ctx(), nullptr /* callback */)); + &result_3, p.get(), BN_prime_checks_for_generation, ctx(), + nullptr /* callback */)); EXPECT_EQ(bn_composite, result_3); } @@ -2257,25 +2259,27 @@ EXPECT_NE(0, HexToBIGNUM(&p, str)); ASSERT_TRUE(BN_primality_test( - &is_probably_prime_1, p.get(), BN_prime_checks, ctx(), + &is_probably_prime_1, p.get(), BN_prime_checks_for_generation, ctx(), false /* do_trial_division */, nullptr /* callback */)); EXPECT_EQ(1, is_probably_prime_1); ASSERT_TRUE(BN_primality_test( - &is_probably_prime_2, p.get(), BN_prime_checks, ctx(), + &is_probably_prime_2, p.get(), BN_prime_checks_for_generation, ctx(), true /* do_trial_division */, nullptr /* callback */)); EXPECT_EQ(1, is_probably_prime_2); ASSERT_TRUE(BN_enhanced_miller_rabin_primality_test( - &result_3, p.get(), BN_prime_checks, ctx(), nullptr /* callback */)); + &result_3, p.get(), BN_prime_checks_for_generation, ctx(), + nullptr /* callback */)); EXPECT_EQ(bn_probably_prime, result_3); } // BN_primality_test works with null |BN_CTX|. ASSERT_TRUE(BN_set_word(p.get(), 5)); - ASSERT_TRUE(BN_primality_test( - &is_probably_prime_1, p.get(), BN_prime_checks, nullptr /* ctx */, - false /* do_trial_division */, nullptr /* callback */)); + ASSERT_TRUE( + BN_primality_test(&is_probably_prime_1, p.get(), + BN_prime_checks_for_generation, nullptr /* ctx */, + false /* do_trial_division */, nullptr /* callback */)); EXPECT_EQ(1, is_probably_prime_1); }
diff --git a/crypto/fipsmodule/bn/prime.c b/crypto/fipsmodule/bn/prime.c index c0c795b..262822f 100644 --- a/crypto/fipsmodule/bn/prime.c +++ b/crypto/fipsmodule/bn/prime.c
@@ -210,7 +210,7 @@ }; // BN_prime_checks_for_size returns the number of Miller-Rabin iterations -// necessary for a 'bits'-bit prime. +// necessary for generating a 'bits'-bit candidate prime. // // // This table is generated using the algorithm of FIPS PUB 186-4 @@ -604,9 +604,8 @@ return ret; } -int BN_primality_test(int *out_is_probably_prime, const BIGNUM *w, - int iterations, BN_CTX *ctx, int do_trial_division, - BN_GENCB *cb) { +int BN_primality_test(int *out_is_probably_prime, const BIGNUM *w, int checks, + BN_CTX *ctx, int do_trial_division, BN_GENCB *cb) { // This function's secrecy and performance requirements come from RSA key // generation. We generate RSA keys by selecting two large, secret primes with // rejection sampling. @@ -679,8 +678,8 @@ } } - if (iterations == BN_prime_checks) { - iterations = BN_prime_checks_for_size(BN_num_bits(w)); + if (checks == BN_prime_checks_for_generation) { + checks = BN_prime_checks_for_size(BN_num_bits(w)); } BN_CTX *new_ctx = NULL; @@ -736,7 +735,7 @@ // 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, iterations); + constant_time_lt_w(uniform_iterations, checks); i++) { // Step 4.1-4.2 int is_uniform; @@ -765,7 +764,7 @@ } } - assert(uniform_iterations >= (crypto_word_t)iterations); + assert(uniform_iterations >= (crypto_word_t)checks); *out_is_probably_prime = 1; ret = 1; @@ -792,7 +791,7 @@ } int BN_enhanced_miller_rabin_primality_test( - enum bn_primality_result_t *out_result, const BIGNUM *w, int iterations, + enum bn_primality_result_t *out_result, const BIGNUM *w, int checks, BN_CTX *ctx, BN_GENCB *cb) { // Enhanced Miller-Rabin is only valid on odd integers greater than 3. if (!BN_is_odd(w) || BN_cmp_word(w, 3) <= 0) { @@ -800,8 +799,8 @@ return 0; } - if (iterations == BN_prime_checks) { - iterations = BN_prime_checks_for_size(BN_num_bits(w)); + if (checks == BN_prime_checks_for_generation) { + checks = BN_prime_checks_for_size(BN_num_bits(w)); } int ret = 0; @@ -848,7 +847,7 @@ // The following loop performs in inner iteration of the Enhanced Miller-Rabin // Primality test (Step 4). - for (int i = 1; i <= iterations; i++) { + for (int i = 1; i <= checks; i++) { // Step 4.1-4.2 if (!BN_rand_range_ex(b, 2, w1)) { goto err;
diff --git a/crypto/fipsmodule/rsa/rsa.c b/crypto/fipsmodule/rsa/rsa.c index 724de69..0830b05 100644 --- a/crypto/fipsmodule/rsa/rsa.c +++ b/crypto/fipsmodule/rsa/rsa.c
@@ -809,6 +809,11 @@ int ret = 1; // Perform partial public key validation of RSA keys (SP 800-89 5.3.3). + // Although this is not for primality testing, SP 800-89 cites an RSA + // primality testing algorithm, so we use |BN_prime_checks_for_generation| to + // match. This is only a plausibility test and we expect the value to be + // composite, so too few iterations will cause us to reject the key, not use + // an implausible one. enum bn_primality_result_t primality_result; if (BN_num_bits(key->e) <= 16 || BN_num_bits(key->e) > 256 || @@ -817,7 +822,8 @@ !BN_gcd(&small_gcd, key->n, g_small_factors(), ctx) || !BN_is_one(&small_gcd) || !BN_enhanced_miller_rabin_primality_test(&primality_result, key->n, - BN_prime_checks, ctx, NULL) || + BN_prime_checks_for_generation, + ctx, NULL) || primality_result != bn_non_prime_power_composite) { OPENSSL_PUT_ERROR(RSA, RSA_R_PUBLIC_KEY_VALIDATION_FAILED); ret = 0;
diff --git a/crypto/fipsmodule/rsa/rsa_impl.c b/crypto/fipsmodule/rsa/rsa_impl.c index 39dc789..74bf098 100644 --- a/crypto/fipsmodule/rsa/rsa_impl.c +++ b/crypto/fipsmodule/rsa/rsa_impl.c
@@ -1046,8 +1046,8 @@ if (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, BN_prime_checks, ctx, 0, - cb)) { + if (!BN_primality_test(&is_probable_prime, out, + BN_prime_checks_for_generation, ctx, 0, cb)) { goto err; } if (is_probable_prime) {
diff --git a/include/openssl/bn.h b/include/openssl/bn.h index 0ca9ad5..295ca62 100644 --- a/include/openssl/bn.h +++ b/include/openssl/bn.h
@@ -684,10 +684,22 @@ const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb); -// BN_prime_checks is magic value that can be used as the |checks| argument to -// the primality testing functions in order to automatically select a number of -// Miller-Rabin checks that gives a false positive rate of ~2^{-80}. -#define BN_prime_checks 0 +// BN_prime_checks_for_validation can be used as the |checks| argument to the +// primarily testing functions when validating an externally-supplied candidate +// prime. It gives a false positive rate of at most 2^{-128}. (The worst case +// false positive rate for a single iteration is 1/4, so we perform 32 +// iterations.) +#define BN_prime_checks_for_validation 32 + +// BN_prime_checks_for_generation can be used as the |checks| argument to the +// primality testing functions when generating random primes. It gives a false +// positive rate at most the security level of the corresponding RSA key size. +// +// Note this value only performs enough checks if the candidate prime was +// selected randomly. If validating an externally-supplied candidate, especially +// one that may be selected adversarially, use |BN_prime_checks_for_validation| +// instead. +#define BN_prime_checks_for_generation 0 // bn_primality_result_t enumerates the outcomes of primality-testing. enum bn_primality_result_t { @@ -698,7 +710,7 @@ // BN_enhanced_miller_rabin_primality_test tests whether |w| is probably a prime // number using the Enhanced Miller-Rabin Test (FIPS 186-4 C.3.2) with -// |iterations| iterations and returns the result in |out_result|. Enhanced +// |checks| iterations and returns the result in |out_result|. Enhanced // Miller-Rabin tests primality for odd integers greater than 3, returning // |bn_probably_prime| if the number is probably prime, // |bn_non_prime_power_composite| if the number is a composite that is not the @@ -706,12 +718,10 @@ // success and zero on failure. If |cb| is not NULL, then it is called during // each iteration of the primality test. // -// If |iterations| is |BN_prime_checks|, then a value that results in a false -// positive rate lower than the number-field sieve security level of |w| is -// used, provided |w| was generated randomly. |BN_prime_checks| is not suitable -// for inputs potentially crafted by an adversary. +// See |BN_prime_checks_for_validation| and |BN_prime_checks_for_generation| for +// recommended values of |checks|. OPENSSL_EXPORT int BN_enhanced_miller_rabin_primality_test( - enum bn_primality_result_t *out_result, const BIGNUM *w, int iterations, + enum bn_primality_result_t *out_result, const BIGNUM *w, int checks, BN_CTX *ctx, BN_GENCB *cb); // BN_primality_test sets |*is_probably_prime| to one if |candidate| is @@ -720,11 +730,9 @@ // // If |do_trial_division| is non-zero then |candidate| will be tested against a // list of small primes before Miller-Rabin tests. The probability of this -// function returning a false positive is 2^{2*checks}. If |checks| is -// |BN_prime_checks| then a value that results in a false positive rate lower -// than the number-field sieve security level of |candidate| is used, provided -// |candidate| was generated randomly. |BN_prime_checks| is not suitable for -// inputs potentially crafted by an adversary. +// function returning a false positive is at most 2^{2*checks}. See +// |BN_prime_checks_for_validation| and |BN_prime_checks_for_generation| for +// recommended values of |checks|. // // If |cb| is not NULL then it is called during the checking process. See the // comment above |BN_GENCB|. @@ -740,11 +748,9 @@ // // If |do_trial_division| is non-zero then |candidate| will be tested against a // list of small primes before Miller-Rabin tests. The probability of this -// function returning one when |candidate| is composite is 2^{2*checks}. If -// |checks| is |BN_prime_checks| then a value that results in a false positive -// rate lower than the number-field sieve security level of |candidate| is used, -// provided |candidate| was generated randomly. |BN_prime_checks| is not -// suitable for inputs potentially crafted by an adversary. +// function returning one when |candidate| is composite is at most 2^{2*checks}. +// See |BN_prime_checks_for_validation| and |BN_prime_checks_for_generation| for +// recommended values of |checks|. // // If |cb| is not NULL then it is called during the checking process. See the // comment above |BN_GENCB|. @@ -939,6 +945,12 @@ // Use |BN_bn2bin_padded| instead. It is |size_t|-clean. OPENSSL_EXPORT int BN_bn2binpad(const BIGNUM *in, uint8_t *out, int len); +// BN_prime_checks is a deprecated alias for |BN_prime_checks_for_validation|. +// Use |BN_prime_checks_for_generation| or |BN_prime_checks_for_validation| +// instead. (This defaults to the |_for_validation| value in order to be +// conservative.) +#define BN_prime_checks BN_prime_checks_for_validation + // Private functions