On October 17th, a group of Czech researchers announced they had found a way to factor the moduli of many RSA public keys generated by hardware produced by Infineon Technologies AG. The technical details were presented in a paper at the 2017 Computer and Communications Security conference, hosted by the Association for Computing Machinery on November 2nd.
The technique only works against the key pairs produced by Infineon’s library, because it exploits the unique method they use to generate RSA primes. Key pairs produced by other methods and libraries are unaffected. However, Infineon’s library is very popular, and used in many scenarios, especially for smart cards. RSA keys for public websites are generally much less likely to have been generated by such hardware, although some cases are known to exist, and certificate authorities are working to inform customers and get the vulnerable keys replaced.
The details of how the attack works are interesting. Remember that an RSA public key is a pair of integers (N,e) where N is large, and e is usually 65537. The RSA private key is (p,q), the two large, prime factors of N. Anyone who has the private key can perform any of the operations that can be performed by the owner of the key pair, but it usually is not possible to obtain the private key from the public key, because N is too large to be factored.
The two primes are typically chosen to be near the square root of N, and since N is large, there are lots and lots of suitable choices. Picking a random prime from a large number of candidates makes it impossible to guess which primes were likely to have been chosen. However, there is significant disagreement about how best to choose RSA primes, and choosing numbers at random and testing whether they are prime is very expensive computationally, especially on smart cards.
Instead, candidate primes are usually selected by some proprietary algorithm that selects candidates from some smaller subset that is more likely to be prime and have other useful security properties (in particular, for subtle mathematical reasons, it is generally a good idea to make sure p-1 and q-1 do not have small prime factors). The same researchers published a paper last year that showed that RSA key generation algorithms are significantly different enough that they can be identified just by looking at the mathematical properties of the public modulus N. And in particular, they found in their previous research that public keys produced by Infineon had fairly odd statistical properties that implied they were selected from a far smaller set of numbers than other methods.
Infineon’s primes all have the form:
p = k * M + (65537^a mod M)
where M is the product of the first several primes until its size is comparable to the desired size for p.
There are still too many possibilities to just try them all, but there are a few more interesting details that make the attack possible. First, since M is the product of small primes, it is what is known as a “smooth” number, and the multiplicative groups it generates have a variety of useful mathematical properties. Second, there is a known attack on RSA called Coppersmith’s attack which can find the rest of the private key when some information about it is known.
There are several other clever improvements and optimizations, but the end result is a highly efficient, highly parallelizable algorithm for recovering the private key directly from the public key for some of these public keys, without requiring access to the device itself.
How serious this is for a particular use case depends on how easy it is to get ahold of the public key, and whether the private key is valuable enough to be worth using substantial resources to factor (cost estimates for factoring a 2048-bit key are in the thousands of dollars).
Again, this attack only affects keys that are generated by Infineon’s prime selection algorithm. Such keys are rarely used as part of the web PKI, and those that are in use are rapidly being replaced. Outside of the web PKI, the impact is far more serious, with many kinds of digital ID documents being vulnerable, and a significant fraction of the Trusted Platform Modules used on laptops being affected.
