Vulnerability in code library allows attackers to work out private RSA keys

Researchers have discovered a security vulnerability in the Infineon-developed RSA library, which could be exploited by attackers to discover the RSA private key corresponding to an RSA public key generated by this library.

This private key could be then misused to impersonate its legitimate owner, decrypt sensitive messages, forge signatures (e.g. for software releases) and more.

The vulnerable version of the library is v1.02.013, and it’s unfortunately been in use since 2012 in a wide range of cryptographic chips produced by Infineon Technologies AG.

The paper detailing the key-discovery factorization method will be published on November 2, to coincide with the researchers presentation at the ACM CCS conference, but they’ve already shared the details with many vendors whose offerings take advantage of Infineon’s chips, as well as published a summary of their findings.

About the vulnerability (CVE-2017-15361)

“The algorithmic vulnerability is characterized by a specific structure of the generated RSA primes, which makes factorization of commonly used key lengths including 1024 and 2048 bits practically possible. Only the knowledge of a public key is necessary and no physical access to the vulnerable device is required,” the researchers explained.

“The vulnerability does NOT depend on a weak or a faulty random number generator – all RSA keys generated by a vulnerable chip are impacted. The attack was practically verified for several randomly selected 1024-bit RSA keys and for several selected 2048-bit keys.”

And while it’s easy for users to check whether their private RSA keys can be derived from their public ones through this method, it’s also easy for attackers to identify vulnerable keys in much the same way, and concentrate on factorizing those ones.

“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. Where k CPUs are available, the wall time required for the attack will be reduced k-times – allowing for practical factorization in order of hours or days,” the researchers shared, and said that while 4096-bit RSA keys are not practically factorizable now, they might be in the future if the attack is improved.

The factorization method they devised is based on an old technique called the Coppersmith’s attack, and consequently this new “hack” has been dubbed by the researchers ROCA (Return of Coppersmith’s Attack).

The vulnerability’s impact

“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 researchers noted.

They told Ars Technica that they’ve:

• Tested 41 laptop models that used trusted platform modules, and found vulnerable TPMs from Infineon in 10 of them
• Scanned the Internet for fingerprinted keys and found 237 factorizable keys (out of 447) used to sign open source software packages published on GitHub
• Found 956 factorizable PGP keys (out of 2,892) used for email encryption – they posited that most of them were generated using the Yubikey 4, which users the vulnerable library to create on-chip RSA keys
• Found 15 factorizable keys used for TLS.

“The currently confirmed number of vulnerable keys found is about 760,000 but possibly up to two to three magnitudes more are vulnerable. The vulnerable chips are pervasive and not necessarily sold directly by Infineon Technologies AG, as the chips can be embedded inside devices of other manufacturers.”

Risk mitigation

Infineon has issued a firmware update for the vulnerability in its TPMs.

Manufacturers of computing devices with an Infineon TPM, such as HP, Lenovo, and Fujitsu have already released the software updates and guidelines for risk mitigation. Microsoft and Google did as well.

People whose RSA keys were generated via smartcards or embedded devices should test them and revoke them if they are vulnerable. The researchers are pretty sure the tools they provided for doing that are extremely accurate: if a key is flagged as vulnerable, it is vulnerable, and if it’s not, it is safe from this attack.

“If a vulnerable key is found, then you should contact your device vendor for further advice,” they advised.

In general, until software updates are implemented, new (safe) keys can be created with the card/device by using other cryptographic algorithms (e.g., ECC). Another option is to generate a secure RSA keypair outside the device (e.g., via the OpenSSL library) and import it to the device.