Debian or Ubuntu users, regenerate those crypto keys now!

Well normally I don't blog about matters that are well published but this is a quite serious one.
A Debian packager modified the source used for OpenSSL on Debian based systems (Debian and the whole of the Ubuntu family) to remove the seed used for Pseudo Random Number Generator used when creating SSL keys. Just to solve some compile errors without realizing the impact. So it used the PID of the process as a seed for generating the old keys, which severely limits the randomness of the keys.
On the Linux platform, the default maximum process ID is 32,768, resulting in a very small number of seed values. So this has made it possible for a rainbow table of all possible keys to be generated. Consider all keys generated between September 2006 and May 13th, 2008 as potentially weak.
The Debian project guys released a tool that can detect weak keys (it is not 100% correct though as the blacklist in the tool can be incomplete). You can download the tool from http://security.debian.org/project/extra/dowkd/dowkd.pl.gz.

And HD Moore from Metasploit has just released Debian-OpenSSL Toys to exploit the vulnerability. He also published all SSH 1024, 2048 and 4096-bit RSA keys which he brute forced.

So if you use keys for authentication, be warned. Webcertificates coming from the Debian SSL packages OpenSSL 0.9.8c-1 up to 0.9.8g-9 also need to be regenerated and resigned by the CA.

UPDATE: Debian Wiki has a good (and evolving) write-up on problems and resolutions: wiki.debian.org/SSLkeys