Famous RNG failures, from Debian OpenSSL to shared RSA keys
The best-known randomness failures — the Debian OpenSSL key generation defect, Android wallet key collisions, and the large-scale surveys that found shared RSA factors across internet hosts — share a pattern. The algorithms were sound and the material fed into them was not.
Described from the public record. Each is worth reading as a study in how invisible this class of failure is until somebody goes looking.
Debian OpenSSL, 2006 to 2008
A change to Debian's OpenSSL package removed code that a memory-checking tool flagged as reading uninitialised memory. The flagged code was contributing to the entropy pool, and removing it collapsed the space of possible keys to something that could be enumerated.
Keys generated on affected systems for roughly two years were predictable. Nothing failed, nothing looked wrong, and the keys worked perfectly. The lesson usually drawn is about packaging discipline; the more useful one is that nothing in the system could detect that its entropy had collapsed.
Android wallet key collisions, 2013
A flaw in the platform's SecureRandom implementation meant some applications generated colliding values. Bitcoin wallets, which use ECDSA, were affected: a repeated nonce across two signatures exposes the private key directly, and funds were taken.
This is the clearest demonstration that the consequence is not proportional to the size of the defect. A partial randomness failure produced total key compromise, because of how ECDSA consumes nonces.
Shared factors across internet hosts, 2012
Independent research groups collected TLS and SSH keys at internet scale and found that a meaningful fraction shared prime factors — which meant those keys could be recovered by computing greatest common divisors across the corpus.
The cause was embedded devices generating keys at first boot, before enough entropy had accumulated. Two devices in the same state produced overlapping key material. Nobody had done anything wrong at the algorithm level, and the boot-time entropy problem remains live today.
The pattern
In every case the cryptography was correct, the implementation was competent, and the failure was upstream of both. In every case it was invisible from the output. And in every case it was found by an outside party, sometimes years later.
That is the argument for measuring the source rather than the product. These systems had no way to notice, and there was nothing in the output to notice with — which the statistical tests could not have changed.
Keep reading
- Where entropy breaks
CWE-330 in the wild, breaches caused by weak randomness
CWE-330, "Use of Insufficiently Random Values", is the class covering every failure where predictable values were used where unpredictable ones were required. It is the root of a family that reaches key generation, session tokens, initialisation vectors, nonces and password resets.
- Where entropy breaks
Entropy in HSMs and secure elements
An HSM or secure element generates keys internally, so its entropy source is the root of everything it protects. What the module's certification covers, and whether the entropy claim is evidenced within its boundary, decide how much the certificate actually tells you.
- Where entropy breaks
Entropy starvation at boot, in virtual machines and containers
Entropy starvation happens when a system needs randomness before its sources have produced enough — most commonly at first boot on embedded devices, in freshly cloned virtual machines, and in containers that inherit a host state. The usual workarounds trade the problem for a weaker one.