RSA keys need to conform to certain mathematical properties in order to be secure. If the key is not generated carefully it can have vulnerabilities which may totally compromise the encryption algorithm. Sometimes this can be determined from the public key alone. This article describes vulnerabilities that can be tested when in possession of a RSA public key.

RSA is an asymmetric encryption algorithm that works with a public and private key, together called a key pair. A key pair is generated by taking two secret random primes and calculating the keys from them. If this is done incorrectly it may be possible to reconstruct the primes and calculate the private key, thus defeating the security of the system.

There are many attacks against key pairs, which are described below. These vulnerabilities are just in the key pair. An RSA implementation may have vulnerabilities of its own even if the used keys are secure.

Most of these vulnerabilities can be automatically tested by RsaCtfTool, which tries most of the mentioned attacks given one or more public keys.

Single key weaknesses

If you have a single public key, there are already several things you can test to determine whether the key is secure.

Modulus too small

If the RSA key is too short, the modulus can be factored by just using brute force. A 256-bit modulus can be factored in a couple of minutes. A 512-bit modulus takes several weeks on modern consumer hardware. Factoring 1024-bit keys is definitely not possible in a reasonable time with reasonable means, but may be possible for well equipped attackers. 2048-bit is secure against brute force factoring.

Try it: smallkey.pem is a small public key. Can you find the corresponding private key?

Low private exponent

Decrypting a message consists of calculating cd mod N. The smaller d is, the faster this operation goes. However, Wiener found a way to recover d (and thus the private key) when d is relatively small. Boneh and Durfee improved this attack to recover private exponents that are less than N0.292.

If the private exponent is small, the public exponent is necessarily large. If you encounter a public key with a large public exponent, it may be worth it to run the Boneh-Durfee attack against it.

Try it: smalld.pem

Low public exponent

Encrypting is performed by calculating me mod N. Here e is a low number that is relative prime to N. A common choice is e = 3. Having a low public exponent makes the system vulnerable to certain attacks if used incorrectly. If the same message is encrypted by three separate keys, the security breaks and the message can be recovered. However, RSA should only be used with randomized padding which prevents this and related attacks. With proper padding it is totally fine to use a low public exponent, so this is not really a vulnerability.

p and q close together

When creating the key, two random primes p and q are multiplied. Consider what happens when pq. Then Np2 or p ≈ √N. In that case, N can be efficiently factored using Fermat’s factorization method.

Fermat’s algorithm searches for an a and b such that N = a2 - b2. In that case, N is factorable as (a + b)(a - b). If p and q are close together, a is close to √N and b is small, making them easy to find.

Try it:

Unsafe primes

When multiplying two primes, the result is almost always hard to factor. However, it turns out that if at least one of the primes conforms to certain conditions there is a shortcut to factor the result.

In practice the chance is negligible that a prime you pick at random conforms to one of these formats. Some key generation algorithms create “strong primes” where p - 1 and p + 1 have large prime factors and are thus not smooth.

Try it:

May 2008 Debian OpenSSH bug

To create a random key, a good cryptographic random number generator is required. Between 2006 and 2008 Debian had a bug where the random number generator was improperly seeded, resulting in predictable keys.

In the Debian branch of OpenSSL, a line was removed that seeded the random number generator, because it generated compiler warnings. This resulted in insufficiently random data to generate good keys, which means many keys are the same, even if they were generated on different systems.

Try it: debian.pub

Public exponent leaks factor of λ(N)

The public exponent e needs to be coprime with λ(N). The most often used public exponent (65537) is not necessarily coprime when selecting two random primes p and q. Some key generation programs solve this by starting with 65537 and increasing it until a coprime number is found:

e = 65537
while GCD(e, λ(N)) != 1 {
    e = e + 2;
}

This means that if a public key has a public exponent of 65539, it is divisible by 65537. If it has an exponent of 65541, it is divisible by both 65537 and 65539, and so on. The public exponent leaks information on the private key by being generated this way.

Try it: leake.pem

Example keys

What do you do when as a developer you need a key pair and don’t know exactly how it works? The same way you do for all your code, you copy-paste it from StackOverflow. Example keys in software implementations, web sites or protocol specifications may end up in software. Multiple implementations then use the same key, and the private key is available for everyone in the documentation or on the internet.

Try it:

e = 1

Encryption is done by calculating me. If e = 1, this operation does nothing and the message is not encrypted. The message may still be padded but otherwise is just plain text and not encrypted at all.

Try it: eone.pem

Prime N

Normally, two primes compose the modulus. However, you could also use three primes, or one prime. In the case of one prime, however, the private key is not very secret. Normally the chosen p and q are secret and you publish N, but in single-factor RSA you choose one number that you also publish.

Try it: nprime.pem

Relations between multiple keys

If you have multiple keys, there may be relations between the keys that are interesting to search for.

Shared N

If two keys have the same modulus, they also have the same p and q and can calculate each other’s private key. This may not be a problem if both keys belong to the same person.

Try it: Can you use the sharedn1.pem private key to obtain the private key of the sharedn2 public key?

Shared p or q

Devices that create their private key on first boot may not have enough entropy to create a random number. What sometimes happens is that this results in keys that have a different modulus but have one factor in common. In that case the greatest common divisor of the two moduli can be efficiently calculated to factor the modulus and recover the private key.

In some cases, even if two keys don’t have the exact same factor but the factor is close, both keys can be broken.

Try it:

Conclusion

There is a lot that can go wrong when creating RSA keys, especially when using a non-standard RSA-like cryptosystem. When finding a RSA public key during a test, make sure to test it for the vulnerabilities listed above.

Read more

Key testing software

Overview

Small prime differences

Shared p or n

Unsafe primes

Small keys

Unsafe public exponent

Partial key exposure

Small private exponent

Other