Attacks on ECDSA Signatures With Single-Bit Nonce Bias [pdf]
irisa.fr
irisa.fr
Every DSA signature requires a random nonce/key k. If k is predictable, DSA falls apart. We demonstrate that here:
http://cryptopals.com/sets/6/challenges/43/
The same problem occurs in elliptic curve DSA, which is just the DSA construction implemented on the elliptic curve discrete log.
What's also true is that if part of the nonce is predictable (or leaked), DSA falls apart --- albeit over more than just a couple signatures. With tens of bits leaked, you might needs hundreds of thousands of signatures.
How would you ever leak part of a nonce over thousands of signatures? One easy way is to generate a nonce that appears cryptographically random, but doesn't fill the modulus. For instance: a 128 bit random number sure seems strong, but if it's filling a cryptographic parameter that's meant to be 256 bits long, fully 128 bits of that parameter are predictably zero.
Here, though, you have a predictable nonce bit leak that can occur purely by accident even given a reasonably sound implementation!
Are you accepting contributions for any of the solutions? I'd be happy to try and contribute some in Golang.
As part of the challenges can be solved using Java's security API it gave me valuable insight into these libraries.
What's slowing us this time is that I left Matasano in October.
It doesn't help that every time this discussion comes up, I get email asking us not to post the solutions. :)
So RFC 6979 is fine, but k=HMAC-SHA-256(x,m) is not a secure choice for 256-bit elliptic curves over random base fields.
Complaining to the implementers has just resulted in <whine>thats more complicated, mod is fine</white> And, indeed, for secp256k1 the differences is 1 part in 10^38, so its not likely of practical importance; unless you can assume an attack that can extract an _awful_ lot of signatures from you.
I expect the same behaviours are common for different parameters where it's not such a small bias.
But careful approaches like RFC 6979 are very important for curves over random fields, like the Brainpool parameters.
[By the way, a more regular contributor of this site suggested that it would be appropriate for me to mention that I'm one of the authors of the OP.]
BTW, you might want to add "[pdf]" to the title. It seems the automated pdf detection and title editing missed this submission for some reason, so I reported it to hn@ycombinator.
A Schnorr-style signature with a deterministic nonce, like djb's EdDSA/Ed25519, is probably a better way to go these days, since the patents expired...!
(1) Shows attacks on ECDSA where there is a one bit of bias on the nonce. These should work equally well on Schnorr signatures of their various forms, including EdDSA (though EdDSA proscribes a particular nonce generation scheme which should hopefully not result in observable biases, other standards proscribe similar schemes for ECDSA users, e.g. RFC6967). If it turns out that the hash functions used for deterministic dsa in these systems are biased, this attack crops back up.
(It's not news that biased RNGs can result in these attacks; the interesting part is that they were able to actually perform an attack on a non-toy curve, with only a one bit bias. Past attacks were mostly theory, and also needed more bias.)
(2) Some unusual curves can have an optimization which common implementations might take which results in biased nonces. These curves are not widely used on the Internet. I'm doubtful you've ever heard of them (except Bitcoin's curve, which is a GLV curve, but I'm relatively confident _no one_ is using the endomorphism in signing). They also give advice on avoiding that weakness.
(3) One way of avoiding the weakness while still using the optimization is to decompose a uniform number instead of using two random numbers, they show an argument for a power attack against a candidate constant time decomposition algorithm. Again, moot if you're not using the optimization.