Wednesday, September 18, 2013

Smartcards have Fatal Crypto Flaw (English)

...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 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 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...

There is more below.
Ниже есть продолжение.

...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...

...An RNG [Random Number Generator] 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...

...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...

...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 minuscule 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 2502 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 2266 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.

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.

...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?"...