Attacks on ECDSA Signatures With Single-Bit Nonce Bias [pdf]

http://www.irisa.fr/celtique/zapalowicz/papers/asiacrypt2014.pdf

by bgentry • 12 years ago

43 14 12 years ago

irisa.fr

tptacek2• 12 years ago

So great.

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!

bgentry2• 12 years ago

I hadn't seen the new cryptopals website for the Matasano Crypto Challenges. Looks very promising, and I'll probably be giving it a run very soon :)

Are you accepting contributions for any of the solutions? I'd be happy to try and contribute some in Golang.

chopin• 12 years ago

I'd be happy to add contributions as well for Java. I hadn't the time for all challenges yet, but those I have done, I'd be willing to contribute.

As part of the challenges can be solved using Java's security API it gave me valuable insight into these libraries.

tptacek2• 12 years ago

We will get to them, these 5 words I swear to you, &c &c.

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. :)

__alexs• 12 years ago

Is this still a major problem for (EC)DSA? I thought it was generally agreed that deterministic nonces (e.g. RFC 6979) were the way to go these days?

mti2• 12 years ago

Deterministic nonces are a good idea, but they don't necessarily prevent biases. Generally speaking, for (EC)DSA/Schnorr in a group of cardinality n, using a nonce of the form k=F_x(m) (where m is the message and x the public key) is safe if F is chosen as a Z/nZ-valued PRF; but if you use a PRF with values in bitstrings of the same length as n, the attack in the paper does apply.

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.

jcr• 12 years ago

I know I'm probably going to only understand some tiny fraction of what I read in this paper, but I'm sure going to have fun trying.

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.

bgentry2• 12 years ago

Oops, that was my fault, I accidentally deleted the [pdf] when I edited the title to better reflect the paper's title.

higherpurpose• 12 years ago

Time to switch to EdDSA?

nullc2• 12 years ago

The paper has basically three parts.

(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.

AlyssaRowan• 12 years ago

Neat! I only saw it done with 2-3 variable predictable leading bits before.

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...!

Attacks on ECDSA Signatures With Single-Bit Nonce Bias [pdf]

Related Stories