1012786 - PK11_GenerateKeyPair can intermittently fail even with a strong random source

Status: NEW

(NSS :: Libraries, defect, P3)

Description

[Dana Keeler (she/her) [:keeler]]

Attachment: pk11test.c

See bug 1002814 comment 14:

What I'm seeing is that RSA_NewKey is occasionally failing with SEC_ERROR_NEED_RANDOM (which gets unhelpfully translated to CKR_FUNCTION_FAILED and then SEC_ERROR_PKCS11_FUNCTION_FAILED by the time PK11_GenerateKeyPair reports the error to GenerateKeyPair in pkixtestutil.cpp). My plan is to modify GenerateKeyPair to attempt to add some entropy and then retry when PK11_GenerateKeyPair fails.

I'm attaching a minimal testcase that reproduces this bug (after ~300 key generations on my machine).

Comment 1

[Ryan Sleevi]

As this comment scared the bejesus out of me (as NSS on a system without quality entropy = scary), it seems to be related to http://mxr.mozilla.org/nss/source/lib/freebl/rsa.c#278

RSA_NewKey attempts up to MAX_KEY_GEN_ATTEMPTS (which is 10) tries to generate a new RSA key pair, which fails if either of the following is true:
- n (p*q) has a leading zero bit (mpl_significant_bits(&n) != keySizeInBits)
- phi(n) and e have no common divisors

Statistically, even with a strong random source, this is possible.

Note that OpenSSL doesn't perform the first check - it does allow for 1023-bit keys, for example (as do several other systems). Additionally, OpenSSL does not put a limit on the number of times it attempts to generate a key (with the exception of degenerate keys when keys are too small and it keeps generating p == q)

Comment 2

[Dana Keeler (she/her) [:keeler]]

Sorry - I guess "non-fatally" isn't exactly what I meant.