Hundreds of Thousands of RSA Private Keys Can Be Factored
Researchers have found that RSA keys generated by cryptographic chips can be factored, exposing a vulnerability affecting the security of many systems and users.
There are a lot of moving parts and complex pieces that combine to make up the Internet’s security infrastructure, but a not-inconsiderable portion of it rests on the difficulty of math. Researchers this week published work, revealing that the RSA keys generated by the cryptographic chips in a wide range of hardware are factorable by current computers.
The issue is the result of a vulnerability in chips, manufactured by Infineon Technologies, that are found in laptops, smart cards, and a variety of other places. It’s not a weakness in the RSA algorithm itself, but in the implementation of it in some of Infineon’s chips involving the way that they generate RSA keypairs. In practical terms, it means that commonly used key lengths such as 1024 and 2048 bits are within reach of many classes of attackers.
“The worst cases for the factorization of 1024 and 2048-bit keys are less than 3 CPU-months and 100 CPU-years, respectively, on a single core of a common recent CPU, while the expected time is half of that of the worst case. The factorization can be easily parallelized on multiple CPUs,” researchers from the Centre for Research on Cryptography and Security in the Czech Republic said in their abstract.
“A remote attacker can compute an RSA private key from the value of a public key. The private key can be misused for impersonation of a legitimate owner, decryption of sensitive messages, forgery of signatures (such as for software releases) and other related attacks. The actual impact of the vulnerability depends on the usage scenario, availability of the public keys and the lengths of keys used. We found and analyzed vulnerable keys in various domains including electronic citizen documents, authentication tokens, trusted boot devices, software package signing, TLS/HTTPS keys and PGP. The currently confirmed number of vulnerable keys found is about 760,000 but possibly up to two to three magnitudes more are vulnerable.”
This is the kind of vulnerability that has worried cryptographers and security researchers for years. It’s a fundamental flaw buried inside a hardware system that has a broad effect on the security of many systems and users. The researchers discovered the bug in the course of looking at a large group of RSA keys generated by Infineon chips. They noticed a certain pattern with the keys and eventually discovered the weakness. Microsoft, Google, Lenovo, and other vendors whose products are affected by the weakness have been aware of the problem for a while and have issued updates to fix it already.
Where else could this kind of weakness be lurking? Cryptographers have been looking at the RSA algorithm every which way for decades now and it has proven to be remarkably resilient. If there was a fundamental weakness in the algorithm, it likely would have been exposed by now. However, there are an untold number of custom implementations of the algorithm, and that’s where the problems usually arise.
It’s a safe bet that there are other issues like this sitting dormant out there. The question is whether researchers will find them before attackers do.