1602379 - Don't use rand in MPI primality testing

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P2)

Description

[Franziskus Kiefer [:franziskus]]

As noticed before (e.g. bug 1215751), mpi uses rand for primality testing.
While this wasn't considered critical so far Kenny Paterson and others pointed out that this may lead to serious problems. As described in [1] it is possible to generate composite numbers that pass the MR test if the used bases aren't random.
Since mpp_pprime uses rand but never calls srand this is the case here.

mpp_pprime is used for primality testing in two cases:
i) checking DSA parameters [2]
ii) RSA prime generation [3]. NSS allows to import partial RSA keys and computes missing parameters from them. For example, given 2 exponents and the modulus it factors the modulus to get the 2 missing primes.
Both functions operate on potentially adversarial input. So this is a security issue.

I recommend to use a proper RNG here. Unfortunately, using the existing RNG in freebl is not possible without changing how this is built.

[1] https://eprint.iacr.org/2018/749
[2] https://searchfox.org/nss/rev/9e4fe37a527b07fe2d280a134abe25cf02eb43dd/lib/freebl/pqg.c#1621
[3] https://searchfox.org/nss/rev/ce7d80af16477b22af4c9bb5d60bdc32541e4b50/lib/freebl/rsa.c#744

Comment 1

[Martin Thomson [:mt:]]

Can we rely on a global function pointer for this? We can use PR_CallOnce() to populate it from BL_Init() or RSA_Init(). It's not ideal, but I don't see much hope for an alternative. RSA already depends on globals. It's annoying to get all the locking right, but we're constrained by the shape of the API.

Comment 2

[J.C. Jones [:jcj] (he/they)]

A global function pointer seems like it should work, and would be the right way to fix it, but just for argument's sake, since to my knowledge M-R doesn't need cryptographically-strong randomness, it just needs to not be too predictable about what psuedoprime composites it could fail with, what about either:

1. Initialize srand with a uint from the real CSPRNG, maybe during RNG_SystemInfoForRNG, or
2. Initialize srand with the timestamp once using PR_CallOnce on the way in, or maybe also during RNG init?

(I don't know why we'd do #2 if #1 is an option, but I'm just typing here).

Comment 3

[Martin Thomson [:mt:]]

Given that the cost of doing either is - at least in terms of engineering - not dissimilar to just using a good PRNG, I'm inclined to say that we just the good PRNG here. We have the PRNG function, we just need to hook it in.

I didn't read the paper closely enough to know for sure, but I'd be concerned that the internal state of rand() might be probed and then the key generation process timed so that weak primes are produced. Think about WebCrypto or WebRTC certificates. I don't know if there is any way rand() state could be read from the web, but it's not worth contemplating the outcome.

Comment 4

[Franziskus Kiefer [:franziskus]]

After getting the code to generate the pseudo-primes from Jake I successfully generated one that passes two rounds of mpp_pprime. This means it is possible to generate RSA keys with pseudo-primes that NSS happily imports.
The DSA case seems safe as it uses at least 40 rounds of MR.

Comment 5

[John Schanck [:jschanck]]

Attachment: Bug 1602379 - Provide secure variants of mpp_pprime and mpp_make_prime. r=mt

Comment 6

[John Schanck [:jschanck]]

https://hg.mozilla.org/projects/nss/rev/b83ad33acd678c78c91b836ad42310e75cac3361