8216012: Infinite loop in RSA KeyPairGenerator

[Valerie Peng]

Hi Masanori Yano,

I can help sponsoring this fix. However, as it's a P4, it may be  
targeted to 15 depending on the available cycles.

Are you a contributor for OpenJDK?

If not, please see http://openjdk.java.net/contribute/ for the process.

Thanks,
Valerie
On 10/8/2019 8:10 PM, yano-masanori at fujitsu.com wrote:
> Hello.
>
> I would like to contribute for JDK-8216012.
>
> The cause of this problem is RSAKeyPairGenerator that doesn't check
> the public exponent even though the algorithm of rsa key generation
> can use only odd exponent number.
>
> To generate a KeyPair, the RSAKeyPairGenerator finds two random primes
> P and Q, and calculate Phi = (P - 1) * (Q - 1). If Phi is not relative
> prime to exponent, RSAKeyPairGenerator retry from the first.
>
> The value of Phi must be an even number because P and Q are odd numbers.
> If exponent is an even number, the greatest common divisor cannot
> be 1 because one of common divisors is 2 which is bigger than 1.
> Therefore, generateKeyPair() method of RSAKeyPairGenerator cannot exit
> the retrying loop.
>
> To solve this problem, I propose to check whether the public exponent
> is even number.
>
> Please sponsor the following change.
>
> diff --git a/src/java.base/share/classes/sun/security/rsa/RSAKeyPairGenerator.java b/src/java.base/share/classes/sun/security/rsa/RSAKeyPairGenerator.java
> --- a/src/java.base/share/classes/sun/security/rsa/RSAKeyPairGenerator.java
> +++ b/src/java.base/share/classes/sun/security/rsa/RSAKeyPairGenerator.java
> @@ -96,6 +96,10 @@
>                   throw new InvalidAlgorithmParameterException
>                           ("Public exponent must be 3 or larger");
>               }
> +            if (!tmpPublicExponent.testBit(0)) {
> +                throw new InvalidAlgorithmParameterException
> +                        ("Public exponent must be an odd number");
> +            }
>               if (tmpPublicExponent.bitLength() > tmpKeySize) {
>                   throw new InvalidAlgorithmParameterException
>                           ("Public exponent must be smaller than key size");
> diff --git a/test/jdk/sun/security/rsa/TestKeyPairGeneratorExponent.java b/test/jdk/sun/security/rsa/TestKeyPairGeneratorExponent.java
> new file mode 100644
> --- /dev/null
> +++ b/test/jdk/sun/security/rsa/TestKeyPairGeneratorExponent.java
> @@ -0,0 +1,65 @@
> +import java.math.BigInteger;
> +
> +import java.security.*;
> +import java.security.interfaces.*;
> +import java.security.spec.*;
> +
> +/**
> + * @test
> + * @bug 8216012
> + * @summary Tests the RSA public key exponent for KeyPairGenerator
> + * @run main/timeout=60 TestKeyPairGeneratorExponent
> + */
> +public class TestKeyPairGeneratorExponent {
> +    private static int keyLen = 512;
> +
> +    private static BigInteger[] validExponents = new BigInteger[] {
> +        RSAKeyGenParameterSpec.F0,
> +        RSAKeyGenParameterSpec.F4,
> +        // Since 512-bit exponent is larger than  modulus, fails in RSAPublicKeyImpl.checkExponentRange().
> +        BigInteger.ONE.shiftLeft(keyLen - 1).subtract(BigInteger.ONE)
> +    };
> +
> +    private static BigInteger[] invalidExponents = new BigInteger[] {
> +        BigInteger.valueOf(-1),
> +        BigInteger.ZERO,
> +        BigInteger.ONE,
> +        // 8216012: An even number causes infinite loop.
> +        BigInteger.valueOf(4),
> +        BigInteger.ONE.shiftLeft(keyLen)
> +    };
> +
> +    public static void testValidExponents(KeyPairGenerator kpg, BigInteger exponent) {
> +        try {
> +            kpg.initialize(new RSAKeyGenParameterSpec(keyLen, exponent));
> +            kpg.generateKeyPair();
> +        } catch(InvalidAlgorithmParameterException iape){
> +            throw new RuntimeException("Unexpected Exception: " + iape);
> +        }
> +    }
> +
> +    public static void testInvalidExponents(KeyPairGenerator kpg, BigInteger exponent) {
> +        try {
> +            kpg.initialize(new RSAKeyGenParameterSpec(keyLen, exponent));
> +            kpg.generateKeyPair();
> +            throw new RuntimeException("Expected InvalidAlgorithmParameterException was not thrown.");
> +        } catch(InvalidAlgorithmParameterException iape){
> +            // Expected InvalidAlgorithmParameterException was thrown.OK
> +        }
> +    }
> +
> +    public static void main(String[] args) throws Exception {
> +        Provider provider = Security.getProvider("SunRsaSign");
> +        KeyPairGenerator kpg;
> +
> +        for(BigInteger validExponent : validExponents) {
> +            kpg = KeyPairGenerator.getInstance("RSA", provider);
> +            testValidExponents(kpg, validExponent);
> +        }
> +
> +        for(BigInteger invalidExponent : invalidExponents) {
> +            kpg = KeyPairGenerator.getInstance("RSA", provider);
> +            testInvalidExponents(kpg, invalidExponent);
> +        }
> +    }
> +}
>
> Regards,
> Masanori Yano