Transmissions
"How to Neuter Cryptography for Thousands of Users in Two Lines"
by Dragorn
Two years ago a vendor made a nonstandard modification to a cryptography library used by thousands of systems for SSH, VPN, SSL, and most other encrypted traffic. For two years this change went undetected, introducing weaknesses into the key generation and encrypted traffic.
Sound like a large commercial vendor (synonym: small, limp) colluding with a spy-happy government to weaken cryptography to ease surveillance? A foreign governmental agency hoping to accomplish the same? Would you believe an open-source developer on arguably one of the most militantly GPL and open Linux distributions, on a completely open-source project?
In September of 2006, a Debian developer followed a warning from the memory auditing tools Purify and Valgrind, and identified a potential read of uninitialized memory in OpenSSL, and commented out the offending line. Unfortunately this line added the supplied data to the entropy pool, effectively removing the randomness at the heart of the cryptographic engine. This change was then picked up by Ubuntu, and presumably any other Debian-based distribution.
The entropy pool is used to create pseudo-random (since very little in a computer is actually random) data used to create cryptographic keys. Typically entropy comes from a combination of sources, such as network packet rate, disk I/O characteristics, typing rates, mouse movement, and on systems which provide it, a random number generator in hardware. The kernel keeps track of these sources, and adds the entropy to the system-wide random pool, but during initialization, OpenSSL must add the entropy to its own sources.
Instead of seeding the random number stream from the process ID and the system-wide entropy pool, the crippled OpenSSL Pseudo-Random Number Generator (PRNG) uses only the process ID, on Linux falling between 1 and 32,767, meaning instead of 24128 (the minimum amount of entropy OpenSSL expects) possibilities - northwards of an undecilion (and yes I had to look on Wikipedia for that) possibilities, there are instead 2,415 possibilities.
Put another way, instead of needing 3.7 x 1032 gigabytes to store every possible SSH host key, it now takes about 40 megabytes per hardware platform (Intel 32-bit, Intel 64-bit, PowerPC, etc.). Put a third way, that's 1.9 x 10-32 percent as many keys as there should have been. (And if you remember your high school math that's 0.0, thirty-one zeroes, 19. It's actually hard to represent these numbers in this article - they're so small.)
Not only have the total number of possible keys been drastically reduced, but a key is now much more predictable depending on when it was generated, as noted by H. D. Moore. Many services generate their keys during install, meaning the process ID of the installer is likely to fall within a predictable range.
The significantly reduced total key space makes brute force attacks against user logins and impersonation of servers trivial. Performing a "man-in-the-middle" attack (over, for example, a wireless network) becomes as simple as fingerprinting the public key of the host and providing the private key from the table of pre-calculated keys. No alert is raised that the host key has changed, and the client continues as normal.
Administrators of systems where a user has uploaded an SSH user key are also vulnerable, even when the system itself does not use a vulnerable OpenSSL library.
Since SSH user keys cover a similarly small key space, brute forcing a user is only a matter of time. Most SSH servers allow seven attempts per connection, meaning the average search area for matching the user's key is just over 2000 connections (32,768 divided by two since on average a key will be found in half of the search area, divided by seven attempts per connection). If the attacker has access to the user's public key (via a web page, control of another server where the user has uploaded a key, etc.), then matching it becomes a matter of simply matching the pre-computed keys. Since the process ID of the SSH-keygen process is moderately guessable, the search area can be narrowed even further, making brute forcing users with vulnerable keys even easier.
H. D. Moore has pre-computed the SSH host and user keys for several platforms, available at: hdm.io/tools/debian-openssl
This flaw affects every application which uses OpenSSL, and is especially insidious because it introduces a persistent, permanent vulnerability which does not go away simply by upgrading the affected library. Any application which stores a key generated by the vulnerable library will continue to be vulnerable: OpenSSH, OpenVPN, Apache, IMAP-SSL, Bind, SSH clients, some hard drive encryption schemes such as EncFS, and any other SSL based application, must regenerate the keys and notify users that the keys and certificates have changed.
All SSH RSA user keys generated on a weakened system must be replaced on every system they have been copied to. All SSH DSA user keys used on a weakened system must be replaced - even if they were generated prior to the weakness - due to a flaw in the DSA mechanism that reveals the private key if an attacker captures multiple uses of the same cryptographic nonce, which is generated by the same flawed PRNG.
Additionally, any encrypted traffic exchanged from or to a weakened system is now vulnerable to attack - even if the keys used predate the vulnerability - including any traffic performed over the past two years which might have been logged by anyone between you and the affected system.
Again, this includes SSH and any service using SSL, such as HTTPS, the very traffic containing sensitive information you encrypted to protect in the first place. The random seed is used in the PRNG to generate per-session symmetric encryption keys, which are faster and require less resources to encrypt data than the public-key method used to identify a server.
How easy could it be to crack saved SSL sessions? In 1996, Netscape used a weak PRNG seed (a hash of the time, process ID, and parent process ID) which could generate, at best, a seed of 47-bits (247 possibilities).
Ian Goldberg and David Wagner, students at Berkeley, wrote a brute-force attack which could break an SSL session in 25 seconds. Using 1996 level hardware, they were able to break the SSL sessions, without knowing the keys, of a seed with four billion times more entropy than the weakened OpenSSL seed. SSH will likely show similar times, especially when the keys themselves are guessable.
How does something like this happen?
Most likely, a combination of good intentions, ignorance, and lack of vigilance. Typically, reading from uninitialized memory is a bad thing - it will have unpredictable results since the value is unknown. When seeding a pool of random data, reading from uninitialized memory is at worst useless - the memory contains all zeroes - and at best another source of semi-random data to be combined into the pool.
Instead of fixing the initial seed of uninitialized memory, the developer commented out the line which used the uninitialized memory where the function adds the input to the entropy pool. By falling into a rote fixing pattern where the goal was to eliminate warnings from Purify, rather than to understand the code and how it was used, a simple mistake became an enormous flaw. Lack of community vigilance in spotting this change during testing allowed it into the main codebase.
Something of this magnitude will likely happen again, though hopefully not for some time, due to the publicity this exposure has gotten. The only solution is to be vigilant about what is modified and installed. Monitor critical packages for modifications, contribute to auditing on your favorite distribution, and don't mess with random number generators.