Hacker News Reader

Comment by lordnacho | Hacker News Reader

I've run into the same issue.

One of the main frustrations is you don't know if the output is correct until you manage to reproduce some known key/document exactly.

When you're debugging anything else, you can sort of see what's wrong as you come closer to a correct solution. A crypto scheme is only correct (you've put the right things in the right places) when it's exactly right. Until then, you have a jumble of characters.

It took me ages to match ECDSA on java with Python. In the end, it was because of some fine print where I needed to hash one version but not the other before signing.

View on HN

It's even worse than that, unfortunately :-( You can absolutely get the correct answer for a bunch of test cases and _still_ get insecure crypto; for example: small subgroup attacks on FFDH with p-1 smooth, small subgroup/off-curve attacks in ECDH, static/predictable k for ECDSA, MtE/M&e instead of EtM... Lots of passing unit tests, no good crypto.

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.

Reply on news.ycombinator.com