Fermat Attack on RSA

Fermat Attack on RSA

Introduction

In 1643 Pierre de Fermat developed a factorization algorithm. The algorithm allows efficiently calculating the prime factors of a composite number that is the product of two "close" primes.

The RSA encryption and signature algorithm relies on the fact that factorization of large numbers is a hard problem. The RSA public key contains a composite number (usually called N) that is the product of two primes (usually called p and q).

If RSA keys are generated with "close" primes then RSA can be broken with Fermat's factorization algorithm. While this is widely known, to my knowledge no such vulnerable RSA keys have been found in the wild before - up until now.

I applied Fermat's factorization method to large datasets of public RSA keys. I discovered a small number of vulnerable keys that belonged to printers from Canon and Fujifilm (originally branded as Fuji Xerox). The devices from Fujifilm use an underlying cryptographic module from the company Rambus.

What is Fermat's factorization algorithm?

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.

Who is affected?

Multiple printers of the Fujifilm Apeos, DocuCentre and DocuPrint series generate self-signed TLS certificates with vulnerable RSA keys. The Fuji Advisory contains a list of all affected printers. (The printers use the brand name Fuji Xerox, but the company has since been renamed to Fujifilm.)

The Fujifilm printers use the Basic Crypto Module of the Safezone library by Rambus. Other products using this module to generate RSA keys may also be affected. The Rambus vulnerability got CVE-2022-26320 assigned.

Some Canon printers have the ability to generate a Certificate Signing Request with a vulnerable RSA key. To my knowledge this affects printers of the imageRUNNER and imagePROGRAF series. I believe that the Canon vulnerability and the Rambus vulnerability are not based on the same implementation and are two independent instances of the same class of vulnerability. The Canon vulnerability got CVE-2022-26351 assigned.

Is this a weakness in RSA?

No, RSA libraries with a correct key generation function are not affected.

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 likelyhood of p and q being close is neglegible.

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.

How did you find those keys?

I used multiple sets of public keys that I either had access to, that were shared with us by other researchers or that were publicly available.

I found the vulnerable, self-signed Fujifilm keys in recent scans of TLS certificates by Rapid7 (Rapid7 has sine closed down access to its scan data, but I performed the tests before that). I found a small number of valid, publicly trusted web certificates in Certificate Transparency logs. By contacting their owners I learned about the Canon printers.

It should be noted that all vulnerable certificates were of relatively recent origin (2020 and later). I believe that this is the reason that no such vulnerabilities were described in previously.

Is SSH affected?

There are probably no vulnerable SSH implementations creating such keys, though I obviously cannot proove that.

I checked multiple large collections of both SSH host and user keys. I did not find any vulnerable keys.

Is PGP/GnuPG/OpenPGP affected?

I applied the algorithm to a dump of the SKS PGP key servers. I found four vulnerable keys. However all these keys had a user ID that did imply they were created for testing.

It is plausible that these keys were not generated by vulnerable implementations, but were manually crafted, possibly by people aware of this attack creating test data.

What do you recommend?

If you are running one of the affected devices you should make sure that you update the devices and regenerate the keys.

If you are in a position where external users will supply public RSA keys to you then you might want to implement checks for this vulnerability. A typical case for this are certificate authorities. I shared the exploit code with certificate authorities and are aware that some have implemented checks in their certificate issuance process to avoid accepting keys vulnerable to this attack.

You can find Let's Encrypt's implementation of the check in their Boulder software in this pull request.

This vulnerability was found by Hanno Böck. This work was supported by the CIDI project (Cybersecure IoT in Danish Industry), CISAT (Center for Information Security and Trust) at ITU Copenhagen.

The website design was "stolen" from the DROWN website and slightly adapted; it was created by Sarah Madden. The Fermat portrait by François de Poilly is in the public domain. Design and content of this website are under a CC0 license. | Imprint

First published: 2022-03-14, last changes: 2022-03-14