The Debian OpenSSL Predictable Random Number Generator Vulnerability

Rec 17-may-2008 14:08

By now you probably heard it elsewhere, but here's my take on the issue: several crucial programs that use public key cryptography services provided by certain versions of the OpenSSL library shipped with Debian-derived Linux distributions (including Ubuntu and Kubuntu) have a severe vulnerability that may enable attackers to gain access to your machines. The exact extent of the possible access depends on how exactly things are set up in your computer, as I'll explain below.

The root of the problem is this: almost two years ago, one of the maintainers of the Debian version of the OpenSSL package disabled a few lines of code in the random number generator. The motivation behind the change seems to have been because running that particular part of the code through Valgrind, one of many automated tools for finding common problems in computer source code, caused it to complain about a possible use of uninitialized data. This would prove to be a disaster.

The security of almost all crypto-based programs depends on choosing keys that are unpredictable by an outsider. Normally, when you ask the OpenSSL routines to generate, say, a x-bit number, it is randomly drawn from a set of 2^x numbers. Let's work this calculation out for a couple of values:

• If you ask for a 32 bit random number, it'll get you one from a set of four billion possible numbers.
• If you ask for a 64 bit random number, it'll be drawn from a set of eighteen quintillion numbers. It's a set so large that most people can't even imagine it.

When choosing keys for public key cryptosystems, we need random number larger than 100 decimal digits; the size of the set where this number comes from is so absurdly large that most people don't even know what to call it, yet it does have a name -- it's "ten duotrigintillion" items, also known as "one googol".

But what all that means is that the chance of an outsider guessing the correct number that comprises our keys is next to nil because there number of possibilities is all those duotrigintillions. Trying each and all of them is not viable for the exact same reason: it's just too much. In other words, your key derives its security from being indistinguishable from the rest of the crowd.

The change the Debian maintainer made to the code, however, caused the OpenSSL random number generator to output random numbers drawn from a set of only 32,768 possible numbers. Suddenly the crowd is WAY smaller, so small that it becomes perfectly viable to list them all.

Most users of Windows probably never heard about SSH, but most users of Linux that go beyond the graphical user interfaces, myself included, use SSH every single day. For the benefit of my many Windows-centric readers: SSH is kind of a remote control program that allows people to control their computers over the Internet, a bit like Windows' Remote Desktop, but (normally) much more secure. Find out more about it at the Wikipedia entry for SSH.

SSH uses public key systems for two things: authenticating servers and optionally authenticating users. But because of the change the Debian maintainer made, if you generated the server keys (automatically done when the SSH server is first installed or upgraded) with a vulnerable version of the software, the key is almost guaranteed to be in that list (or that one).

