The Debian OpenSSL bug

A key is only as unpredictable as the random numbers it’s made from, and a generator is only as good as its seed. In 2008 that stopped being a textbook point. For nearly two years, the random number generator in OpenSSL, as packaged by Debian, the operating system many servers ran (and the base of Ubuntu), had almost no seed at all. Every key it made was one of a few tens of thousands, and anyone could list them all.

This page takes the bug apart: what the change was, why it looked harmless, how an attacker uses it, and why nothing seemed wrong for so long. It’s a story about how quietly randomness fails, not about blame: the change was made in good faith, for a sensible reason, and its danger was easy to miss.

1 · What happened

OpenSSL is a library of cryptographic code used by a great deal of software: web servers, SSH (the tool for logging in to remote computers) through its key generator, VPNs. Like every such library, it has a random number generator: a pool of bits that the operating system’s entropy (unpredictable measurements such as the timing of interrupts) is mixed into, and that keys are drawn from.

In September 2006, a change was made to Debian’s own copy of OpenSSL. Memory-checking tools such as Valgrind, which find bugs by watching for programs reading memory they never set, were reporting warnings inside OpenSSL’s random number generator. The change removed the lines the warnings pointed to.

One of those lines was the one that mixed entropy into the pool. Without it, what was left to make the output differ from one run of a program to the next was the process ID: the number the operating system gives each running program. On Linux then, process IDs went up to 32,767. So each kind of key (each type and size, on each kind of processor) could come out as one of at most 32,767 keys.

On 13 May 2008, Debian announced the problem (security advisory DSA-1571), found by Luciano Bello. Every key made with the affected package, on Debian and on systems built from it such as Ubuntu, had to be thrown away and made again: SSH keys for servers and for people, the keys behind websites’ certificates, VPN keys.

2 · Two identical lines

OpenSSL’s pool had two functions that mattered here. One adds bytes to the pool: the operating system’s entropy comes in through it. The other hands out random bytes. Each contained the same line, which mixes a buffer of bytes (buf) into the hash that keeps the pool’s state:

in ssleay_rand_add(), which adds entropy to the pool

/* buf: the bytes being added, such as the system's entropy */
MD_Update(&m, buf, j);

in ssleay_rand_bytes(), which hands random bytes out

/* buf: the caller's output buffer, which may not be set yet */
MD_Update(&m, buf, j);

The two lines (from OpenSSL’s random pool, simplified), and a toy of the pool with each as a switch. Below, a program makes a key six times: each run gets the system’s fresh entropy and a process ID, and runs 2 and 5 happen to get the same ID. With both lines in, every key is different. Switch off the second line: still all different. Switch off the first: the entropy goes nowhere, and runs 2 and 5 make exactly the same key.

In the function that hands bytes out, buf is the caller’s output buffer, about to be filled. Mixing its old contents in is a small bonus at best, and those contents are often memory that was never set: that’s what the tools complained about. Removing this line costs nothing. OpenSSL’s own code already allowed it to be left out when building for a memory checker.

In the function that adds entropy, buf is the entropy. Removing this line throws away everything the operating system offers. The warnings pointed at both lines because both read buf; only one of them was safe to lose.

The question had been raised on a public OpenSSL mailing list before the change was made, and nobody spotted the danger. Read side by side, the two lines are identical; what makes them different is everything around them.

3 · Every possible key, in a list

If a key can only be one of 32,767, an attacker doesn’t have to break anything. They run the broken package once for each process ID, keep every key it makes, and look up whichever key they meet. Only the public half of a key is ever shown (to log in, or in a website’s certificate), but it’s enough to look up, and the list gives back the private half that goes with it.

Start by making a key.

Make a key on a machine with the broken package (the toy’s key is 128 bits: real SSH keys are bigger, but just as easy to list). Then build the attacker’s table, running the broken generator once for every process ID, timed in your browser, and look your key up by its fingerprint. Try the same with a fixed machine: its key isn’t there.

The real lists were made within days of the announcement, for the common key types and sizes, and published. With one, logging in to a server that trusted an affected SSH key took at most 32,767 tries, and usually just a look-up.

4 · Why nobody noticed

For two years, nothing looked wrong. The keys looked like keys, the generator’s output looked random, and programs worked. Statistical tests, the usual way of checking random numbers, would have passed it too:

The same checks on 100,000 bits from the broken package (one process ID) and from this browser’s generator: how many bits are 1, how often a run of equal bits ends, how evenly the 256 byte values turn up (the chi-squared score from Old ciphers, here against equal counts), and how much each bit predicts the next. The two columns are indistinguishable; the tests check this in the toy for three process IDs.

The broken generator still hashes its state: everything it puts out looks perfectly random. What’s wrong is that there are only 32,767 streams it can produce, and no test of a single stream can see that. As the randomness page puts it: bad random numbers look just like good ones.

What does show it is looking across many machines. If keys are made from a few thousand possibilities, then among a few hundred machines, two will soon have made the same one. That’s the birthday problem: with N equally likely values and m picks, the number of matching pairs expected is about m(m − 1) / 2N, which for 1,000 machines and 32,767 values is about 15.

Many machines each make a key (each with a random process ID, and fresh entropy that the broken ones throw away). The count is of keys that some other machine also has. With the broken package, a few hundred machines are enough for matches to appear; fixed, there are none, however many machines.

5 · The clean-up

Fixing the package was one line. Fixing the keys was the hard part, because they were everywhere, copied to other machines, and the people who had made them didn’t know which were weak. Debian and Ubuntu published blacklists of the weak keys’ fingerprints with tools to check against them (ssh-vulnkey for SSH keys, openssl-vulnkey for others), and servers were changed to refuse blacklisted keys. Certificate authorities reissued certificates for affected websites.

One kind of key was hurt even if it had been made somewhere else. A DSA key (a common kind of SSH key) needs a fresh random number for every signature it makes, and the signature, the message and that number together give away the private key. If the number came from the broken generator, it was one of 32,767: an attacker who saw a single signature could try each in turn until one worked, and so recover the key. So DSA keys merely used on an affected machine had to be replaced as well.

And the long tail was long. A study the following year (Yilek, Rescorla, Shacham, Enright and Savage, “When Private Keys are Public”, 2009) watched websites’ certificates and found many still using weak keys months after the announcement.

6 · What it teaches

Entropy is invisible. Nothing in a key, or in a generator’s output, says how unpredictable it really was. Losing the entropy changed nothing anyone could see.
A change to cryptographic code needs someone who knows why each line is there. The two lines were identical to the eye. Only knowing the code around them could tell them apart.
Test the seeding, not only the output. A test that the generator’s output changes when its entropy changes, or that two runs with the same process ID differ, fails at once on the broken package. Every statistical test passes it.

Summary

In 2006 a change to Debian’s OpenSSL, made to quiet memory-checker warnings, removed the line that mixed the system’s entropy into the random pool. What still varied was the process ID: at most 32,767 keys of each kind.
An identical line nearby was safe to remove; this one wasn’t, and side by side they looked the same.
An attacker lists every possible key once, and looks up any key they meet.
The output passed statistical tests: only the number of possible streams was wrong, which no test of one stream can see. Duplicate keys across many machines do show it.
The weak keys had to be found and replaced everywhere, and DSA keys used on affected machines too.