An RSA key developed by Infineon and used by governments, corporations, and TPM modules has recently been found to be broken. The weakness, which only affects keys that were generated using smartcards and other embedded devices using the Infineon Library, uses the public portion of the key to calculate private portion in relatively short order; the flaw is five years old, and is located in code that has been accepted by two international security certification standards.
“In public key cryptography, a fundamental property is that public keys really are public—you can give them to anyone without any impact in security,” says Graham Steel, CEO of encryption consultancy firm Cryptosense.
Inherent to the Infineon library, the algorithm that generates prime numbers on smartcards and embedded devices, all of the keys are weaker than they should be. By factorizing the 2048-bit keys that were generated using the affected Infineon Library, researchers were able to generate the private portion of the key in 17 days using Amazon Web Services; a 1024-bit key was factorized in 45 minutes. Notably, this method isn’t practical using typical consumer-grade computers.
To make this specific attack practical, the Coppersmith Attack was implemented; it reduces the time needed to crack the private key significantly. Coppersmith’s algorithm can be used to find the integer solution (roots) to polynomial equations. The idea behind Coppersmith’s method is to find a different polynomial that has the same solution, but has only small coefficients. If the coefficients are small, the roots are easy to find using various types of numerical methods (consider various open methods such as Newton, Secant, fix point, etc.). Coppersmith’s Algorithm uses the LLL reduction algorithm to construct a polynomial with small coefficients. The LLL algorithm uses an inequality so that standard factorization methods can calculate the zeros.
Among other things, RSA encrypts data sent over the internet. This encryption is most notably found when using https sites for credit card information and other Personally Identifiable Information (PII). RSA’s do not require both parties to know a secret key to work. A “public key” is matched with a “private key.” You first request the public key from the server and encrypt your data using this public key. Your data then gets decrypted using the server’s private key. Describing the mathematics used by RSA encryption is outside of the scope of this writing.
To make this attack method more successful, a malicious actor could use a fingerprinting method to test public keys to see if they’re vulnerable. The ROCA Vulnerability Test Suite allows users to verify the security of their encryption keys. The Infineon vulnerability has been documented in NIST FIPS 140-2 since 2012; as computing power increases, the entire library will become cryptographically broken.
Researchers at CRoCS laboratory, Masaryk University, Enigma Bridge and Ca’ Foscari University discovered the vulnerability. The full results will be presented at an academic ACM Conference on Computer and Communications Security (ACM CCS ’17) starting from October 30th.
Sources:
https://csrc.nist.gov/csrc/media/publications/fips/140/2/final/documents/fips1402.pdf
