So anyone new jumping on this would have to race the one or more existing exploiters.
Most of the time this property is useless, because you want to verify the signature against a known-good key, but it does also mean you're probably not going to want to use DSA to pass signed covert messages.
Schnorr signatures actually have a simpler, and I think more intuitive, construction and don't have this property. They also don't require collision resistant hashes.
def verify(msg,sig,addr): return pubkey_to_address(ecdsa_recover(msg,sig)) == addr
https://docs.google.com/spreadsheet/ccc?key=0AscYGzcM4zJNdHR...
I've probably missed a few tweets and typo'd a few numbers along the way, but it should be mostly accurate. Note the tabs (at bottom left) for a derived speadsheet (percent of participants at each level) and a chart.
I don't know what I'll do for set 7 yet. Maybe Excel implementations of the SHA-3 finalists...
(seriously, downvoted for asking about stats on cryptopals? it is relevant -- #6 has two DSA questions!)
63 people have finished the crypto challenges; about 9000 people have started them.
I don't know the Bitcoin software involved at all, but I can sketch out an attack that might shed some light on it, and, more importantly, instill an appropriate fear of DSA into you:
To generate a DSA key, you come up with primes p and q and a generator g, which process is a paralytic non-Euclidian brain injury I will not attempt to describe. Then you do like Diffie Hellman: generate a random private key x and from it a public value y = g^x % p. The pubkey that validates signatures is the tuple (p, q, g, y).
To sign, you generate a random k value, which must never be reused, Iä! Iä! never, and:
The signature is (r, s).If ever you should fail to heed these words and generate two signatures with the same k value, Iä Cthulhu Ftaghn! then simple high school algebra can be used to beat DSA. The attacker doesn't even need to know what the k was, and the attack is so fast you can just try it to see if k was repeated (I skipped the algebra and just dumped the formulas for the attack here):
This bug (also in an ECDSA implementation) is what broke the Playstation 3, too.You see that comment on the Bitcoin thread about the repeated r-values; a repeated r-value (r as in the r parameter of a DSA signature) just tells you that someone repeated a k. Iä! Iä!