When news broke last year about the serious flaw in the Debian OpenSSL pseudorandom number generator, security experts knew it was a serious problem and warned users to regenerate any keys that had been created using the vulnerable versions of the OpenSSL package. It was a big problem, but it turns out that it could have been far worse.
Nate Lawson, an expert on cryptography, today described in detail why the situation could have turned out much differently: Not only was every key that had been generated by the vulnerable versions compromised, so was every key used on systems running those vulnerable versions of Debian.
In the rush to find and replace SSL certs and SSH keys generated on Debian or Ubuntu systems, very few people grasped the significance of this other warning. This is important because an attacker can retroactively seek out DSA signatures generated during the vulnerable period and use them to recover your private key…
The impact of this attack is that every signature generated on a vulnerable system reveals the signer’s private key. An attacker can find old signatures by crawling your website, examining signed email, analyzing saved packet captures of an SSL exchange, etc. The associated DSA key has to be revoked, regenerated and redistributed. Luckily for Debian, their packages are signed using GnuPG, which did not use the OpenSSL PRNG. But for anyone using other software based on OpenSSL, you need to revoke all DSA keys used to sign data on vulnerable Debian or Ubuntu systems. Even if the key was generated securely, a single insecure signature reveals the entire private key. It’s that bad.
Debian pointed out this fact in its original advisory on the OpenSSL PRNG problem, but, as Lawson said, it was not widely reported. And, given that attackers could conceivably still go back and find old signatures, it’s worth ensuring that any key used or generated during that period has been discarded and regenerated.
Problems with cryptographic algorithms or packages like OpenSSL sometimes are dismissed as being too difficult to exploit. But that was clearly not the case with the Debian vulnerability. Within days of the announcement of the vulnerability, HD Moore of the Metasploit Project had posted a list of compromised keys that he was able to brute force.
And, not only did this vulnerability affect OpenSSL keys, it also affected digital certificates. It was a widespread problem stemming from a small error in one part of a Linux distribution. For an excellent analysis of the problem, see Michael Cobb’s column.