Minerva: Practically exploitable side-channel leakage in ECDSA implementations

I've repeatedly acknowledged the existence of USG surveillance programs, including Dual-EC. I believe the "hours" I've spent discussing Dual-EC and PKRNGs in general are also straightforwardly countable; just use the search box:

https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

What you're doing here is deceptively reframing a subtle nerd technical argument as a normative argument about USG surveillance. In particular: at no point have you or anyone else ever witnessed me arguing that Dual-EC was okay; rather, my argument was that Dual-EC was so batshit, and such poor tradecraft, that it was unlikely to be a serious NSA program. My argument at the time mirrored that of Bruce Schneier: "never use this, no competent engineer would". My twin mistakes: I overestimated both NSA and the industry, in particular vendors like Juniper, which did in fact implement this standard.

What's even dumber about this comment is that you're making it in support of an argument virtually nobody in the field supports, which is that the NIST P-curves are somehow "backdoored". As you know, or at least should know before talking about this stuff, there is virtually no relationship between the P-curves and Dual-EC. But you're happy to exploit the general lack of understanding about the distinction to score points on HN, even if means dumbing the whole thread down.

To head off some other comment you'll write 6 months from now without me noticing: you can easily peruse the site history and see me consistently arguing against use of the P-curves (in fact, I cite the P-curves is a damning failure of DNSSEC, which you'll no doubt find some fig leaf some years from now to claim I also support). But not because the curves are "backdoored"; rather, because modern curves are misuse-resistant.

https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

Since I'm assuming you have at least the ability to Google, I'm expecting you to cite Bernstein's analyses of the flexibility NSA's generation process provided for hunting for vulnerable curves. To see that outré claim rebutted, here's another Google search for you: [koblitz menezes enigma curve]. Happy to help.

Meanwhile, your message betrays no evidence of understanding what misuse-resistance in curves means, though you've been happy to preen about cofactors and Schnorr signatures on other threads; you depict the choice between 25519 and P-384 as one between a "suspicious generation mechanism' and an "immature" alternative. Of course, that's not why serious designs use 25519; rather, it's because 25519 is less susceptible to curve point validation vulnerabilities and is designed to be straightforwardly implemented without side channels.

Your comment is one of the most gratuitously uncivil and mean-spirited things I've had directed at me on this site, and I have been the target of a lot of mean-spirited bullshit here.

That isn't something that I wanted, but at the same time, I earnestly believe you've harmed the world with your positions-- which have, in my view, consistently and inexplicitly apologized for both suspicious and unethical conduct from the US government. Not just in your commentary about backdoor risks, but also in your commentary about Snowden, Manning, and Wikileaks.

I suppose I lack the communications chops required to be crisp and clear in that disapproval without it coming across as mean. For whatever it's worth, I earnestly don't think you are a bad person, but I do think that you've found yourself stuck behaving consistently with years of mistaken positions (perhaps some of which your income depended on?... gross speculation on my part, I admit). In any case, I am happy to extend you the benefit of doubt to believe you're at worst just mistaken, I hope you can find it in your heart to do the same for me.

If no one close to you that you trust has said similar things to you about your positions on HN then I think people must be afraid to be frank to you. I've had people who worked for you apologize to me for your conduct on HN when I heard where they worked and responded with a "whats with the government apologia?". And not with a surprised apology but rather a 'sorry, I know, I have heard this 100 times before' sort of tone.

Maybe it's ultimately unfair, but at least w/ some people you've managed to pick up that reputation.

> My twin mistakes: I overestimated both NSA and the industry, in particular vendors

But it isn't the case that vendors merely implemented it-- consider the absolutely astronomical payoff we know that was required for RSA: a company at least on paper full of cryptographic experts-- to implement it.

This wasn't hapless implementers making dumb choices, this was the government standardizing a backdoor then paying people quietly ship it. ( https://www.reuters.com/article/us-usa-security-rsa/exclusiv... ) Doubly so when you consider that until they expired in 2000 RSA patents were used to force people to use the bsafe library.

