Debian and Ubuntu Linux users should look into their OpenSSH setup. It turns out the PRNG (Pseudo Random Number Generator) as used was predictable.

Remember patching isn't enough, you need to regenerate keys generated on these machines! Including those used in SSL certificates (X.509).

Worse: even good keys apparently can be exposed due to this. Quoting from the Debian reference below:

"Furthermore, all DSA keys ever used on affected Debian systems for signing or authentication purposes should be considered compromised; the Digital Signature Algorithm relies on a secret random value used during signature generation."

So merely using your (good) keys on an affected machine might be enough to get the key itself compromised.

• CVE-2008-0166
• Ubuntu: USN-612-1
• Debian: DSA-1571-1

Interested in what makes the PRNG be predictable I started reading the changelog and found this:

* Re-introducing seeding of the random number generator.  Patch from the
   maintainer.

-- Florian Weimer <fw@deneb.enyo.de>  Thu, 08 May 2008 01:58:40 +0200

Guess that sums it up ...

Update: Alex dug deeper and found it might have been triggered by a tool to find use of uninitialized memory (valgrind) and bug report 363516

Update: Florian provided a link to a tool to detect these weak keys

--
Swa Frantzen -- Gorilla Security