Use a higher iteration limit for RSA key generation at e = 3.
Generating a 2048-bit RSA key with e = 3 (don't do this), the failure
rate at 5*bits iterations appears to be around 7 failures in 1000 tries.
Bump the limit up to 32*bits. This should give a failure rate of around
2 failures in 10^14 tries.
(The FIPS 186-4 algorithm is meant for saner values of e, like 65537. e
= 3 implies a restrictive GCD requirement: the primes must both be 2 mod
3.)
Change-Id: Icd373f61e2eb90df5afaff9a0fc2b2fbb6ec3f0a
Reviewed-on: https://boringssl-review.googlesource.com/22584
Commit-Queue: David Benjamin <davidben@google.com>
Commit-Queue: Adam Langley <agl@google.com>
Reviewed-by: Adam Langley <agl@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
diff --git a/crypto/fipsmodule/rsa/rsa_impl.c b/crypto/fipsmodule/rsa/rsa_impl.c
index b89eccb..adbb69f 100644
--- a/crypto/fipsmodule/rsa/rsa_impl.c
+++ b/crypto/fipsmodule/rsa/rsa_impl.c
@@ -807,11 +807,16 @@
return 0;
}
- // Ensure the bound on |tries| does not overflow.
- if (bits >= INT_MAX/5) {
+ // See FIPS 186-4 appendix B.3.3, steps 4 and 5. Note |bits| here is nlen/2.
+
+ // Use the limit from steps 4.7 and 5.8 for most values of |e|. When |e| is 3,
+ // the 186-4 limit is too low, so we use a higher one. Note this case is not
+ // reachable from |RSA_generate_key_fips|.
+ if (bits >= INT_MAX/32) {
OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
return 0;
}
+ int limit = BN_is_word(e, 3) ? bits * 32 : bits * 5;
int ret = 0, tries = 0, rand_tries = 0;
BN_CTX_start(ctx);
@@ -820,8 +825,6 @@
goto err;
}
- // See FIPS 186-4 appendix B.3.3, steps 4 and 5. Note |bits| here is
- // nlen/2.
for (;;) {
// Generate a random number of length |bits| where the bottom bit is set
// (steps 4.2, 4.3, 5.2 and 5.3) and the top bit is set (implied by the
@@ -890,7 +893,7 @@
// If we've tried too many times to find a prime, abort (steps 4.7 and
// 5.8).
tries++;
- if (tries >= bits * 5) {
+ if (tries >= limit) {
OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS);
goto err;
}
