Researcher uses 600-year-old algorithm to crack crypto keys found in the wild

Stylized illustration of keys.

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 Bock 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 first described this method in 1643.

Fermat’s algorithm was based on the fact that any 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 belong to printers originally branded as Fuji Xerox and now belonging to Canon. Printer users can use the keys to generate a Certificate Signing Request. The creation date for the 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 also that the keys were generated manually, “possibly by people aware of this attack creating test data.”

The researcher found the keys by searching through billions of public keys that he either had access to, were shared with him by other researchers, or 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=(ab)(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=ab.

Fermat described this algorithm originally in a letter in 1643. The text of the original letter can be found in Fermat’s workspage 256, available at the Internet Archive.

I have 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.

Leave a Reply

Your email address will not be published.