Given only RSA public key parameters, what security issues might I be able to detect?

Question

I'm attempting to automate some checks against a large list of .NET assemblies, and want to include a test to see if the RSA parameters used to sign the assemblies are sensible. However, since I don't have access to their private keys, I'm wondering how far I can go.

At the moment I'm reporting if:

• The modulus $n$ is smaller than 1024 bits (issue)
• The exponent $e$ is not 65537 (informational)

The latter is reported due to it being unusual, rather than a flaw in the cryptography, as I've never come across a case where a signed .NET binary uses anything other than 65537.

Are there any other checks I can perform, given only this limited data?

Answer 1

The tests you can do depend on how much time you want to spend for checking each certificate and the "stupidity" you assume for the given key-owner.

You already mentioned the basic checks:

• Modulus is too small, only interesting if it's smaller than 1024 bits
• Exponent is unusual, not exactly a vulnerability in most cases

The following attacks may take more or less time but applying each of them will give you high assurances that the parameters are indeed not vulnerable. This can be read as a list of techniques for factoring given moduli.

The following techniques are rather fast and may be applied to each modulus.

• Check for GCD > 1 with a given database. For example get a database of many certificates and apply the GCD algorithm to each pair, if the GCD is larger than 1 you've found a non-trivial factor.
• Check for the Debian RNG vulnerability. Although the vulnerability is quite old you might get "lucky" and find a vulnerable key.
• Check if the modulus is a perfect power. This is highly unlikely but can be verified extremely fast, as proposed by Ricky Demer in the comments.
• Check if the modulus is a prime, for example using the Miller-Rabin test. If it is a prime it's obviously an invalid modulus, making it possible although unlikely.
• Check if $|p-q|$ is small. If so the Fermat factoring (or more advanced version) will quickly factor the modulus. This is highly unlikely as well.

The last few techniques are rather slow and may not be applicable in the given setting due to time constraints.

• If you suspect the modulus to contain a few large (128-bit) primes you can try and apply the elliptic curve method. This is rather unusual for RSA moduli.
• If you suspect that the modulus isn't composed of safe primes you may want to give Pollard's p-1 and Williams p+1 algorithm a try.
• If you suspect the private exponent to be small you can try to apply Wiener's attack.