379年前のアルゴリズムを使って RSA 暗号鍵を破った話

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.

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 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 Rambus SafeZone Basic Crypto Module before 10.4.0, as used in certain Fujifilm (formerly Fuji Xerox) devices before 2022-03-01, Canon imagePROGRAF and imageRUNNER devices through 2022-03-14, and potentially many other devices, generates RSA keys that can be broken with Fermat’s factorization method. This allows efficient calculation of private RSA keys from the public key of a TLS certificate.

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.

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.

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.

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.