I'm not quite sure what part of my message really conflates dual-ec and curve selection beyond this one point: I hope we can agree what DualEC provides virtually irrefutable proof that the US government is willing to promulgate backdoored standards.

The only connection to the curve selection is that there are, in fact, degrees of freedom which I believe reasonable people can hold present an actual (if small) risk. I had seen the "Enigma" paper, but I found it fairly unconvincing especially since it patronizes the reader with an argument that the NSA wouldn't select an insecure system, I say patronizes because the track record with DualEC is an extremely a strong counterargument to that position. (You could argue that DualEC is trapdoored to a designated mallory, but Juniper's experience shows that it isn't even that simple!).

It's also relatively straight-forward that if we 'forget' some of the things we have long know about choosing secure curves that is isn't hard to grind a NIST like procedure to choose an actually insecure curve. Consider: if, absent knowing about insecure forms we were cryptographically-unlikely to encounter one, why would the NIST generation procedure include security tests in the inner loop?

For me, it comes down to the simple argument that we can select curves rigidly where there is little avenue to grind in any hidden properties. ... and there are curves from a source known to have released backdoored parameters. It's a needless risk to choose unrigid parameters at all, but especially foolish to take them from source with a prior history of abuse.

To be completely clear: I think the black box generation is not a very great risk, but it is so absurdly needless and without any articulate benefit that we would be wise to avoid it.

The decision framework implicit in my positions on this sort of thing is to imagine yourself in the future and assume that things have gone wrong. Do you feel stupid about your decisions or do you feel you made the best choices given what you could work with at the time?

Use of less than strongly rigid parameters doesn't play especially well in this sort of analysis.

> your message betrays no evidence of understanding what misuse-resistance in curves means, though you've been happy to preen about cofactors and Schnorr signatures on other threads; you depict the choice between 25519 and P-384 as one between a "suspicious generation mechanism' and an "immature" alternative.

Er, you've misread my message. I think ed25519 is mature and generally a reasonable choice, but it violates the rather strong NSA recommendation for 384-bit+... which is unfortunate. This means that someone cannot concurrently get the benefits of it without violating a recommendation that anyone should feel pretty stupid to violate (unless that person considers the NSA to be completely discredited).

The comparison I was attemping to make is _ed448_, which is equally "misuse resistant", but implementations are far far far less mature. (Perhaps to the point of such obscurity that it caused you to misread my message as recommending P384 which I would not generally recommend, but it is what the NSA would recommend).

And yes, I do also think that the 25519 misuse resistance arguments are somewhat overstated and not supported by rigorous science. The misuses it avoids are uncommon and tend to co-occure with other grievous stupidity that it doesn't prevent, and when implementations have them they tend to also have them for 25519 (the recent HN thread on java ECC implementation being a reasonable example!). The belief that ed25519 doesn't need e.g. point validation has itself resulted in stupid vulnerabilities.

_But I think this is a nitpicky point because even if the benefits are overstated they're still benefits_, and it certainly wasn't a reason to not use ed25519 I was referencing in my message. And I've frequently recommended curve25519/ed25519 in places where plain ECDH or digital signatures are required.

For other cryptographic protocols I can't recommend ed25519 due the cofactor, which has resulted in total breaks in real systems (and not 'merely' side-channels, which are only serious in a subset of applications). From my own experience designing zero-knowledge protocols it is simply a lot harder to deal with cofactor than with non-unified addition law, and it results in much more serious breaks when you mess it up. But I'd happily recommend one of the 'decaf' alternatives to it in those applications. (At least I've yet to hear an argument against them beyond level of adoption related reasons) And this doesn't apply to plain ECDH or signatures, where people should be adopting a whole misuse resistant cryptosystem rather than directly implementing their own and messing around with stuff like group law.