Update: Debian has a good summary page on their wiki.
This is pretty serious – a packaging stuff-up for OpenSSL by Debian (and hence Ubuntu) has resulted in not-very-random randomness being used in various packages such as OpenSSH for key generation. The Ubuntu report says:
A weakness has been discovered in the random number generator used by OpenSSL on Debian and Ubuntu systems. As a result of this weakness, certain encryption keys are much more common than they should be, such that an attacker could guess the key through a brute-force attack given minimal knowledge of the system. This particularly affects the use of encryption keys in OpenSSH, OpenVPN and SSL certificates.
This is a Bad Thing(tm), Debian have told their own developers:
Since the nature of the crypto used in ssh cannot ensure confidentiality if either side uses weak random numbers we have also randomized all user passwords in LDAP.
It’s also been around for almost 2 years now according to the Debian security notice:
The first vulnerable version, 0.9.8c-1, was uploaded to the unstable distribution on 2006-09-17, and has since propagated to the testing and current stable (etch) distributions. The old stable distribution (sarge) is not affected.
So now would be a good time to change your passwords, unless you can be certain you’ve never logged into a Debian or Debian derived system..