Fatal crypto flaw in some government-certified smartcards makes forgery a snap

With government certifications this broken, the NSA may not need backdoors.

by Dan Goodin - Sept 16 2013

• Government
• Hacking

http://arstechnica.com/security/2013/09/fatal-crypto-flaw-in-some-government-certified-smartcards-makes-forgery-a-snap/

As many of 10,000 of these smartcards may provide little or no cryptographic protection despite receiving two internationally recognized certifications.

Angelo Su

Raising troubling questions about the reliability of government-mandated cryptography certifications used around the world, scientists have unearthed flaws in Taiwan's secure digital ID system that allow attackers to impersonate some citizens who rely on it to pay taxes, register cars, and file immigration papers.
The crippling weaknesses uncovered in the Taiwanese Citizen Digital Certificate program cast doubt that certifications designed to ensure cryptographic protections used by governments and other sensitive organizations can't be circumvented by adversaries, the scientists reported in a research paper scheduled to be presented later this year at the Asiacrypt 2013 conference in Bangalore, India. The flaws may highlight shortcomings in similar cryptographic systems used by other governments around the world since the vulnerable smartcards used in the Taiwanese program passed the FIPS 140-2 Level 2 and the Common Criteria standards. The certifications, managed by the National Institute of Standards and Technology (NIST) and its counterparts all over the world, impose a rigid set of requirements on all cryptographic hardware and software used by a raft of government agencies and contractors.

“Trivially broken keys”

The team of scientists uncovered what their paper called a "fatal flaw" in the hardware random number generator (RNG) used to ensure the numbers that form the raw materials of crypto keys aren't based on discernible patterns. Randomness is a crucial ingredient in ensuring adversaries can't break the cryptographic keys underpinning the smartcards issued to Taiwanese citizens.
Out of slightly more than 2 million 1024-bit RSA keys the researchers examined, an astonishing 184 keys were generated so poorly they could be broken in a matter of hours using known mathematical methods and standard computers to find the large prime numbers at their core. Had the keys been created correctly, breaking them so quickly would have required a large supercomputer or botnet. That even such a small percentage of keys were found to be so easily broken underscores the fragility of cryptographic protections millions of people increasingly rely on to shield their most intimate secrets and business-sensitive secrets.
"The findings are certainly significant for the citizens who have been issued flawed cards, since any attacker could impersonate them online, the research team wrote in an e-mail to Ars. "More broadly, our research should give pause to any of the many countries that are rolling out this kind of national public key infrastructure. These smart cards were certified to respected international standards of security, and errors led to them generating trivially broken cryptographic keys. If a technologically advanced government trying to follow best practices still has problems, who can get this right?"

Stacking the deck

The research is being published two weeks after documents leaked by former National Security Agency (NSA) contractor Edward Snowden outlined the covert hand intelligence agents have played in deliberately weakening international encryption standards. As a result, the NSA and its counterparts in the UK can most likely bypass many of the encryption technologies used on the Internet. Cryptographers involved in, and independent of, the research agreed that the weaknesses exposed in the paper were almost certainly the result of human error, rather than deliberate sabotage. They based that assessment on the observation that the predictable patterns caused by the malfunctioning PRNG were so easy to spot.
"Some of the primes discovered in this work are so obviously non-random that, if they were the result of deliberate weaknesses, then I'd be asking for my money back from my three-letter agency," Kenneth G. Paterson, a Royal Holloway scientist who has seen the paper, told Ars. "Because they would clearly not have been doing a very good job in hiding their footprints."
Still, the fact that Taiwan's extremely weak RNGs passed stringent validation processes is troubling. An RNG that picks prime numbers in predictable ways is in some ways the cryptographic equivalent of a blackjack croupier who arranges a deck of cards so they're dealt in a way that puts the gambler at a disadvantage. Properly implemented RNGs, to extend the metaphor, are akin to a relief dealer who thoroughly shuffles the deck, an act that in theory results in the strong likelihood the cards never have and never again will be arranged in that exact same order.

Enlarge / A slide from a recent presentation detailing the 119 primes shared among 103 of the weak cards used in Taiwan's Citizen Digital Certificate program.

There's no way to rule out the possibility that the NSA, or intelligence agencies from other nation states, didn't already know about the vulnerability in Taiwan's crypto program or about programs in other countries that may suffer from similar weaknesses. The inability of the certifications to spot the fatally flawed RNGs suggests the standards offer far less protection than many may think against subtle flaws that either were intentionally engineered by intelligence agencies or were exploited after being discovered by them.
The researchers began their project by examining almost 2.2 million of the Taiwanese digital certificates secured with 1024-bit keys (newer cards have 2048-bit RSA keys). By scanning for pairs of distinct numbers that shared a common mathematical divisor, they quickly identified 103 keys that shared prime numbers.
A little more than 100 keys that shared primes out of a pool of 2 million makes for an infinitesimally small percentage, but in the eye of a trained cryptographer, it flags a fatal error. When generating a 1024-bit RSA key, there are an almost incomprehensible 2⁵⁰² prime numbers that can be picked to form its mathematical DNA, Mark Burnett, an IT security analyst and author, estimates. That's many orders of magnitude more than the 2²⁶⁶ atoms in the known universe. If all these primes are properly mixed up and evenly distributed in a large digital pot—as is supposed to happen when being processed by a correctly functioning RNG—no two primes should ever be picked twice. By definition a prime is a number greater than one that has no positive divisors other than 1 and itself.

