The cryptographic vulnerability known as Return of Coppersmith's Attack, or ROCA, is arguably the most serious...
and pervasive publicly known flaw in digital cryptography to date.
Revealed in October 2017, the ROCA vulnerability puts a significant number of public/private key pairs at risk, leaving companies and governments struggling to grasp the implications.
For example, what to do with 60 million national ID smart cards impacted in Spain, and an unknown number of susceptible network authentication tokens and encrypted hard drives? Estonia, which had issued approximately 760,000 flawed national identity cards, chose to suspend the cards and required citizens to renew the flawed ID cards.
How does it work?
The ROCA vulnerability enables an attacker who has access to an RSA public key to quickly determine, through a mathematical fingerprint, whether or not the corresponding private key can easily be discovered through a process called factorization. ROCA uses methods developed by Don Coppersmith, a cryptographer and mathematician who helped design the DES block cipher. The attack potentially exposes the data the keys were protecting; for example, an electronic identity, physical or logical access, software certificate, electronic document authentication, or disk and email encryption.
The ROCA vulnerability is not in the RSA algorithm itself, but in the way that prime numbers are produced by one particular key generation program in a security library used by one maker of widely deployed crypto chips. The difficulty of factoring the product of two very large and very random prime numbers is what makes public key encryption possible and hard to break.
The library in question used a shortcut to generate primes that had the unfortunate side effect of limiting entropy -- that is, how many different primes could be generated. By using a variety of mathematical techniques, researchers observing patterns within a large number of public keys were able to work backwards to the private key.
The chips in question are made by Infineon Technologies, whose key generation hardware is in everything from authentication tokens and smart cards to the Trusted Platform Modules (TPMs) in laptops and servers. The library in question is RSALib. The researchers disclosed the vulnerability to Infineon in February, along with the fingerprinting and factorization tools they had developed. On October 16, CVE-2017-15361 was published, and it included a growing collection of advisories, solutions and tools -- 16 at the last count.
What to do about it
Unfortunately, there's no one-size-fits-all mitigation strategy for this vulnerability, the impact of which varies widely. In terms of risk management, the current cost of factoring in a weak key is likely to limit attacks to high-value targets pursued by well-funded adversaries.
However, that calculus is subject to change based on future computing costs and advances in the relevant mathematics and coding techniques. After all, the Infineon products in question received Federal Information Processing Standard 140-2 and the Common Criteria Evaluation Assurance Level 5+ certification, and they were thought to be resistant to attack based on parameters researchers undermined with an inventive combination of theorems and techniques.
The technical side of mitigation depends on multiple factors, including the specific version of the device hardware and key generation library, how RSALib is implemented and stored, the length of the keys being generated, and the availability of an alternative algorithm. Consider a smart card with a vulnerable version of RSALib stored in read-only memory, with key length limited to 2,048 bits and with no alternative key generation methods available. Replacing it with a card that uses a different algorithm or longer key length may be the only mitigation option, as RSALib keys greater than 2,048 bits are stronger.
Less dramatic mitigation is possible for laptops if their TPM firmware is updateable, but, otherwise, operating system changes to compensate for key generation weakness are needed -- Microsoft has been working hard on this. Some tokens that are used to generate and store keys, like YubiKey, can be fed fresh keys from a nonvulnerable source.
The preferred response to ROCA would be for organizations to audit their use of public key encryption to identify vulnerable sources and devices, from tokens to TLS certificates. The mitigation strategies available from vendors can then be reviewed and applied according to risk-based priorities.
The amount of effort and urgency around mitigation will clearly vary between high -- like a defense contractor relying on TPM-based laptop disk encryption to control access to sensitive data in the field, and low -- like a chain of florists that uses Infineon-chipped smart cards for employee access to its stores.
There is some good news: Public key systems where RSA keys are generated outside the security chips should not be affected, like EMV banking cards and chip-enabled passports. But the bottom line is that ROCA reveals serious deficiencies in today's digital encryption and security.
That vulnerable products were certified highlights the problems with the certification process. Deploying chips with only one method of generating keys creates a single point of failure and obsolescence if the implementation is read only. And the underlying challenge that led to the vulnerability -- the need to quickly generate strong primes using relatively weak computing devices, like most internet of things devices -- is still with us.
Finally, no account of the ROCA vulnerability would be complete without referencing the ROCA vulnerability test suite created by the researchers at Masaryk University. This can help individuals and organizations determine if specific keys are vulnerable.