Others have written all about the recent Debian OpenSSL security vulnerability; I have nothing intelligent to add about who did what or who should have done what or did not, so I'll refrain.
However, I noticed that several sources mention that DSA is trivial to break
given access to a signature made by a bad randomness generator. For instance,
Applied Cryptography (Schneier) says (thanks to Peter Palfrader for digging
up the quote): Each signature requires a new value
of k, and that value most be chosen randomly. If Eve ever recovers a k that
Alice used to sign a message, perhaps by exploiting some properties of the
random number generator that generated k, she can recover Alice's private key,
x. If Ever ever gets two messages signed using the same k, even if she doesn't
know what it is, she can recover x. And with x, Eve can generate undetectable
forgeries of Alice's signature. In any implementation
of the DSA a good random-number generateor is essential to the system's security.
I couldn't find out exactly how, though, so I decided to work it out myself -- it is indeed pretty easy. You don't require much maths either -- although DSA can in principle work over any commutative ring (look Ma, I know fancy algebra words! =) ), simple modular arithmetic is what's usually used, and it's also the easiest to understand.
DSA has a public key consisting of the integers (p, q, g), and a private key consisting of another integer (x). (There are some limitations on them apart from that they are integers, of course, but that's not so important for the algorithm.) The DSA signature of a message m (having the hash value H(m)) consists of two integers r and s, calculated as follows:
r = (gk mod p) mod q
s = (k-1 (H(m) + xr)) mod q
where k is the infamous secret random integer (0 < k < q). (k-1 is the multiplicative inverse of k -- you can think of it as roughly equivalent to 1/k over the real numbers. (I'm deliberately being sloppy with the terminology here :-) ))
Attack 1: If you can guess k, you can also find the secret key x. It's actually quite trivial; take s, multiplied by k:
sk mod q = (H(m) + xr) mod q
subtract H(m):
(sk - H(m)) mod q = xr mod q
multiply by r-1:
((sk - H(m)r-1) mod q = x
and voila. (x is between 0 and q, so we can drop the mod on the right-hand side.)
Attack 2: If you have two messages (let's call them m1 and m2) encoded with the same k, you can also find the secret key x. The trick is to first realize that r in the two messages will be the same (it depends only on g, k, p and q, and all but k are part of the public key), so what you essentially have is:
s1 = (k-1 (H(m1) + xr)) mod q
s2 = (k-1 (H(m2) + xr)) mod q
Now subtract the second equation from the first and the fixed xr term vanishes:
s1 - s2 = (k-1 (H(m1) - H(m2)) mod q
Now finally multiply by (H(m1) - H(m2))-1:
(s1 - s2)(H(m1) - H(m2))-1 = k-1 mod q
and you have the used k, which can be used in attack 1 above.
No MathML was harmed during the making of this blog entry. Does anyone have a TeX plugin for pyblosxom, please?