openssl: RSA key generation fails sporadically when under high load since OpenSSL 3.0.2

Since running with OpenSSL 3.0.2 we encounter sporadic RSA key generation failures. EVP_PKEY_keygen() fails but no error is set (ERR_print_errors_fp() shows nothing). This seems to be workload dependent, it seems to happen only if key gens a running concurrently (in different processes though).

I have debugged this and it turned out that it fails in ossl_bn_rsa_fips186_4_derive_prime() (file crypto/bn/bn_rsa_fips186_4.c) at step 8-10, where i >= imax. So it just took too many loops to derive the prime…

            /* (Step 8-10) */
            if (++i >= imax || !BN_add(Y, Y, r1r2x2))
                goto err;

What is an application program supposed to do in such case ? Just retry the key gen?

Would also be nice if an appropriate error could be set in that case, so that the application has a chance to identify this situation.

I understand that you don’t want run the loop forever, but now the problem is just pushed to the application deciding how often to retry the RSA key gen…

In my case it happens for 2048 or 4096 bit keys, with an given public exponent of 3. I haven’t seen it for any other public exponent so far… Maybe a such small public exponent of 3 makes it more likely to required many iterations?

What is the reason for the too many loops being driven? Could it be that the random pool is depleted, because too many random bytes are read in relatively short time? Would this lead to such situation? Shouldn’t the random-read just block until the entropy pool has been filled up instead?

This did not fail on OpenSSL 1.1.1. I can’t tell if it also failed with earlier OpenSSL 3.0 releases…

About this issue

Original URL
State: closed
Created 2 years ago
Comments: 18 (18 by maintainers)

Commits related to this issue

RSA keygen fixes Fixes #18321 Increase the iteration factor used when 'Computing a Probable Prime Factor Based on Auxiliary Primes' from 5 to 20. This matches the algorithm update made in FIPS 186-5... — committed to slontis/openssl by slontis 2 years ago
RSA keygen fixes Fixes #18321 Increase the iteration factor used when 'Computing a Probable Prime Factor Based on Auxiliary Primes' from 5 to 20. This matches the algorithm update made in FIPS 186-5... — committed to openssl/openssl by slontis 2 years ago
RSA keygen fixes Fixes #18321 Increase the iteration factor used when 'Computing a Probable Prime Factor Based on Auxiliary Primes' from 5 to 20. This matches the algorithm update made in FIPS 186-5... — committed to sftcd/openssl by slontis 2 years ago

Most upvoted comments

May be something like this (untested) would do it for check the exponent and if it is < 2¹⁶, use the old path:

 crypto/rsa/rsa_gen.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/crypto/rsa/rsa_gen.c b/crypto/rsa/rsa_gen.c
index ac64483e6a..1cf473720c 100644
--- a/crypto/rsa/rsa_gen.c
+++ b/crypto/rsa/rsa_gen.c
@@ -427,10 +427,11 @@ static int rsa_keygen(OSSL_LIB_CTX *libctx, RSA *rsa, int bits, int primes,
     int ok = 0;
 
     /*
-     * Only multi-prime keys or insecure keys with a small key length will use
-     * the older rsa_multiprime_keygen().
+     * Only multi-prime keys or insecure keys with a small key length and
+     * public exponents < 2^16 will use the older rsa_multiprime_keygen().
      */
-    if (primes == 2 && bits >= 2048)
+    if (primes == 2 && bits >= 2048 &&
+        (e_value == NULL || BN_num_bits(e_value) > 16))
         ok = ossl_rsa_sp800_56b_generate_key(rsa, bits, e_value, cb);
 #ifndef FIPS_MODULE
     else

ifranzki on May 30, 2022

OTC: three steps are needed here:

check the exponent and if it is < 2¹⁶, use the old path (FIPS does not allow this);
change the number of iterations from 5* to 20* as per FIPS 186-5 and
raise an error message on failure.

This is a bug and any fixes should go into 3.0.

paulidale on May 24, 2022

One option would be to fall back to the old key generation algorithm when public exponent is < 65537 (in default provider).

t8m on May 16, 2022