First, these are more informed and to the point:

• metasploit page with information about the bug and pre-generated vulnerable keys
• The relevant Debian security advisory. Note that the ‘openssh-blacklist’ package only contains DSA-1024 and RSA-2048 keys, if, like me, you use RSA-4096 keys this blacklist isn’t much use. Download the one from the metasploit page. (Yes, one of my keys was vulnerable! But the ssh-vulnkey tool didn’t detect it because it was 4096 bit. I assume that in time the blacklist will be extended to include other keysizes.)
• Advisory on nessus.org. I like this one because it sums it up nicely “Consider all cryptographic material generated on the remote host to be guessable.” Joy.

Some people think that having a 1-in-131k chance of getting the right key for a susceptible account isn’t enough of a risk to cause much concern. I can’t agree, I think any reasonable risk is a concern and that this is certainly a reasonable risk. Given that the default is 2048 bit RSA keys and it is reportedly likely that the generating PID is low the risk is probably higher anyway, less than 1-in-32k.

There’s an easy solution for SSH authorized_keys: check the keys against the blacklists! The metasploit page has blacklists for the usual key sizes available as well as a few less common key sizes.

What’s the risk though? The main known factor is that there are a small number of possible keys. If we know our target is x86 (highly likely) and only go for RSA 1024, 2048, and 4096 keys plus DSA keys that’s only about 131k keys (as large as that number seems, I assure you that it really is rather small in this context.) For an attacker to successfully compromise your system he’ll have to “get lucky” with a key and username combination. There are a couple of general classifications for the attack scenarios I guess:

1. Global brute-force. (Low chance of successful attack on a specific system?)
2. Targeted attack with inside knowledge. (High chance of successful attack on a specific system?)

The first scenario is best executed with a botnet. If I was an evil botnet herder I’d probably consider devoting some of my resources to this. I’d probably select only 2048 and 4096 bit keys to attack, as in my experience these are the most recommended key sizes (in fact, it is probably a good bet to try for just 2048 bit RSA keys only, as this is the default for ssh-keygen and I expect most people stick to the defaults. I’m not sure about the data-point regarding PIDs on the metasploit site, but I can imagine it to be true. (I imagine many user keys are generated as an almost first-step after installing and booting a new system, thus a low PID.) Believing the data-point I’d assume that limiting the PID seed to 10k probably increases the likely rate of successful compromises.

The other variable from the point of view of a single system is user-names. I think trying for ‘root’ is a given, and may even consider that to be the only user-name worth trying. Not going for the lowest hanging fruit, going for the ripe and juicy windfall apples. (I know admins who prefer to give ‘root’ access via ssh keys, because then you can revoke an individual’s root access without having to change the password and update everyone. There’s sudo for that these days though, stop using ssh keys.)

So, block remote root logins – as you should – and you’d probably be safe from me. But there’s also common user-names, attackers have lists of these. (I get a large number of SSH login attempts daily for user/pass combinations like bob/bob, tom/tom, … etc.) These user-names are probably a definite risk. Like I said, I see a regular flow of brute-force attempts to SSH in brute-forcing on usernames and passwords, given that this activity is common on the ‘net I reckon it is a given that it’s already happening for the bad SSH keys.

How about the likelihood of your server actually being attacked? From the point of view of the attacker this is a third variable, server address. It is a big Internet. Assuming bot-nets are randomly testing all valid ‘net IPs individual machines are probably, statistically, fairly safe. Though if I were configuring a botnet I’d pare the IP range down to blocks owned by specific co-location providers. Places like EV1 where large numbers of machines with lots of bandwidth are administrated by large numbers of totally clueless gits. If you’re on such a network your risk is likely to be higher (and who doesn’t have a server that’s in a “bad neighbourhood” purely because such neighbourhoods are cheap?)

Overall, I’d rate the chances of becoming the victim of a global-brute-force as fairly low. Still, the bad guys are going to successfully compromise some machines, it could be your unlucky day! This bug still increases your overall chances of compromise and you decrease them by fixing it. At the very least ensure that remote root isn’t permitted (and fix the situation if it is) then check all user-keys without locking down SSH.

The second scenario could leave you much more vulnerable.

If your company is likely to be targeted then it is likely that the attackers can get hold of all kinds of information. If they know the names of your employees (easy to find out) they can probably work out a list of likely user-names. If any one of your uses logs in with key-based auth and has a susceptible key you’re probably screwed (especially if they chose a 2048 or 4096 bit RSA key, like most people probably do?)

If an employee has lost a laptop with a susceptible SSH key you have a new worry (amongst the many your probably have anyway): it no longer matters how good their passphrase is. The new owner of the laptop’s data now knows the employee’s login (well, it is likely, .bash_history for example) and the size and type of their key.

What if some employee logs in from a shared machine where somebody else has root? OK, this is already a risk. You should simply never do this and employee’s who use SSH should know better! Anyway, previously the untrusted root would have to set something up to snaffle the key when the user types in their passphrase – now they can narrow it down to one of 32k keys without intervention.

What if your employee logs into another server run by someone else using an SSH key that they also use on your server? The owners of the other system now have that employee’s private key, all they have to guess is the login. Vice versa, you now have the private key for systems that the employee may log into with that same key. It probably only takes a little bit of digging to find out what companies/institutions many of the users of your system uses. The user could be security concious and may not trust you, but it’s OK the only data they’ve given you is their SSH public key, right? But now you have their private key! It is likely that they use the same key for other systems, have a guess at their username and try logging into the IPs they’ve logged in from.

There’s more…

Anyway, this is all speculation. I’m just tossing around some of the obvious risk scenarios in my head, I don’t have the data to put any numbers on them so I can’t prove anything at all. The main point is that I think there are enough risk cases that taking this potential hole in your system lightly is probably a bad mistake. You should have fixed it already.

In the end I think this is a case where it is better to be paraniod.

And I’m only talking about SSH user keys here – server certificates are a whole other nightmare. Given that you publish your SSL public key as part of the transaction I assume it would be trivial for someone to generate your private key from this data – Mavis is going to be one very happy girl. IIRC signed keys are typically only 1024 or 2048 bit (last time I worked with CA-signed server keys, years ago, our CA would only sign 1024 bit SSL keys.)