The ructions of the recent Debian OpenSSH/SSL failure are likely to be with us for some time. It's probably one of the most serious security failures in Debian's history. I'm still waiting for Bruce Schneir's reaction, I'll assume there will be one.
There have been security problems with OpenSSH and related tools before (and there will be in the future, the only secure computer is turned off, not plugged into the net and locked in a box with armed guards around it). While some have been a cause of concern others have mostly been theoretical weaknesses when the attacker has had an unusual amount of access. Still when the vulnerability is discovered and the updates provided you read the vulnerability, update you servers and move on. The problem with the current problem is it doesn't affect just by Debian based servers, potentially the problem is much wider as any machine you logged into from a Debian machine may have a compromised key on it.
This particular security issue is a key space vulnerability. Cryptography relies in part on very large numbers that are computationally expensive to transform and therefor hard to brute force a result by going through every possible number. Attacks on cryptography itself (rather than the programs that do it) usually involve very brainy mathematicians testing the assumptions of the authors and trying to reduce the number of possible keys there may be, or finding shortcuts to reduce the number of calculations required to eliminate potential candidate keys.
Assuming your algorithm is secure and the number of possible cryptography keys stays high you look to see if the user is somehow limiting the number of keys he has selected from. This is where the importance of randomness is so key. It's actually very hard to generate real random numbers on a computer as they are by their logical nature very predictable things. Most modern computers add to their entropy pools when external events happen but care had to be taken. For example some timing attacks are based on the fact people type in certain patterns for certain keys. None of this mattered in this case as the "randomness" of the key generation was reduced to being based on one value, the process id of the key generation program. This is simply a number between 1 and 32,768 (and most likely in the low few thousands) and basically makes it trivially easy to generate every key that a comprised Debian system would have ever generated.
For every Debian based (and it's derivatives like Ubuntu) machine you are responsible for
- Login and update the Open SSH and OpenSSL software
- Ensure the host keys and SSL certificates are updated
- Scan the machine for all key files (.ssh/id.*) and delete them (you may want to save a secure copy somewhere in case your users have only their key to log into some machine, but fundamentally those keys are broken).
- Audit all the authorized_keys files (.ssh/authorized_keys) files. Delete them (maybe keeping a saved copy). Users will need to copy new keys onto the machine to use key based authentication
- Audit all the known_hosts files (.ssh/known_hosts). Each one of these machines may have a comprised key installed by your user. If you are responsible for any of these machines make note of it to fix
- If you are especially paranoid reset all user passwords and get them to go through the normal reset channels to get them back
- Delete your keys and regenerate a fresh set for you machines
UPDATE: I see xkcd is on the case.