Debian Deleted Two OpenSSL Lines to Quiet Valgrind. For 20 Months, Its Keys Were Predictable.

In 2006, Debian removed two lines from its copy of OpenSSL to quiet a debugging tool. For the next 20 months, Debian systems, and later Ubuntu systems, generated encryption keys that could be predicted. The maintainer who made the change had asked the OpenSSL developers first.

On 1 May 2006, Kurt Roeckx, who maintained Debian’s OpenSSL package, wrote to openssl-dev, a public OpenSSL mailing list. Valgrind, a tool that reports when a program makes decisions based on memory it never initialized, was showing many warnings in programs that used OpenSSL. Roeckx had traced them to two lines in a file called md_rand.c, where the library’s random number generator was adding an uninitialized buffer to its pool.

“What do you people think about removing those 2 lines of code?” he asked. He admitted he was not even sure how much randomness uninitialized data contained.

Ulf Möller answered that doubt the same day, from an openssl.org address: “Not much. If it helps with debugging, I’m in favor of removing them.” The next day, Geoff Thorpe pointed to a switch the code already had for memory-checking tools: “build with -DPURIFY.”

Both lines were the same call, MD_Update(&m,buf,j). Roeckx removed both. Only one of them was safe to delete.

Why two identical lines did different jobs

OpenSSL kept its randomness in a pool — in effect, the running state of a hash function. One of the two calls sat in the function that hands out random bytes. Before filling the caller’s buffer, it mixed in whatever the buffer already held, which could be memory nobody had set. OpenSSL already wrapped that call in #ifndef PURIFY, so it could be compiled out for Purify, another memory-checking tool. Removing it was harmless.

The other call sat in the function that adds new data to the pool. It was the line through which seed data — the unpredictable input the whole generator depends on — actually entered. Without it, OpenSSL still raised its estimate of how much randomness it held, but the seed itself was thrown away. That left one input that Russ Cox, who later dissected the code, called “a little unpredictable”: the process ID, the number the operating system assigns each running program. The generator mixed it in on each call.

That is why, as Cox put it, an affected system “could only generate 32,767 different possible SSH keys of a given type and size” — one for each process ID. SSH (Secure Shell) keys let administrators and developers log in to remote machines. Debian’s wiki adds that the generator’s output also differed by processor architecture — little-endian 32-bit, little-endian 64-bit or big-endian 32-bit — for 98,301 possible streams of “random” numbers in all.

Twenty months of predictable keys

The change took effect in Debian’s openssl package version 0.9.8c-1, uploaded to Debian’s development branch on 17 September 2006. From there it reached Debian’s next stable release, etch, and the Debian-derived Ubuntu, whose security notice lists versions 7.04, 7.10 and 8.04 as affected.

On 13 May 2008, a Debian security advisory announced that “Luciano Bello discovered that the random number generator in Debian’s openssl package is predictable,” the result of “an incorrect Debian-specific change.” The affected keys included SSH, OpenVPN and DNSSEC keys, key material for X.509 certificates — the kind websites use for HTTPS — and the session keys of encrypted SSL/TLS connections. Keys generated with GnuPG or GnuTLS were not affected. Ubuntu published its own notice the same day.

Some keys were compromised even though they had been generated elsewhere. The advisory warned that all DSA (Digital Signature Algorithm) keys “ever used on affected Debian systems for signing or authentication purposes” should be considered compromised. DSA needs a secret random value every time it signs, and on an affected machine that value came from the broken generator.

Within two days, many of the weak keys were public. On 15 May, the SANS Internet Storm Center reported that the security researcher H D Moore had posted a web page with all the SSH 1024-, 2048- and 4096-bit RSA keys he had brute-forced. Debian shipped blacklists of weak keys and a checker, ssh-vulnkey.

Replacing the keys took far longer. In a 2009 study, Scott Yilek and four co-authors scanned more than 50,000 SSL/TLS-enabled web servers every day and found 751 with vulnerable certificates. Of the hosts that were vulnerable when the survey began four days after the disclosure, about 30% were still vulnerable almost six months later, and certificate authorities kept issuing certificates for weak keys.

What the first reactions got wrong about asking OpenSSL

On the day of the advisory, Ben Laurie of the OpenSSL core team wrote on a cryptography mailing list that two years earlier, Debian had “fixed” a problem reported by Valgrind “by removing any possibility of adding any entropy” — unpredictable input — to OpenSSL’s pool. Vendors “should contribute their patches upstream to the package maintainers,” he wrote. “Had Debian done this in this case, we (the OpenSSL Team) would have fallen about laughing.” His maxim: “never fix a bug you don’t understand.”

The list archive tells a more tangled story. Roeckx had asked on openssl-dev, a list that OpenSSL’s own support page described as being for “Discussions on development of the OpenSSL library.” Laurie later argued, as LWN reported, that openssl-dev was not the place to discuss the development of OpenSSL. Yet Möller’s answer had come from an openssl.org address.

What did not go back upstream was the patch itself. Cox noted that Roeckx’s message did not name the functions containing each call — the detail that separated the harmless line from the essential one — and that the OpenSSL developers “responded incorrectly, probably without actually looking at the code.”

Lessons from two identical lines

A warning names a symptom, not a purpose. Valgrind’s warnings were accurate: uninitialized memory really was reaching the pool. Valgrind could not tell anyone that one of the two lines also carried the seed.

Code that looks the same can do different jobs. As Cox put it, “The fact that one instance wasn’t essential made it look like the other instance wasn’t essential.” His first lesson was “Try not to write clever code. Try to write well-organized code.”

An answer on a mailing list is not a review. Cox was surprised that nobody followed up with OpenSSL once the patch was written. In his words: “Mailing list discussions aren’t a substitute for real code review.”

Both lines read MD_Update(&m,buf,j). One stirred leftover memory into the pool; the other let the seed in.

Roeckx asked whether two lines could go. The question that mattered was what each one did.

Explore

Stay connected