Let me just point out, that the consequences affect all users of SSH. Therefore IMHO all other Linux and BSD distributions need to release a security update to OpenSSH as well, to prevent the use of insecure (too common) keys, because it threatens the security of their systems as well!

Apparently, there are only about 2^15 different keys generated by the SSH versions shipped with Debian for 2 years. It's really surprising that noone noticed this earler. This is just about 32767 different keys. (For each type, size and endianess, but that still makes this number much much much too low) The weakness is caused by a bad random number generator in the Debian package.

Hackers have already generated all these 32767 different keys, for two key lengths and types. In a few hours, they'll also have generated all the 4096 bit keys that could have been generated. Other key lengths are uncommon and sometimes might even be unsupported. Most people use keys with length 1024 or 2048.

So we now have about 32767 keys which are used by lots of Debian and Ubuntu users. That's not very much. Now you have to realize how the keys are used:

The key is used to log into a system without a password. Sometimes a key is protected with a passphrase (you really should do that), but this doesn't help here, because an unencrypted clone of the key was already generated.

Sometimes (or let me even claim 'often') one such key is also used to login as root into a server. This is equivalent to just 32767 different passwords being used as root passwords. So with about this number of tries, an attacker might be able to log into your server as 'root'!

Now the weakness is 'distributed' by the users, it's not just a server-side vulnerability. If your server is running e.g. RedHat, it doesn't mean it is secure!.

In fact, if your server is running Debian and you installed the Debian security update for openssh, it will be much more secure than the RedHat server. Because the Debian server has a blacklist of keys that are too common. The other-Linux server who doesn't have this blacklist doesn't know that a certain 'weak' key is not trustworthy.

Fixing the bad key-generation is just half of the deal. "Recalling" all the keys in use out there is the big challenge, that affects all systems using SSH (and to a different extend, SSL). The most reliable way is if all other distributions would release a security update as well, which refuses to accept the keys that were generated by vulnerable Debian systems.

Let me just repeat it in other words: Any Linux/Unix/*BSD system is vulnerable that grants access to a key that was generated on an affected Debian or Ubuntu system. (Until the system has a reliable detection method of such weak keys.) Keys are usually generated on the users workstation, so if any of your users is or was potentially running Debian or Ubuntu ... you get the idea.

Note that if you are not careful, you might lock yourself out from your server. If you don't have or remember the password, installing the security update might disable your login key. So if your key is bad, make sure to generate a new, secure key and distribute it ASAP. Also remove any vulnerable key ASAP; remember that hackers now have a list of all possible keys and could use that to brute-force login.

P.S. Since some people still don't seem to get the consequences in full: The bigger problem is to remove are the weak keys, not to fix the broken library. The weak keys (especially in the form of public keys!) can live on tons of other systems, not just on Debian and Ubuntu. This is why TOR also released a security update and e.g. CACert urges non-Debian distributors to also ship and use the blacklists of known weak keys. Also note that not all keys that can be considered compromised can be detected this easily. If you've been using a DSA key on an affected system - even when it was created on a different system - it is to be considered compromised.