Most public key systems fail catastrophically if you ignore any of their requirements. You can decrypt RSA messages if the padding is not random, for example. With DSA, many implementation mistakes expose the signer’s private key.
Many crypto protocols use a nonce. The traditional requirements of a nonce is that it never be repeated. So a simple counter can suffice, as long as it is safely persisted. Using a timestamp is problematic if the clock ever goes backwards (say, NTP) or you need to generate two messages in a short interval.
In DSA, the k value is not a nonce. In addition to being unique, the value must be unpredictable and secret. This makes it more like a random session key than a nonce. When an implementer gets this wrong, they expose the private key, often with only one or two signatures.
If k is predictable, there is a way to recover the private key from a single signature with straightforward algebra. Since a past weakness in the Debian PRNG resulted in only 32767 possible outputs, an attacker could recover any DSA private key where a single signature was generated on a vulnerable Debian system. The key could have been generated securely on a system without this flaw, but that single signature would compromise it.
But what about the requirement that k be unique? Assume there’s an email signing system that has a secure PRNG but it is rate-limited so two requests that come in quickly from the same process produce the same output. As an attacker, you can’t predict k but you suspect the signing system may have this weakness.
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
If you see a repeated r value, then you know k has been repeated. Build a web crawler to find DSA signatures. Dump its output into a parser for a bunch of formats (X509v3, PGP, PKCS#7, etc.) From each signature file, insert each r value into a key-value database and look for a match. If you find any two matching r values, you can recover the signer’s private key.
The algebra to do so is pretty straightforward. Given two signatures for messages MA and MB, we want to solve for k.
SA = k-1 (H(MA) + x*r) mod q
SB = k-1 (H(MB) + x*r) mod q
Subtract the two signatures. (The modular reduction step is implicit from here on for readability.)
SA – SB = k-1 (HA + x*r) – k-1 (HB + x*r)
Redistribute. Since the k’s are identical, their inverse is also.
SA – SB = k-1 (HA + x*r – HB – x*r)
The x*r values cancel out.
SA – SB = k-1 (HA – HB)
Redistribute.
k = (HA – HB) / (SA – SB)
Once you have k, you can solve for x directly as in the previous post. There is a more complicated technique for solving for x if only a few bits of k are known, requiring more signatures.
It is extremely important that all bits of k be unique, unpredictable, and secret. With two DSA signatures on separate messages with the same k, you can recover the signer’s private key.