Authors:

Complete Citation

Debian Security Advisor: http://www.debian.org/security/2008/dsa-1571 National Vulnerability Database: http://nvd.nist.gov/nvd.cfm?cvename=CVE-2008-0166 Metasploit: http://www.metasploit.com/users/hdm/tools/debian-openssl/ Debian Wiki, SSL Keys: http://wiki.debian.org/SSLkeys

Abstract

Luciano Bello discovered that the random number generator in Debian's openssl package is predictable. This is caused by an incorrect Debian-specific change to the openssl package (CVE-2008-0166). As a result, cryptographic key material may be guessable.

Dilbert random

XKCD random

Annotations

A perfect example of the advantages and disadvantages of Open Source code.

In order to generate "more" random numbers a random number generating function needs to be seeded in such a way as to produce more entropy. OpenSSL? uses uninitialized memory locations since the contents of these locations is not necessarily known it injects more "randomness" into the seed for the generator. However, during a code audit of Open SSL by Debian code maintainers using software tools such as: Valgrind and Purify to "detect many memory management and threading bugs, avoiding hours of frustrating bug-hunting, making your programs more stable. You can also perform detailed profiling to help speed up your programs." (Source Valgrind website, Section: About). These tools are not fool proof and do require some careful human analysis before correcting issues in code. Valgrind complained about the uninitialized data being used to seed the generator, the auditors were not familiar with the code, but did check with the OpenSSL? mailing list. Two responders on the OpenSSL? mailing list addressed the problem: one person said removing it may reduce the entropy, but no one was sure by how much and was in favor removing the code in order to improve debugging. The other responder also favored removing the code in order to get rid of warnings from Valgrind. This was two years ago in 2006.

Code Changes

Why is this a problem? The random number generator since it had the "uninitialized variables" removed from the seeding process was only seeded the current process ID. One of the goals of making something very secure at least in terms of cryptography is to have a tremendous amount of possible values so that brute force guessing is infeasible with current computing resources. However, with the only seed to the random number generator begin the current process ID the possible seed values is given a definite upper limit of: 32768.

Problems: any keys generated for SSH, etc that use OpenSSL? in the past two years need to be regenerated since it is possible that an offline attack can break, easily, any keys generated in the past two years. Other problems, having to reissue certificates with regenerated keys opens everything up to possible man in the middle attacks.

Interesting FAQs:

From Metasploit:

"Q: How long did it take to generate these keys?

A: I used 31 Xeon cores clocked at 2.33Ghz. It took two hours to generate the 1024-bit DSA and 2048-bit RSA keys for x86. The 4096-bit RSA keys took about 6 hours to generate. The 8192-bit RSA key generation would take about 100 hours at its current rate and will likely be stopped before completion."

This is a very reasonable number of machines to find at any institute's computing cluster or even anybody with access to large botnets can generate these keys even faster with more machines and processing power available to them.

-- AndrewBlaich - 05 Jun 2008