Fermat Factorization in the Wild, background paper published at the Cryptology ePrint Archive.
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 use an underlying cryptographic module from the company Rambus.
This research was done during development of the badkeys project. badkeys is a web service and tool to check cryptographic keys for known vulnerabilities.
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.)
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.
Both the Fujifilm and the Canon 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. This vulnerability got CVE-2022-26320 assigned.
(A previous version of this webpage implied that the Canon and the Rambus issue were two separate, unrelated vulnerabilities. This was incorrect. I have informed Mitre that the previously assigned separate CVE for Canon should be rejected.)
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:
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 since 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. The zlint tool has added a check for vulnerable keys in version 3.4.0.
The badkeys tool contains code to check for this vulnerability and factor affected keys.
Ars Technica, 2022-03-14: Researcher uses 379-year-old algorithm to crack crypto keys found in the wild
Golem.de, 2022-03-15: Über 300 Jahre alter Algorithmus knackt RSA-Keys
Computerphile, 2022-05-10: Breaking RSA
heise online, 2022-06-01: Schwache RSA-Schlüssel mit 380 Jahre altem Faktorisierungsalgorithmus knacken
Rambus Security Vulnerability Disclosure: SafeZone Basic Crypto Module, non-FIPS certified version
Canon: Notice of potential vulnerability in RSA key generation
Fujifilm: Notification about the vulnerability for RSA key in our multi-function printers and single-function printers
This vulnerability was found by Hanno Böck. This work was funded in part by Industriens Fond through the CIDI project (Cybersecure IOT in Danish Industry) and in part by the Center for Information Security and Trust (CISAT) at the IT University of Copenhagen, Denmark.