With the Quickness: HD Moore sets new land speed record with exploitation of Debian/Ubuntu OpenSSL flaw

So, for those who haven’t heard, a Debian packager modified the source used for OpenSSL on Debian based systems (Debian and the whole of the Ubuntu family) to remove the seed used for PRNG (Pseudo Random Number Generator) used when creating SSL keys.  Well, HD Moore set a new record for speed to exploit with the release of what he calls Debian-OpenSSL Toys.

HD describes the bug on the page, and I’ve quoted his explanation below:

On May 13th, 2008 the Debian project announced that Luciano Bello found an interesting vulnerability in the OpenSSL package they were distributing. The bug in question was caused the removal of the following line of code from md_rand.c

MD_Update(&m,buf,j); [ .. ] MD_Update(&m,buf,j); /* purify complains */

These lines were removed because they caused the Valgrind and Purify tools to produce warnings about the use of uninitialized data in any code that was linked to OpenSSL. You can see one such report to the OpenSSL team here. Removing this code has the side effect of crippling the seeding process for the OpenSSL PRNG. Instead of mixing in random data for the initial seed, the only “random” value that was used was the current process ID. On the Linux platform, the default maximum process ID is 32,768, resulting in a very small number of seed values being used for all PRNG operations.

Mmmm… don’t you love security tools?  Just goes to show you, no matter how great your tool set is, and I do like Valgrind, you have to understand how they work and more importantly how your code works.  No tool can be smart enough to tell you that the warning its complaining about with uninitialized data should be ignored (or at least fixed and not removed from the codebase) because it will effectively render the encryption you are trying to accomplish neutered.

The impact to this is unbelievably huge, as HD mentions:

All SSL and SSH keys generated on a Debian-based systems (Ubuntu, Kubuntu, etc) between September 2006 and May 13th, 2008 may be affected.  In the case of SSL keys, all generated certificates will be need to recreated and sent off to the Certificate Authority to sign.  Any Certificate Authority keys generated on a Debian-based system will need be regenerated and revoked.  All system administrators that allow users to access their servers with SSH and public key authentication need to audit those keys to see if any of them were created on a vulnerabile system.  Any tools that relied on OpenSSL’s PRNG to secure the data they transferred may be vulnerable to an offline attack.  Any SSH server that uses a host key generated by a flawed system is subjection to traffic decryption and a man-in-the-middle attack would be invisible to the users.

This flaw is ugly because even systems that do not use the Debian software need to be audited in case any key is being used that was created on a Debian system.

Onto HD’s toys, click read more below to continue…

This is poached directly from HD’s page for time savings and because I’m definitely not a crypto guy:

The Toys

The blacklists published by Debian and Ubuntu demonstrate just how small the key space is. When creating a new OpenSSH key, there are only 32,767 possible outcomes for a given architecture, key size, and key type. The reason is that the only “random” data being used by the PRNG is the ID of the process. In order to generate the actual keys that match these blacklists, we need a system containing the correct binaries for the target platform and a way to generate keys with a specific process ID. To solve the process ID issue, I wrote a shared library that could be preloaded and that returns a user-specified value for the getpid() libc call.

The next step was to build a chroot environment that contained the actual binaries and libraries from a vulnerable system. I took a snapshot from a Ubuntu system on the local network. You can find the entire chroot environment here In order to generate an OpenSSH key with a specific type, bit count, and process ID, I wrote a shell script that could be executed from within the chroot environment. You can find this shell script here. This script is placed into the root directory of the extracted Ubuntu filesystem. In order to generate a key, this script is called with the following command line:

# chroot ubunturoot /dokeygen.sh 1 -t dsa -b 1024 -f /tmp/dsa_1024_1

This will generate a new OpenSSH 1024-bit DSA key with the value of getpid() always returning the number “1″. We now have our first pre-generated SSH key. If we continue this process for all PIDs up to 32,767 and then repeat it for 2048-bit RSA keys, we have covered the valid key ranges for x86 systems running the buggy version of the OpenSSL library. With this key set, we can compromise any user account that has a vulnerable key listed in the authorized_keysfile. This key set is also useful for decrypting a previously-captured SSH session, if the SSH server was using a vulnerable host key. Links to the pregenerated key sets for 1024-bit DSA and 2048-bit RSA keys (x86) are provided in the downloads section below.

The interesting thing about these keys is how they are tied to the process ID. Since most Debian-based systems use sequential process ID values (incrementing from system boot and wrapping back around as needed), the process ID of a given key can also indicate how soon from the system boot that key was generated. If we look at the inverse of that, we can determine which keys to use during a brute force based on the target we are attacking. When attempting to guess a key generated at boot time (like a SSH host key), those keys with PID values less than 200 would be the best choices for a brute force. When attacking a user-generated key, we can assume that most of the valid user keys were created with a process ID greater than 500 and less than 10,000. This optimization can significantly speed up a brute force attack on a remote user account over the SSH protocol.

In the near future, this site will be updated to include a brute force tool that can be used quickly gain access to any SSH account that allows public key authentication using a vulnerable key. The keys in the data files below use the following naming convention:

/ Algorithm / Bits / Fingerprint-ProcessID and / Algorithm / Bits / Fingerprint-ProcessID.pub

To obtain the private key file for any given public key, you need to know the key fingerprint. The easiest way to obtain this fingerprint is through the following command:

$ ssh-keygen -l -f targetkey.pub 2048 c6:7b:14:fa:ae:b6:89:e6:67:17:ee:04:17:b0:ec:4e targetkey.pub

If we look at the public key in an editor, we can also infer that the key type is RSA. In order to locate the private key for this public key, we need to extract the data files, and look for a file named:

 rsa/2048/c67b14faaeb689e66717ee0417b0ec4e-26670

In the example above, the fingerprint is represented in hexadecimal with the colons removed, and the process ID is indicated as “26670″. If we want to authenticate to a vulnerable system that uses this public key for authentication, we would run the following command:

$ ssh -i rsa/2048/c67b14faaeb689e66717ee0417b0ec4e-26670 root@targetmachine

Tools - GetPID Faker Shared Library (4.0K) - Ubuntu Root Filesystem (4.9M) - Key Generation Script (8.0K)

Keys - SSH 1024-bit DSA Keys X86 (30.0M) - SSH 2048-bit RSA Keys X86 (48.0M) - SSH 4096-bit RSA Keys X86 (94.0M)

Frequently Asked Questions

Q: How long did it take to generate these keys?
A: About two hours for the 1024-bit DSA and 2048-bit RSA keys for x86. I used 31 Xeon cores clocked at 2.33Ghz.

Q: Will you share your code for distributing the key-generation across mulitple processors?
A: Nope. The code is hardcoded for this specific cluster and is too poorly-written to be worth cleaning up.

Q: How long does it take a crack a SSH user account using these keys?
A: This depends on the speed of the network and the configuration of the SSH server. It should be possible to try all 32,767 keys of both DSA-1024 and RSA-2048 within a couple hours, but be careful of anti-brute-force scripts on the target server.

Q: I use 16384-bit RSA keys, can these be broken?
A: Yes, its just a matter of time and processing power. For mere mortals, 4096-bit keys are already a little on the paranoid side. All possible 4096-bit keys should be available within the next day or so. It is possible to generate all combinations of 8192-bit and 16384-bit keys, but I probably have better uses for my processors :-)

All that I can say is, unbelievable.  Serious flaw, yes, but the turnaround time by HD is ridiculous… I think he’s trying to get himself nominated for a pwnie award.  HD, it’s cheating if you are on the voting panel though!

-Nate