Hacker News new | past | comments | ask | show | jobs | submit login

What's especially unfortunate about this is that experts would caution you against using ECDSA at all.



Tell me more?

I was doing some bitcoin calculations and needed it.


If you have to use ECDSA you have to use it. Bitcoin is an example of where you have to use it.

Otherwise, though, it's an inferior and outmoded signature system. It's got the worst random nonce dependency of any modern crypto primitive: if it's even biased, just a little bit, you can recover keys from groups of signatures (a full repeat instantaneously destroys security with a single pair of signatures). It's weak against simultaneous attacks on multiple signatures, so it minimizes the effort attackers need to spend. Meanwhile, it's inefficient compared to the alternatives, so it tends to maximize the effort you have to spend. It's also hard to implement without side channels.

Modern cryptography engineers would recommend something like EdDSA instead.


Do you believe CFRG took so long to standardize EdDSA because of natural bikeshedding, or because the NSA worked to slow them down?


It's obviously bikeshedding.

People have been misconstruing the bikeshedding and cliquishness of the IETF as enemy action for decades.

John Gilmore has a story about how, during IPSEC standardization, someone was pushing for a CBC chained-IV construction hard, and that he was both confident it could only be enemy action and had sources suggesting it was. This came out right after the Snowden leaks, so everyone took it seriously.

But if you look at it context, I'm pretty sure the people he was talking about were Perry Metzger and Bill Simpson† (both clearly not NSA plants). They were arguing with Phil Rogaway --- calling one of the most famous and prolific cryptographers a "so-called" cryptographer when he cautioned them not to do dumb things like chaining IVs.

There's a message thread you can look up on the Internet where this happened. Rogaway even got a petition put together from a bunch of other cryptographers, including Rivest. No luck! The IPSEC standards committee ignored them.

A decade or so later (earlier, really, but nobody took Bard's paper seriously) we discovered chained CBC IVs lead to the BEAST attack on TLS.

Enemy action? No. Crypto standards groups don't need enemy action. They are intrinsically evil, and need to be avoided.

I think this is the case, but I haven't confirmed it with Gilmore; maybe he's talking about a different controversy during IPSEC standardization. But these are the ones where the details fit from what I can tell.


lordnacho, as tptacek wrote below (which also applies to DSA);

>a full repeat instantaneously destroys security with a single pair of signatures

Roughly--assuming ECDSA parameters (H,K,E,q,G)--where H is a hash function, E the Elliptic Curve over finite field K w/ point G of prime order q. Suppose two different messages m and m' have been signed with private key x using the same (non-ephemeral) random nonce value of k.

According to ECDSA Signing these messages m, m' become signatures (r,s), and (r',s') where;

  r = r' = kG,

  s = (H(m) + x*r)/k   mod q,

  s' = (H(m') + x*r)/k  mod q.
Observe that,

  (H(m) + x*r)/s = k = (H(m') + x*r)/s'  mod q.
Or,

  x*r(s' - s) = s*H(m') - s'*H(m)  mod q.
Which allows us to recover the private key x.

Since,

  x = s*H(m') - s'*H(m) / r*(s' - s)  mod q.


The problem is really much worse than this. You don't merely need a non-repeating nonce (the way you can get away with a GCM nonce that increments by 1 every session): you need an unbiased nonce.


I believe an natural segue here is to remind people about cryptopals (especially set 8). Ie., I don't have the chops and wouldn't attempt to writeup EC/DSA nonce bias and partial key exposure attacks better than you all--not to mention the challenges regarding GCM. Cheers.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: