4 ms·
Tell me more? I was doing some bitcoin calculations and needed it.
by lordnacho 10y ago
Tell me more?
I was doing some bitcoin calculations and needed it.
- tptacek 10y agoIf 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.
- wolf550e 10y agoDo you believe CFRG took so long to standardize EdDSA because of natural bikeshedding, or because the NSA worked to slow them down?
- tptacek 10y agoIt'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.
- deleted 10y ago[deleted]
- YAYERKA 10y agolordnacho, 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.
- tptacek 10y agoThe 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.
- YAYERKA 10y agoI 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.