A researcher cracks crypto keys discovered in the wild using a 379-year-old technique

More On: Bitcoin

It simply takes a second to crack the small number of weak keys. Is there anything else out there?

A researcher reported on Monday that cryptographic keys generated using earlier software currently held by technology company Rambus are weak enough to be broken quickly using commodity hardware. This discovery is part of an examination that also turned out a number of weak keys in the wild.

According to a Rambus official, the software is based on a basic version of the SafeZone Crypto Libraries, which were developed by a firm named Inside Secure and bought by Rambus as part of its 2019 acquisition of Verimatrix. That version was deprecated prior to the acquisition and differs from the FIPS-certified version that the business now distributes under the Rambus FIPS Security Toolkit name.

Keep your Ps and Qs in order

According to Hanno Böck, the vulnerable SafeZone library fails to appropriately randomize the two prime integers required to produce RSA keys. (These keys are useful for encrypting Web traffic, shells, and other online connections.) Instead, after selecting one prime number, the SafeZone tool finds a prime number close by as the second one required to build the key.

"The issue is that both primes are overly similar," Böck explained in an interview. "As a result, the difference between the two primes is very modest." CVE-2022-26320 is the identifier for the SafeZone flaw.

Cryptographers have long known that RSA keys created with too near primes can be easily broken using Fermat's factorization approach. In 1643, French mathematician Pierre de Fermat presented this method for the first time.

Fermat's technique was founded on the principle that each odd integer may be represented as the difference between two squares. When the factors are close to the number's root, they can be calculated quickly and easily. When elements are truly random and hence far apart, the method is not practical.

The difficulty of factoring a key's huge composite number (typically indicated as N) to obtain its two factors determines the security of RSA keys (usually denoted as P and Q). When P and Q are made public, the key they create is broken, which means that anybody can decode data protected by the key or use it to authenticate communications.

Böck has uncovered only a few keys in the wild that are vulnerable to the factorization attack thus far. Some of the keys are from printers made by Canon and Fujifilm (originally branded as Fuji Xerox). The keys can be used by printer users to generate a Certificate Signing Request. All of the weak keys were created in 2020 or later. CVE-2022-26351 is assigned to the vulnerable Canon keys.

Böck also discovered four insecure PGP keys on SKS PGP key servers, which are usually used to encrypt email. A user ID associated with the keys suggested they were created for testing, so he doesn't believe they're in use.

Böck believes that all of the keys he discovered were produced using software or methods unrelated to the SafeZone library. If this is the case, additional software that creates keys could be easily cracked using the Fermat method. It's possible that the keys were generated by hand, "perhaps by someone knowledgeable of the attack providing test data," according to Böck.

The researcher discovered the keys by combing through billions of public keys to which he had access. He also examined keys given with him by other researchers as well as keys made public through certificate transparency schemes.

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 finding of these keys does not indicate that they have posed a significant security risk, especially as none of them are utilized for extremely sensitive applications. However, it's possible that the discovery points to a bigger issue, and that more vulnerable keys or key-generation software are still in circulation.

People who own a vulnerable printer should contact the manufacturer to see if a firmware upgrade is available to replace the faulty keys. Let's Encrypt has also added a checker to detect keys with primes that are too close together.

** Information on these pages contains forward-looking statements that involve risks and uncertainties. Markets and instruments profiled on this page are for informational purposes only and should not in any way come across as a recommendation to buy or sell in these assets. You should do your own thorough research before making any investment decisions. All risks, losses and costs associated with investing, including total loss of principal, are your responsibility. The views and opinions expressed in this article are those of the authors and do not necessarily reflect the official policy or position of USA GAG nor its advertisers. The author will not be held responsible for information that is found at the end of links posted on this page.