FYI -- Once again, *security by obscurity* doesn't work for 58% of the Estonian population -- in this case the inaptly-named "Trusted Platform Modules" can't generate hard-to-factor RSA numbers. So much for Estonian voting and democracy. https://arstechnica.com/information-technology/2017/10/crypto-failure-crippl... COMPLETELY BROKEN -- Millions of high-security crypto keys crippled by newly discovered flaw Factorization weakness lets attackers impersonate key holders and decrypt their data. Dan Goodin - Oct 16, 2017 11:00 am UTC A crippling flaw in a widely used code library has fatally undermined the security of millions of encryption keys used in some of the highest-stakes settings, including national identity cards, software- and application-signing, and trusted platform modules protecting government and corporate computers. The weakness allows attackers to calculate the private portion of any vulnerable key using nothing more than the corresponding public portion. Hackers can then use the private key to impersonate key owners, decrypt sensitive data, sneak malicious code into digitally signed software, and bypass protections that prevent accessing or tampering with stolen PCs. The five-year-old flaw is also troubling because it's located in code that complies with two internationally recognized security certification standards that are binding on many governments, contractors, and companies around the world. The code library was developed by German chipmaker Infineon and has been generating weak keys since 2012 at the latest. The flaw is the one Estonia's government obliquely referred to last month when it warned that 750,000 digital IDs issued since 2014 were vulnerable to attack. Estonian officials said they were closing the ID card public key database to prevent abuse. On Monday, officials posted this update. Last week, Microsoft, Google, and Infineon all warned how the weakness can impair the protections built into TPM products that ironically enough are designed to give an additional measure of security to high-targeted individuals and organizations. Completely broken "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," Graham Steel, CEO of encryption consultancy Cryptosense, told Ars. "In this work, that property is completely broken." He continued: It means that if you have a document digitally signed with someone's private key, you can't prove it was really them who signed it. Or if you sent sensitive data encrypted under someone's public key, you can't be sure that only they can read it. You could now go to court and deny that it was you that signed something--there would be no way to prove it, because theoretically, anyone could have worked out your private key. Both Steel and Petr Svenda, one of the researchers who discovered the faulty library, also warned the flaw has, or at least had, the potential to create problems for elections in countries where vulnerable cards are used. While actual voter fraud would be difficult to carry out, particularly on a scale needed to sway elections, "just the possibility (although impractical) is troubling as it is support for various fake news or conspiracy theories," Svenda, who is a professor at Masaryk University in the Czech Republic, told Ars. Invoking the prolific leakers of classified National Security Agency material, Steel added: "Imagine a Shadowbrokers-like organization posts just a couple of private keys on the Internet and claims to have used the technique to break many more." The flaw is the subject of a research paper titled The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli, which will be presented on November 2 at the ACM Conference on Computer and Communications Security. The vulnerability was discovered by Slovak and Czech researchers from Masaryk University in the Czech Republic, Enigma Bridge in Cambridge, UK, and Ca' Foscari University in Italy. To give people time to change keys, the paper describing the factorization method isn't being published until it's presented at the conference. https://en.wikipedia.org/wiki/Coppersmith%27s_Attack The flaw resides in the Infineon-developed RSA Library version v1.02.013, specifically within an algorithm it implements for RSA primes generation. The library allows people to generate keys with smartcards rather than with general-purpose computers, which are easier to infect with malware and hence aren't suitable for high-security uses. The library runs on hardware Infineon sells to a wide range of manufacturers using Infineon smartcard chips and TPMs. The manufacturers, in turn, sell the wares to other device makers or end users. The flaw affects only RSA encryption keys, and then only when they were generated on a smartcard or other embedded device that uses the Infineon library. To boost performance, the Infineon library constructs the keys' underlying prime numbers in a way that makes them prone to a process known as factorization, which exposes the secret numbers underpinning their security. When generated properly, an RSA key with 2048 bits should require several quadrillion years--or hundreds of thousands of times the age of the universe--to be factorized with a general-purpose computer. Factorizing a 2048-bit RSA key generated with the faulty Infineon library, by contrast, takes a maximum of 100 years, and on average only half that. Keys with 1024 bits take a maximum of only three months. The factorization can be dramatically accelerated by spreading the load onto multiple computers. While costs and times vary for each vulnerable key, the worst case for a 2048-bit one would require no more than 17 days and $40,300 using a 1,000-instance machine on Amazon Web Service and $76 and 45 minutes to factorize an affected 1024-bit key. On average, it would require half the cost and time to factorize the affected keys. All that's required is passing the public key through an extension of what's known as Coppersmith's Attack. While all keys generated with the library are much weaker than they should be, it's not currently practical to factorize all of them. For example, 3072-bit and 4096-bit keys aren't practically factorable. But oddly enough, the theoretically stronger, longer 4096-bit key is much weaker than the 3072-bit key and may fall within the reach of a practical (although costly) factorization if the researchers' method improves. To spare time and cost, attackers can first test a public key to see if it's vulnerable to the attack. The test is inexpensive, requires less than 1 millisecond, and its creators believe it produces practically zero false positives and zero false negatives. The fingerprinting allows attackers to expend effort only on keys that are practically factorizable. The researchers have already used the method successfully to identify weak keys, and they have provided a tool here to test if a given key was generated using the faulty library. A blog post with more details is here. https://keychest.net/roca https://roca.crocs.fi.muni.cz/ In search of vulnerable keys The researchers examined keys used in electronic identity cards issued by four countries and quickly found two--Estonia and Slovakia--were issuing documents with fingerprinted keys, both of which were 2048 bits in length, making them practically factorizable. Estonia has disclosed the flaw in what it said were 750,000 of the cards issued since 2014. Ars checked the key used in an e-residency card Ars Senior Business Editor Cyrus Farivar obtained in 2015, and it came back as factorizable. While it has closed its public key database, Estonian government officials have also announced plans to rotate all keys to a format that's not vulnerable, starting in November. The status of Slovakia's system isn't immediately clear. With two of the four countries checked testing positive for fingerprinted keys, a more exhaustive search is likely to identify many more nations issuing cards with factorizable keys. Next, the researchers examined a sampling of 41 different laptop models that used trusted platform modules. They found vulnerable TPMs from Infineon in 10 of them. The vulnerability is especially acute for TPM version 1.2, because the keys it uses to control Microsoft's BitLocker hard-disk encryption are factorizable. That means anyone who steals or finds an affected computer could bypass the encryption protecting the hard drive and boot sequence. TPM version 2.0 doesn't use factorizable keys for BitLocker, although RSA keys generated for other purposes remain affected. Infineon has issued a firmware update that patches the library vulnerability, and downstream affected TPM manufacturers are in the process of releasing one as well. The researchers also scanned the Internet for fingerprinted keys and quickly found hits in a variety of surprising places. They found 447 fingerprinted keys--237 of them factorizable--used to sign GitHub submissions, some for very popular software packages. GitHub has since been notified of the fingerprinted keys and is in the process of getting users to change them. The researchers also found 2,892 PGP keys used for encrypted e-mail, 956 of which were factorizable. The researchers speculated that the majority of the PGP keys were generated using the Yubikey 4, which allows owners to use the faulty library to create on-chip RSA keys. Other functions of the USB device, including U2F authentication, remain unaffected. Yubico has more details here. https://www.yubico.com/keycheck/ The researchers went on to find 15 factorizable keys used for TLS. Strangely, almost all of them contain the string "SCADA" in the common name field. That raised the possibility the certificates are being used by an organization involved in Supervisory Control And Data Acquisition, which uses computers to control dams, electric substations, and other industrial equipment. All 15 fingerprinted keys have a characteristic involving their prime numbers that is outside the range of what's produced by the faulty Infineon library, raising the possibility there was a modification of it that hasn't yet been documented. This is the second time in four years that a major crypto flaw has been found hitting a crypto scheme that has passed rigorous certification tests. In 2013, a different set of researchers unearthed flaws in Taiwan's secure digital ID system that would allow attackers to impersonate some citizens. Both the flawed Infineon library and the Taiwanese digital ID system passed the FIPS 140-2 Level 2 and the Common Criteria standards. Both certifications are managed by the National Institute of Standards and Technology. Both certifications are often mandatory for certain uses inside government agencies, contractors, and others. The researchers who uncovered the Infineon library flaw questioned whether the secrecy required by some of the certification process played a role. They wrote: Our work highlights the dangers of keeping the design secret and the implementation closed-source, even if both are thoroughly analyzed and certified by experts. The lack of public information causes a delay in the discovery of flaws (and hinders the process of checking for them), thereby increasing the number of already deployed and affected devices at the time of detection. All told, the researchers estimate that Infineon's faulty library may have generated tens of millions of RSA keys in the five or so years it has been commercially available. A good many of them are practically factorizable, but even those that are not are considerably more vulnerable to factorization than federal standards and common-sense security guidelines dictate. RSA keys generated with OpenSSL, PGP-compliant programs, or similar computer programs aren't affected. People who have relied on smartcards or embedded devices for cryptographic functions should test their RSA keys using the researchers' fingerprinting tool. In the event the keys test positive, people should revoke them as soon as possible and generate new ones. Keys using Elliptic Curve Cryptography and other non-RSA methods aren't affected. It's going to take a while for people to identify all vulnerable keys. They should start by replacing those that are known to be practically factorizable, but eventually all RSA keys generated by the flawed library should go. Cryptographers and engineers within NIST and other standards organizations should also use the failure to learn how to improve their high-security certifications processes. Promoted Comments vintagedave Wise, Aged Ars Veteran Quote: Estonia has disclosed the flaw in what it said were 750,000 of the cards issued since 2014. Ars checked the key used in an e-residency card Ars Senior Business Editor Cyrus Farivar obtained in 2015 and it came back as factorizable. I live in Estonia. A couple of interesting or concerning points here: * The population is 1.3 million. 750,000 affected cards sounds plausible for the majority or even entire adult population. No material that I've seen in articles (here) or online (eg Estonian government) have mentioned a breakdown of the affected cards by population, voting rights, or residency. Ars - a good opportunity for some investigative journalism? * Estonia is a nation at risk from Russian cyber attacks. It's happened before. Here's CEPA's analysis of the current situation as of 2016. * We had municipal elections yesterday, and online voting using ID cards is common. Municipal elections are important in this country: consider the ex-mayor of Tallinn Edgar Savisaar and the social turmoil and potential Russian-related corruption attributed to him. Dan Goodin Dan is the Security Editor at Ars Technica, which he joined in 2012 after working for The Register, the Associated Press, Bloomberg News, and other publications. Email dan.goodin@arstechnica.com // Twitter @dangoodin001