A year ago, I wrote about the Debian OpenSSL PRNG bug that reduced the entropy of its random seed to 15 bits. There was a little-noticed part of the advisory that said all DSA keys used on the affected systems should be considered compromised. 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.
DSA is a public-key signature algorithm. Unlike RSA, it isn’t useful for encryption or key exchange. Like other public key algorithms, it is extremely sensitive to the choice of parameters. I’ve written about RSA signature flaws (1, 2, 3) that resulted from too much ambiguity in how a signature verify operation was interpreted.
With DSA, the entropy of the random signature value k is critical. It is so critical that knowledge of only a few bits of k can reveal your entire private key to an attacker. Interestingly enough, the Wikipedia article on DSA doesn’t mention this concern. This is why it’s so important to get your crypto reviewed by an expert. Small, obscure flaws can cause immense damage.
To generate a DSA signature, the signer calculates (r, s) as follows:
r = gk mod p mod q
s = k-1 (H(m) + x*r) mod q
The message to be signed is m, H(m) is the SHA hash function, and p and q are primes. The value k is a random nonce and x is the signer’s private key. If an attacker knows k and has a single signature (r, s), he can recover the signer’s private key with a simple calculation. In the case of the vulnerable PRNG, he can just repeat this process for all 32,767 possible values. Remember that the message m is not secret, so neither is the SHA-1 hash H(m). The attacker calculates x as follows:
x = ((s * k) – H(m)) * r-1 mod q
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.
I hope a year has been enough time for people to revoke their DSA keys, even though the warning was somewhat obscure. Thanks to Peter Pearson for interesting discussions about this issue.
rdist 
“knowledge of only a few bits of k can reveal your entire private key to an attacker”
You’ve lost me on this. Knowing the full value of k of course allows recovering the private key very easily (I used it to attack GNU Classpath’s DSA implementation last winter), but if knowing only a few bits of k (let’s say, 8 bits) for a particular signature allowed recovery of the private key, it would be trivial to convert this to a slightly less efficient attack on any DSA signature: just guess the 8 bits, attempt the attack, and if it doesn’t work make another guess.
If you knew many but not all bits of k, say, 120 bits, leaving 40 bits unknown, that would of course allow feasible brute force of the remaining k space.
I could believe there is a number theory trick of some kind that allows recovering the private key with only partial/inperfect knowledge of k, but I have never seen or heard of it. If you are aware of such a trick, you should definitely explain or reference it!
Jack, you’re right that knowing only a few bits of k and a single signature is not enough to recover the private key. However, with multiple signatures and partial knowledge of k, you can attack it.
This is a very clever attack that I plan to write up soon. It was originated by Boneh and Venkatesan, improved most recently by Nguyen and Shparlinski. The paper is a bit dense, but I’m hoping to come up with a clearer explanation.
The lesson is that in crypto, any partial knowledge you give an attacker can possibly result in a complete compromise. It is extremely fragile.
Thanks! I had completely missed this paper as well as the earlier work by Boneh that they cite. I don’t know much about lattice theory so it will probably take me a while to work through the whole paper, but their experimental result of recovering the full key from the lowest 3 bits of k for 100 messages is definitely impressive.