Cryptographic keys generated with older software now owned by technology company Rambus are weak enough to be broken instantly using commodity hardware, a researcher reported on Monday. This revelation is part of an investigation that also uncovered a handful of weak keys in the wild.
The software comes from a basic version of the SafeZone Crypto Libraries, which were developed by a company called Inside Secure and acquired by Rambus as part of its 2019 acquisition of Verimatrix, a Rambus representative said. That version was deprecated prior to the acquisition and is distinct from a FIPS-certified version that the company now sells under the Rambus FIPS Security Toolkit brand.
Mind your Ps and Qs
Researcher Hanno Böck said that the vulnerable SafeZone library doesnât sufficiently randomize the two prime numbers it used to generate RSA keys. (These keys can be used to secure Web traffic, shells, and other online connections.) Instead, after the SafeZone tool selects one prime number, it chooses a prime in close proximity as the second one needed to form the key.
âThe problem is that both primes are too similar,â Böck said in an interview. âSo the difference between the two primes is really small.â The SafeZone vulnerability is tracked as CVE-2022-26320.
Cryptographers have long known that RSA keys that are generated with primes that are too close together can be trivially broken with Fermatâs factorization method. French mathematician Pierre de Fermat .
Fermatâs algorithm was based on the fact that any odd number can be expressed as the difference between two squares. When the factors are near the root of the number, they can be calculated easily and quickly. The method isnât feasible when factors are truly random and hence far apart.
The security of RSA keys depends on the difficulty of factoring a keyâs large composite number (usually denoted as N) to derive its two factors (usually denoted as P and Q). When P and Q are known publicly, the key they make up is broken, meaning anyone can decrypt data protected by the key or use the key to authenticate messages.
So far, Böck has identified only a handful of keys in the wild that are vulnerable to the factorization attack. Some of the keys are from printers from two manufacturers, Canon and Fujifilm (originally branded as Fuji Xerox).Printer users can use the keys to generate a Certificate Signing Request. The creation date for the all the weak keys was 2020 or later. The weak Canon keys are tracked as CVE-2022-26351.
Böck also found four vulnerable PGP keys, typically used to encrypt email, on SKS PGP key servers. A user ID tied to the keys implied they were created for testing, so he doesnât believe theyâre in active use.
Böck said he believes all the keys he found were generated using software or methods not connected to the SafeZone library. If true, other software that generates keys might be easily broken using the Fermat algorithm. Itâs plausible that the keys were generated manually, âpossibly by people aware of this attack creating test data,â Böck said.
The researcher found the keys by searching through billions of public keys that he had access to. He also looked at keys that were shared with him by other researchers and keys that were available through certificate transparency programs.
Too close for comfort
In explaining the vulnerability, Böck wrote:
The idea of Fermatâs factorization algorithm is that a product of two large primes can always be written as N=(a-b)(a+b), with a being the middle between the two primes and b the distance from the middle to each of the primes.
If the primes are close then a is close to the square root of N. This allows guessing the value a by starting with the square root of N and then incrementing the guess by one each round.
For each guess, we can calculate b^2 = a^2 - N. If the result is a square, we know we have guessed a correctly. From this, we can calculate p=a+b and q=a-b.
Fermat described this algorithm originally in a letter in 1643. The text of the original letter can be found in Oeuvres de Fermat, page 256, available at the Internet Archive.
He continued:
How can this happen?
An RSA library is vulnerable if the two primes p and q are close. If the primes are generated independently and randomly, then the likelihood of p and q being close is negligible.
An RSA library might, however, implement a flawed key generation algorithm like this:
- Generate random number X.
- Search the next prime after X and use it as p.
- Search the next prime after p and use it as q.
For common RSA key sizes, this creates p and q with a difference that is usually in the thousands or lower. This can easily be broken with Fermatâs factorization method.
How âcloseâ do primes need to be in order to be vulnerable?
With common RSA key sizes (2048 bit) in our tests, the Fermat algorithm with 100 rounds reliably factors numbers where p and q differ up to 2^517. In other words, it can be said that primes that only differ within the lower 64 bytes (or around half their size) will be vulnerable.
Up to 2^514 it almost always finds the factorization in the first round of the algorithm. It could be argued that the 100 rounds is therefore excessive; however, the algorithm is so fast that it practically does not matter much.
Can vulnerable keys be generated by accident if primes are generated randomly and independently?
This is almost impossible. For primes to be âcloseâ they would have to be identical at least on their upper 500 bits. The chance of that happening is therefore smaller than 1:2^500.
The discovery of these keys doesnât indicate that theyâve created much of a security risk, particularly because none of them are used for especially sensitive applications. Still, itâs possible that the discovery indicates a larger problem and that more vulnerable keys or key-generation software are still out there.
People who own a vulnerable printer should check with the manufacturer to find out if thereâs a firmware update that will replace the weak keys. Letâs Encrypt has also implemented a checker that will detect keys with primes that are too close together.
Listing image: Getty Images