Debian OpenSSH Vulnerability

In May 2008, a bug was discovered in the Debian OpenSSL package which affected the seeding of the random number generator (RNG) used to generate keys. Any SSH keys generated by affected systems should be considered compromised. GnuPG keys are not affected. See the official Debian security advisory for details.

This does not mean that an attacker could immediately guess your private key, but because there was significantly less entropy being introduced into the seeding of the RNG, the key space was significantly reduced making a brute-force attack feasible. As I understand it, the primary source of entropy for seeding the RNG was originally uninitialized memory from the heap. Additional, more predictable components like the current process ID (an integer between 1 and 32,768) were also used. Due to an erroneous patch introduced in September 2006, uninitialized memory was no longer used in seeding the RNG leaving the process ID as the primary source of randomness. Thus, generated keys can be predicted to the extent that one knows how soon after boot time a key was generated. For example, SSH host keys are usually generated immediately after installation and so they are likely to have been generated by a processes with IDs, say, less than 500.

If it were not for this ever so small bit of “randomness,” this bug would likely have been discovered much sooner, before the patch made it to stable distributions, as someone would have noticed that all their SSH keys were the same. Unfortunately, as they say, bad cryptography looks the same as good cryptography.

Once the bug was discovered, Debian security updates were released that blacklisted the vulnerable keys, causing the system to fall back to a password-based login. If you have an affected key and try to log into an updated system, you may see a message like the following:

Public key 81:e6:75:64:17:5f:e2:ff:12:c3:ac:85:43:1e:6a:3c blacklisted (see ssh-vulnkey(1)); refusing to send it

Thus as long as your system is up to date, you can sleep well knowing that it won’t be compromised and update your key at your leisure. However, if you have been used to using ssh-agent and key-based authentication, typing your password over and over will soon become burdensome and you’ll want to generate a new key.

The remainder of this article discusses how to check your key and generate a new one if necessary. If you would like to read more about the situation, Russ Cox wrote a very nice article which provides some technical background and documents the decisions leading up to the offending patch.

Here’s the description from the ssh-vulnkey man page:

A substantial number of keys are known to have been generated using a broken version of OpenSSL distributed by Debian which failed to seed its random number generator correctly. Keys generated using these OpenSSL versions should be assumed to be compromised. This tool may be useful in checking for such keys.

Running ssh-vulnkey on a box that I log into, I find the following:

$ ssh-vulnkey
/home/jrblevin/.ssh/authorized_keys:1: COMPROMISED: RSA 2048 81:e6:75:64:17:5f:e2:ff:12:c3:ac:85:43:1e:6a:3c jrblevin@syd
#
# Some keys on your system have been compromised!
# You must replace them using ssh-keygen(1).
#
# See the ssh-vulnkey(1) manual page for further advice.

The solution is to generate a new key and update the relevant ~/.ssh/authorized_keys files on the systems you access via SSH. First, backup the old key:

$ cd ~/.ssh/
$ ls
authorized_keys  config  id_rsa  id_rsa.keystore  id_rsa.pub  known_hosts
$ mkdir backup
$ mv id_rsa* backup

Then, generate a new one:

$ ssh-keygen
Generating public/private rsa key pair.
Enter file in which to save the key (/home/jrblevin/.ssh/id_rsa):
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /home/jrblevin/.ssh/id_rsa.
Your public key has been saved in /home/jrblevin/.ssh/id_rsa.pub.
The key fingerprint is:
bf:6e:7e:a4:b9:5e:6f:65:a2:bb:00:79:4b:bf:d5:cc jrblevin@roark
The key's randomart image is:
+--[ RSA 2048]----+
|                 |
|                 |
|                 |
|         .       |
|        S o      |
|         = o. .+o|
|          ++o..+E|
|          ++o+.  |
|         =*o++.  |
+-----------------+

Finally, add the contents of ~/.ssh/id_rsa.pub to the ~/.ssh/authorized_keys file on each system you want to log into using your new, secure, SSH key. Don’t forget to remove the old compromised key from the authorized_keys file.