Enlarge / A summary of the data flow leading to successful factorizations of the Digital Citizen Card used in Taiwan.

Bernstein, et al.

And yet, 103 of the keys flagged by the researchers factored into 119 primes. The anomaly was the first unambiguous sign that something horribly wrong had gone on during the key-generation process for the Taiwanese smartcards. But it wasn't the only indication of severe problems. The researchers sifted through the shared primes and noticed visible patterns of non-randomness that allowed them to factor an additional 81 keys, even though they didn't share primes. Once the primes are discovered, the underlying key is completely compromised. Anyone with knowledge of the primes can impersonate the legitimate card holder by forging the person's digital signature, reading their encrypted messages, and accessing any other privileges and capabilities afforded by the card.

The researchers said they informed officials in Taiwan's government of the problems and were told that as many as 10,000 cards might suffer similar weaknesses. The estimate, the researchers told Ars, were based on internal records from the Ministry of Interior Certificate Authority and Chunghwa Telecom, Taiwan's official digital certificate authority and the smartcard manufacturer, respectively.
"The government claims that they will track down and replace all the flawed cards but hasn't done so at the time of writing," the researchers told Ars. "So everybody with an RSA-1024 card could have a weak one." The newer RSA 2048-bit cards they examined didn't suffer from the same weaknesses, although they didn't rule out the possibility those cards contain more subtle flaws that make them just as vulnerable.

Not the first time

Enlarge / One of the affected smartcards, from Chunghwa Telecom Co., Ltd.

NIST

The discovery has roots in research published last year that made another astonishing discovery: four of every 1,000 1024-bit keys found on the Internet provided no cryptographic security at all. The reason: as with Taiwan's Citizen Digital Certificate keys, the almost 27,000 cryptographically worthless keys they found shared primes with at least one other key. One of the research teams that discovered the keys later released a detailed analysis of what went wrong. Since almost all the keys were from "self-signed" certificates used to protect routers and other devices, the researchers speculated the hardware lacked the robust RNGs found in more advanced platforms and applications. Two of the three mathematical techniques used to factor the keys in the Taiwanese smartcards are well-known and unsophisticated. They are trial division and use of things like the Binary Greatest Common Divisory Algorithm for finding greatest common divisors. A third technique know as Coppersmith's attack is significantly more advanced, and the researchers said it represents the first recorded time it has been used to break a cryptographic system.
All three techniques can be carried out on unsophisticated computers to factor weak keys in a matter of hours. Using the same methods and hardware to factor 1024-bit keys that are generated properly would "not have found those primes within the expected lifetime of the universe," the researchers said. (Other, more sophisticated algorithms, when carried out on supercomputers, represent a much bigger threat to 1024-bit keys.)
"Our results make it pretty clear that the more computational effort we expend, the more keys we were able to factor," the researchers wrote. "We did enough computation to illustrate the danger, but a motivated attacker could easily go further."
As crucial as random number generation (RNG) is to cryptographic security, the task remains maddeningly difficult to do. It requires a computer to carry out what scientists call non-deterministic behavior, which typically causes malfunctions in most other contexts. Frequently, extremely subtle bugs can cause RNGs, assumed to be robust, to produce highly predictable output. One example was an almost catastrophic vulnerability in the Debian distribution of Linux. The overlooked bug caused vulnerable machines to generate dangerously weak cryptographic keys for more than 20 months before it was diagnosed and fixed in mid 2008.

The FIPS 140-2 Validation Certificate for one of the affected smartcards.

NIST

To prevent these common mistakes, standards bodies sponsored by governments around the world have created a set of rigid criteria cryptographic systems must pass to receive certifications that can be trusted. The certifications are often a condition of a hardware or software platform being adopted or purchased by the government agency or contractor.
But despite passing both the FIPS 140-2 Level 2 and Common Criteria standards, the RNG process used to generate the weak cards clearly didn't meet their mandated requirements. FIPS 140, for instance, specifies that output of a hardware RNG on the processor of the smartcard must (a) be fed through tests to check whether it's random and unbiased, and only then can the output (b) be used as a seed for a so-called deterministic random bit generator, which in many settings is referred to as a pseudo RNG. The hardware RNG was provided by the AE45C1, a CPU manufactured by Renesas that sits on top of the smartcard. The deterministic random bit generator was driven by the smartcard firmware provided by Chunghwa Telecom.
"It's pretty clear that neither step happened in this case," the researchers told Ars. "Even without performing step (a), step (b) should have made the keys appear individually random, even if they were not. Instead, the factored keys contained long strings of 0 bits or periodic bit patterns that suggest that step (b) was skipped, and what we see is the direct unwhitened output from the malfunctioning hardware."
The seven researchers are Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, and Nicko van Someren. More information about them and their findings is available here. The failure has implications not only for the citizens of Taiwan but for internationally certified cryptographic technologies everywhere.
"It is a common practice to advertise chips as certified if they get certification on some part of it, but the certification actually means very little," the researchers told Ars. "The whole system is broken. "Two certifications didn't stop the bad hardware RNG on the card; how can we trust them to find more sophisticated flaws such as intentional back doors?"