Iä! Digital Signature Algorithm! The Black Goat of the Woods with a Thousand Crypto Bugs!
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:
r = g^k % p % q
s = k^-1 (H(m) + x•r) % q
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):
H(m1) - H(m2)
k = -------------
S1 - S2
x = ((S1•k) – H(m1))• r^-1 % q
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ä!
For folks wondering -- why yes, you can scan the entire blockchain for repeated k values. It's about O(n^2) for an N so small as to be effectively constant (n = outgoing transactions per address), and will be dominated by the time it takes you to actually download the blockchain.
...which appears to be how the problem was brought to public attention. Someone was draining balances held by keys so compromised, within a few hours after the repeated 'random' value.
So anyone new jumping on this would have to race the one or more existing exploiters.
Lest we think everything's lost, Thomas Pornin's RFC to fix (EC)DSA's need for good randomness when signing was published this month [1]. The approach is similar to Dan Bernstein et al's EdDSA.
[1] http://tools.ietf.org/html/rfc6979
Another interesting thing about DSA is that the signatures allow for public key recovery i.e. given a signed message, you can (usually within 1 or 2 possibilities) determine the public key of the signer. It's a bit like a handwritten signature where everybody can read your name amongst the scrawl.
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.
Actually, the key-recovery process is quite useful. The reason is that instead of having your public key be the public key itself, you can use the hash of your public key (ie. Bitcoin address) instead. This cuts the required "public key" length in half for the same level of security. The verification protocol then becomes
def verify(msg,sig,addr): return pubkey_to_address(ecdsa_recover(msg,sig)) == addr
See also: https://github.com/vbuterin/pybitcointools
Yes, Bitcoin is one exception because of the digested addresses, but if I'm up to date it's not currently used on the network. There's no opcode in the transaction script to perform recovery, so currently you can't reduce transaction size by omitting public keys. I suppose the primary advantage in Bitcoin is the reduced storage space.
It's not currently used on the blockchain, but there's a feature in the Bitcoin client that uses public key recovery in order to sign out-of-band messages with Bitcoin addresses.
Well then...first I learned something about DSA, and now I'm 1/3 of the way through re-reading The Black Goat of the Woods with a Thousand Young. Jesus Christ I am a nerd. Iä! Iä!
On a side note, what are the current stats for the Matasano crypto challenge? How many have finished all 6?
On a side note to my side, how many are psyched about Breaking Bad tonight?!
(seriously, downvoted for asking about stats on cryptopals? it is relevant -- #6 has two DSA questions!)
I'm a season behind on Breaking Bad; I don't like watching half-seasons and would rather just watch the whole thing once it's all on Netflix. So: not too excited.
63 people have finished the crypto challenges; about 9000 people have started them.
Whenever I see tptacek tweet the current stats, I try to update this spreadsheet:
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.
For those watching from the stands, 'rwg also sent us a spreadsheet that does AES. Entirely in cell formulas. He also sent us a Postscript file that appeared to be a visualization of AES state but was in fact a pure-Postscript implementation of AES that rendered itself into the Postscript document.
To be fair, I've only tweeted screenshots of the AES spreadsheet -- you'll be getting the actual .xlsx file with my set 6 answers. AES128.applescript is waiting in the responses@ and cryptopals@ mailboxes right now, along with my set 5 answers.
I don't know what I'll do for set 7 yet. Maybe Excel implementations of the SHA-3 finalists...