Enigma Bridge Ltd, Cambridge, UK; and Ca' Foscari University of Venice, Italy has discovred a vulnerability in generation of RSA keys used by a
software library adopted in cryptographic smartcards, security tokens and other secure hardware chips manufactured by Infineon Technologies AG
allows for a practical factorization attack, in which the attacker computes the private part of an RSA key. The attack is feasible for commonly
used key lengths, including 1024 and 2048 bits, and affects chips manufactured as early as 2012, that are now commonplace.
Major vendors including Microsoft, Google, HP, Lenovo, Fujitsu already released the software updates and guidelines for a mitigation.
Full details including the factorization method will be released in 2 weeks at the ACM CCS conference as 'The Return of Coppersmith's Attack:
Practical Factorization of Widely Used RSA Moduli' (ROCA) research paper.
So what is all about?
A security vulnerability was found in the implementation of RSA keypair generation in a cryptographic library used in a wide range of cryptographic chips produced by Infineon Technologies AG. The product is also integrated in authentication, signature and encryption tokens of other vendors and chips used for Trusted Boot of operating systems. The vulnerability is present in NIST FIPS 140-2 and CC EAL 5+ certified devices since at least the year 2012.
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 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.
The specific structure of the primes in question allows for a fast detection of vulnerable keys, even in very large datasets. This property is useful for mitigation (users can assess own keys for vulnerability), but also for potential attackers (keys vulnerable to factorization can be pre-selected, without undergoing time-consuming factorization attempts). 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 worst-case price of the factorization on an Amazon AWS c4 computation instance is $76 for the 1024-bit key and about $40,000 for the 2048-bit key.
The difficulty of the factorization attack is not the same for all key lengths and is NOT strictly increasing (some longer keys may take less time to factorize than other shorter ones). The following key length ranges are now considered practically factorizable (time complexity between hours to 1000 CPU years at maximum): 512 to 704 bits, 992 to 1216 bits and 1984 to 2144 bits. Note that 4096-bit RSA key is not practically factorizable now, but may become so, if the attack is improved.
The time complexity and cost for the selected key lengths (Intel E5-2650 v3@3GHz Q2/2014):
512 bit RSA keys - 2 CPU hours (the cost of $0.06);
1024 bit RSA keys – 97 CPU days (the cost of $40-$80);
2048 bit RSA keys – 140.8 CPU years, (the cost of $20,000 - $40,000).
The vulnerability was found by a close inspection of a large number of RSA keys generated and exported from the manufacturer smartcards by researchers at CRoCS laboratory, Masaryk University, Enigma Bridge and Ca' Foscari University. The full results will be presented at an academic ACM Conference on Computer and Communications Security (ACM CCS '17) starting from October 30th.
The vulnerability was disclosed to Infineon Technologies AG, following the responsible disclosure principle, in the first week of February with agreement of an 8 month period before a public disclosure.
The team cooperated with the manufacturer and other affected parties to help evaluate and mitigate this vulnerability during this period. Major vendors including Microsoft, Google, HP, Lenovo, Fujitsu already released the software updates and guidelines for a mitigation.
They are also releasing tools for assessmnet of the individual keys.
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. The details will be presented in two weeks at the ACM CCS conference.
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.
More details and links to assesment tools can be found on CRoCs wiki here...