Posted by Jesse Victors on October 17, 2017
There’s been some very big news in the cryptographic world this week. So far, several technology news sites have highlighted the impact of a new vulnerability on Estonian and Slovakian smartcards, but the reach of this vulnerability is far wider than that. Five security researchers have just announced their discovery of a cryptographic flaw in a widely used cryptographic library. The vulnerability, formally assigned CVE-2017-15361 and called the Return of Coppersmith’s Attack, or ROCA for short, is a practical mathematical attack that allows an adversary to reveal secret keys on certified devices using this library. The key can be revealed offline, and no physical access to the affected device is required. Once the attack is complete, the attacker can then use the secret key to overcome any authentication or encryption systems that are in place on the affected device.
Unfortunately, many certified devices are vulnerable. This flaw is present in the library used by NIST FIPS 140-2 and CC EAL5+, two internationally adopted cryptographic standards. This library has made its way into smartcards and Trusted Platform Modules (TPMs) used by BitLocker and Windows 10 Secure Boot. The flaw affects the identity smartcards of approximately 750,000 Estonians, nearly 55% of the country’s population. In these contexts, the attacker can use ROCA to impersonate the owner of the smartcard, break BitLocker encryption, or bypass the protections of Secure Boot.
Based on the limited information released by the authors, we know that ROCA exploits a flaw in a software library that generates RSA keys. RSA is a public key cryptosystem widely used for digital signatures for authentication or encrypted messages for confidentiality. You will find RSA practically everywhere, even in the HTTPS on this web page. RSA uses two keys: public and private. The public key consists of two numbers, N and E. These two numbers can be shared with anyone. N is a large number, typically 2,048 bits in length, while E is a small number, often 3, 17, or 65,537. E is small for performance reasons; all RSA operations require modular exponentiation (aE mod N), which is orders of magnitude faster if E is a small Fermat prime such as 3, 17, or 65,537. The secret key consists of N and D, and D must be kept secret for the entire system to work.
There are some subtle differences between the choice of 3, 17, and 65,537 for the value of E. It’s intuitive to choose 3 owing to its higher performance, which is critical for very low-power devices such as smartcards, but crucially the choice can have a significant impact on the security of the entire RSA system. In 1996, Dan Coppersmith developed fatal attacks against E=3 if the software library used a simple message-padding scheme. In fact, in June 2000, Boneh and Durfee showed that if E > N0.292, then RSA is not secure. This implies that E=3 is unsafe in all standard key sizes, including the 2,048-bit keys used in identity smartcards, BitLocker, Secure Boot, HTTPS, and many other applications.
Over the years, several standards have attempted to shore up RSA against low-exponent attacks. However, E=65,537 is safer, so it became widely recommended, and the industry generally settled on it. The SSL certificate protecting Synopsys.com uses E=65,537, and you will find this to be true across many other websites. Several internet standards, such as RFC 4871, state that 65,537 should be used.
The ROCA authors, Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, and Vashek Matyas, have not yet published the full details of their attack, but it seems likely that ROCA relates to the issues with E=3. In January, they discovered that Infineon Technologies AG had written a cryptographic library that contained a critical flaw in the generation of RSA keys. This library was then compiled and embedded into millions of smartcards, Trusted Platform Modules, and other certified devices used in organizations and governments around the world since at least 2012. The full details will be presented at ACM CCS 2017 and are included in a research paper titled “The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli.” This paper and presentation will be available in about 2 weeks.
The answer is most likely yes. Even if you aren’t a citizen of Estonia or Slovakia, your personal computer and your workstation may be affected. Microsoft has published an advisory (ADV170012) stating that Windows 8.1, Windows 10, and Windows Server 2012 and 2016 are all affected. BitLocker keys may also need to be regenerated.
Estonia is well-aware of the vulnerability affecting 55% of its citizens; the government published an advisory last month, which was followed by an update earlier this week. They stress that the flaw remains theoretical and is difficult to execute, so they have decided not to recall the affected smartcards. Some of their services use the ID smartcard to supplement a username and password, which an attacker would not have.
You can test RSA public keys against the ROCA flaw with these tools:
The authors have made it clear that this flaw is embedded into the hardware and firmware of many devices widely used across the globe. This makes it difficult to completely patch, but there are some mitigating controls.
If you are using Windows, Microsoft has issued several updates that should address the issue. Google, HP, Lenovo, and Fujitsu have released updates for their software products as well. Estonian citizens can suspend the digital signature services of their smartcards if they choose. A new chip is in development in the meantime.
As we’ve discussed before on this blog, crypto is fragile. RSA turned 40 years old this year, and we still seem to struggle with using and implementing it correctly. The RSA algorithm described in 1977 is fast but unsafe and must be implemented carefully to avoid several padding oracle attacks and information leaks. Numerous schemes have been introduced to address the flaws—which I consider to be a flaw with RSA’s design and the complexity of standards. However, RSA was here first, and it’s one of our best public key encryption schemes, so it isn’t going away anytime soon.
In an article titled “Secure or Compliant, Pick One,” Steve Marquess argued in 2009 that unvalidated software libraries can be more secure than certified software libraries. Unvalidated libraries are exposed to the real world and can be patched, updated, and redistributed quickly, whereas certified libraries must go through a long and expensive process to be marked “secure.” This creates a financial disincentive for reporting vulnerabilities in certified software, which means that certified secure software can become less secure than its open source brother.
Smartcards are between a rock and a hard place when it comes to RSA. They have limited resources, so they are always designed to use the cheapest operations that are still safe. I think the solution is elliptic curve cryptography (ECC). Perhaps Infineon Technologies AG should have used EdDSA/Ed25519, which is blazingly fast and much easier to implement than RSA. EdDSA has been standardized and has made its way into numerous high-security software projects. It might be time to consider it for smartcards.
For further reading on ROCA, see the following:
Get the latest Software Integrity news, thought leadership, and more.