Attacking RSA keys
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 p ≈ q. Then N ≈ p2 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.
- Pollard’s p − 1 algorithm: p - 1 is powersmooth.
- Williams’s p + 1 algorithm: p + 1 is smooth.
- Cheng’s elliptic curve algorithm: 4p − 1 has the form db2 where d ∈ {3,11,19,43,67,163}
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
- FactHacks
- Twenty Years of Attacks on the RSA Cryptosystem
- Possible Attacks on RSA
- Exploring 3 insecure usage of RSA
- Ron was wrong, Whit is right
- The properties of RSA key generation process in software libraries
- Survey: Lattice Reduction Attacks on RSA
- 15 ways to break RSA security
Small prime differences
- Mathematical attack on RSA
- Cryptanalysis of RSA with Small Prime Difference
- The Fermat factorization method revisited
- Finding close-prime factorizations
Shared p or n
- Understanding Common Factor Attacks: An RSA-Cracking Puzzle
- Finding Duplicate RSA Moduli in the Wild
- Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices
- Implicit factorization of unbalanced RSA moduli
Unsafe primes
- A New Class of Unsafe Primes
- I want to break square-free: The 4p-1 factorization method and its RSA backdoor viability
Small keys
Unsafe public exponent
- RSA and a higher degree diophantine equation
- Cryptanalysis of RSA with constrained keys
- A New Vulnerable Class of Exponents in RSA
Partial key exposure
Small private exponent
- A Generalized Wiener Attack on RSA
- RSA Cryptanalysis with Increased Bounds on the Secret Exponent using Less Lattice Dimension
- A new attack on RSA with a composed decryption exponent