This means an outsider can mount what crypto people call a "man-in-the-middle attack": first, he asks your SSH server for its public keys (the server can't deny, otherwise legitimate users wouldn't be able to connect.) Then he uses the list to see which private keys correspond to your public keys (that's the part that fails if the random number generator is good.) Now he can install a SSH server that identifies exactly like yours. If he can also redirect you to his server (not a very hard thing to do), it can lure you to connect to his server instead of yours and, if he is careful enough, you won't notice the difference well past the point you typed in your passwords. If the attacker is really careful, you might not notice at all.

For authenticating users, SSH provides several authentication methods. You can use the older "name+password" method, but many people, myself included, use the modern "public key authentication" method, which is normally more secure and provides lots of other practical advantages: for instance, you could give me acess to a server just by putting my public key there -- I woundn't need to go there and set up yet another password; this makes it possible for me to have one single password to remotely access several computers yet none of them actually knowing what my password is.

However, if the key I use to identify myself was generated with the vulnerable SSH version from Debian, my key would surely be one of those 32,768 -- which means it would be easy for an outsider to figure out exactly what is the corresponding private key. Unless something else stops him, this outsider could access all the computers I have access to, just as I can.

Notice that the vulnerability is in the key generation process. This explains why I wasn't affected myself -- my current SSH keys were generated circa 1999, using a version of the SSH program that didn't have this random number generator problem. If your personal keys (in ~/.ssh/id_dsa or ~/.ssh/id_rsa) arent't in the compromised set, you aren't in the high risk group. But there may be other risks -- read on.

To check whether your key is affected, do this:

• Upgrade to the latest version of the SSH package. First, give a apt-get update to get the new package lists. Then, in Debian, give a apt-get install openssh-client openssh-server openssh-blacklist. The upgrade process will check whether your server's keys are vulnerable and offer to regenerate them. If they weren't vulnerable, they'll be kept unchanged. This will solve the "server" part of the problem.
• Run the ssh-vulnkey utility that comes with the new version of the SSH tools. It will check whether the keys in your ~/.ssh directory are vulnerable. If it says "COMPROMISED", you generate a new set of keys with the ssh-keygen utility (read the man page for details). Now you should copy those new keys to all ~/.ssh/authorized_keys files in every server you previously copied your vulnerable keys to. This is the tricky part -- it may very well be that you don't remember all computers you ever copied your vulnerable key to; or some of them may be unreachable to you at the time. And if you have a vulnerable key in hundreds of servers, it will be quite a lot of work.

The new SSH server will reject connection attempts from users using keys in the blacklist, so even if your system still has users with vulnerable keys, they will no longer be able to connect.

On the other hand, the new SSH client will not prevent you from connecting to servers with blacklisted keys. This is a bit unfortunate, because you may have no simple way to determine whether you're connecting to your real server or to a trap in the form of a man-in-the-middle attack. But it is understandable why the OpenSSH developers did this: in many cases, SSH is the only way people have to get to their servers. If the new SSH client prevented them from getting there, it might render the users unable to fix them. But you shouldn't connect to servers with blacklisted keys unless you have other means of making sure you're actually connecting to the server you really intend to.

If your version of the SSH toolset already has the ssh-vulnkey utility, you can test if a remote server has vulnerable keys with the following commands:

ssh-keyscan -t dsa,rsa your-server-name-or-ip-address | cut -d' '  -f2- | ssh-vulnkey -

(The "ssh-vulnkey" man page has a similar recipe, but it doesn't work; the ssh-keyscan utility outputs an extra initial field with the server address that the ssh-vulnkey doesn't understand. That's the reason for the cut command in the middle for the pipe.)

The problem may be deeper still: one thing I didn't see people commenting all that much was the impact of all this to the symmetric keys used for encrypting the bulk data past the authentication phase. If there are only 32,768 symmetric keys as well, it should be trivially easy to decrypt the data in transit (that's why intelligence agencies record everything, even if they can't decrypt it today -- they might be able to decrypt it later.) The sad conclusion would be that during almost two years, Debian's SSH was almost as insecure as TELNET.

This whole mess brought new fuel to an old holy war: the fact that the Debian maintainers make changes of their own in many packages. I think that most of the time this is a good thing: it keeps the platform stable and things generically working. For instance, I recently had a 2.6.18 kernel failing to run on a brand new server because it didn't have support for the Intel ICH9 SATA chipset, while Debian's 2.6.18 kernel worked just fine because the maintainers usually backport new hardware support from newer kernels. This made a lot easier to get the server running and pinpoint exactly where the problem was so we could fix our custom kernel as well.

In the OpenSSL's random number generation mess, however, we had a critical security code changed by someone who obviously didn't understand the implications. I wouldn't want to be in that guy's shoes; no doubt many curses are being directed his way. And it also gives Debian a bad press that I think it doesn't deserve, along with the usual jokes. People hav even been ressurecting an old Dilbert strip.

My suggestion to the Debian people is to have only certain knowledgeable people touch security critical stuff. But, sure, this easier said than done. The mere act of establishing what constitutes "security-critical" is a lot of work already -- plenty of stuff that doesn't look like security-related at first sight and yet it is ("Ooooh! I didn't know that a random number generator was a security critical thing!"). Let alone gathering knowledgeable volunteers.
top