When the mathematics is not enough.

There is an irony in the history of public key cryptography: RSA, the discrete logarithm and well chosen elliptic curves have withstood half a century of mathematical attacks without giving way, and yet keys have been broken again and again. They were broken by a crippled random number generator, by a number that was supposed to change and never did, by a library that manufactured primes with too much structure. This article gathers the most instructive cases. None of them required solving a hard problem; all of them required someone to get something wrong that seemed secondary.

Debian, 2008: the entropy that vanished

In September 2006, a maintainer of the OpenSSL package in Debian wanted to silence warnings from a memory analysis tool, which flagged the use of uninitialized data in the random number generator. He commented out two lines. One of them was the line that fed real entropy into the generator. From then on, the only source of variation was the process ID, a number that on Linux did not exceed 32,768.

For about twenty months, every SSH key, every certificate and every key of any kind generated with OpenSSL on Debian, Ubuntu and their derivatives came from a universe of roughly 32,000 possibilities per key type and size. In May 2008 the Argentine developer Luciano Bello discovered the flaw, and within hours lists of every possible key were circulating. There was an additional, less well known effect: DSA keys generated on healthy machines but used to sign on affected ones were also compromised, because the nonces of those signatures were predictable.

Shared primes, 2012: the greatest common divisor

In 2012, Nadia Heninger, Zakir Durumeric, Eric Wustrow and Alex Halderman scanned every address on the internet and collected millions of TLS and SSH public keys. They then computed the greatest common divisor of every pair of RSA moduli, using a product tree algorithm that makes this efficient at that scale. If two moduli share a prime, the greatest common divisor reveals it, and both keys are factored instantly.

They were able to obtain the private key for 0.50% of TLS servers and 0.03% of SSH servers using RSA, and for 1.03% of SSH servers using DSA, in that case because of repeated nonces. Nearly all were embedded devices: routers, firewalls, remote management servers. They generated their keys on first boot, before the system had accumulated any entropy, and two units of the same model would end up choosing the same first prime and a different second one. A European academic team published equivalent results that same year.

A game console, 2010: the nonce that never changed

The article on how a signature is produced showed that in ECDSA, repeating the nonce k hands over the private key from just two signatures. In December 2010, at the Chaos Communication Congress, the group fail0verflow showed that an enormously popular video game console signed its updates with ECDSA using the same k every time. Two public signatures and a one line equation were enough to recover the manufacturer’s private key and sign arbitrary software as if it were official. The key, burned into millions of devices, could not be replaced.

In 2013 history repeated itself on a different stage: a flaw in the random number generator of a mobile platform caused cryptocurrency wallet apps to repeat nonces, and someone drained the accounts whose keys could be solved for from the public blockchain. Since then, deterministic nonce derivation has no longer been a mere suggestion.

ROCA, 2017: primes with too much shape

This is the most relevant case for legally binding signatures, because it hit identity cards. A library from a major manufacturer of secure chips, used in smart cards, TPM modules and security keys, generated RSA primes with a particular structure to speed up the process:

Matúš Nemec, Marek Sýs, Petr Švenda, Dušan Klinec and Vashek Matyáš, of Masaryk University, showed that this structure makes it possible to apply a variant of Coppersmith’s method, which finds small roots of modular polynomials, and factor the moduli. The estimated cost for a 2048 bit key was about 140 CPU years in the worst case, tens of thousands of dollars in the cloud; for 1024 bits, less than a hundred CPU days. Expensive, but well within reach of anyone with a motive, and parallelizable. Moreover, vulnerable keys could be recognized with an instant test on the public key.

Among those affected was the national ID card of Estonia, a country with one of the most advanced digital identity and signature systems in the world, with some 750,000 cards compromised. In November 2017 the authorities suspended the affected certificates and organized a mass key update, mostly carried out remotely. For signatures already made, the question became when they had been made, and the answer depended on the existence of timestamps and preserved evidence. This is exactly the scenario long term signatures exist for.

Other weak links we already know

Earlier articles in this series presented three more cases of the same nature. The rogue certificate authority certificate forged in 2008 with an MD5 collision, and the code signature forged by the Flame malware in 2012, exploited the continued use of a hash function years after it was known to be broken. The 2006 RSA signature forgery exploited verifiers that parsed the padding instead of reconstructing it. And the DigiNotar compromise in 2011 showed that a chain of trust is only as strong as the operational security of its weakest link.

Building to fail well

A handful of principles follow from these cases, and today they are part of the design of any serious signature system.

1. Keys generated in evaluated hardware, with verified entropy. And with the ability to replace them all if a defect turns up in that hardware.
2. Algorithms that do not punish small mistakes. Deterministic signatures, complete formulas, constant time implementations.
3. Strict verifiers. Reconstruct the expected structure and compare it byte by byte; validate every point, every range and every extension.
4. Cryptographic agility. Switching algorithm, curve or key size should be a configuration decision, not a project that takes years.
5. Evidence that outlives the key. Timestamps and preserved validation information, so that a legitimate signature remains provable even if its key falls later.

← All notes