CVE 2018 1000180

Extracts from the original Jira Issue

Description

Standard FIPS PUB 186-4 defines the necessary rounds of M-R testing when generating primes for use in RSA digital signature. The implementation of RsaKeyPairGenerator contains a method that is responsible to provide the number of required rounds to ensure an error probability of 2^(-100) according to FIPS PUB 186-4, Table C.3 (RsaKeyPairGenerator::getNumberOfIterations())

The error occurs in the use of the method RsaKeyPairGenerator::getNumberOfIterations(). This method expects in parameter 1 the bitlength of the number to be tested. Instead the implementation uses the length of the key to be generated (e.g. 1024 Bit), but FIPS 186-4, Table C.3 makes a statement about the length of the prime factors p and q. They usually should have something like key_length/2. Especially for keys less than 2048 bit key length, the required iterations should be 7, instead the implementation delivers a value of 4 (which would be in our opinion correct for key sizes from 2048 Bit).

In RsaKeyPairGenerator::init() the use of RsaKeyPairGenerator::getNumberOfIterations() should be corrected to use an estimated bitlength of p and q or the estimation should be computed when p and q have been generated.

Workaround Details

There's a work around, and some level of additional coverage.

To get correct 2^-100 for different RSA modulus sizes, you can work around with the following certainty values:

     >= 3072: 100 (not affected)
else >= 2048: 128
else >= 1536: 134
else >= 1024: 116
else >= 512: 186
else 100 (not affected)

The certainty value usually doesn't impact RSA keygen performance that much (because the majority of candidate primes fail at the first M-R test). You might want to just pick the highest value.

Further to this we actually use BigInteger to generate the prime candidates (with certainty 1), which does do 1 M-R round plus a "Lucas Lehmer" test - it's difficult to quantify this last one as a direct comparison to extra M-R rounds, but it would mean for a 1024 bit key that the 1024 condition of at least 2^-80 would be met. These extra tests do mean the API in addition to having the correct value for 3072, will be mostly correct for 2048 bit keys (outside of the certainty range [113-127] where there are 2 missing M-R tests, which drops to 1 due to the BigInteger test, although there is the additional "Lucas Lehmer" test). Using the adjusted certainty values above does guarantee that the full number of M-R tests is satisfied directly by the Bouncy Castle API (the Java BigInteger tests are still done, but you can regard them as extras).

Fixes

Patch issues for BC-FJA 1.0.1, issue removed for BC-FJA 1.0.2 and later.