NIST Elliptic Curves Seeds Bounty

> "However, they gave no evidence of a back door, and in the two decades since that time no one has found a way that a back door could be inserted in DSA (or ECDSA)."

ElGamal/DSA is fragile and difficult to implement securely in a way that doesn't reveal secret k. ECC (and somewhat particularly NIST curves[1]) is also very difficult to implement securely from side channel attacks[2].

Consideration of "backdoors" should be broader than just mathematical equations on paper. "backdoors" could also include deliberate choice of algorithm or parameters that are fragile and difficult to implement in a secure way to minimise risk of side channel leakage of secrets. This is especially important in a whole variety of applications such as passports, payment cards and TPMs.

[1] https://www.hyperelliptic.org/tanja/vortraege/20130531.pdf#p...

[2] Specifically, implementation of: https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic...

So if I understand this correctly: the community accepted those mysterious strings of unknown origin while it would’ve been trivial to replace them with different strings with a known origin, by providing another but known input to the hash?

Agreed, I wouldn't have thought so a few weeks ago, but after seeing the messages that contain the first few SHA bytes of themselves in themselves, I don't know how implausible it is that they might have generated billions of strings and hashes and then chosen the weaker ones.

You understand the situation correctly, hence why it's kind of disastrous. The phrases "so close" and "you had one job" seem relevant here. Unfortunately, as far as I know this would be the only case related to the NSA and cryptographic standards where someone has alleged incompetence. Normally the stories run the other way.

Doubly problematic: NIST is known to have been compromised and putting backdoors into elliptic curve related standards, the fact that this mechanism didn't create trust was pointed out immediately, and neither NIST nor the NSA did anything to address the concern. Just like with Dual_EC_DRBG.

Triply problematic: the NSA explicitly told people in 2015 not to upgrade past the NIST curves to other curves, because quantum computers will soon be good enough to break ECC entirely and so everyone should switch to post-quantum crypto instead (which is new and still experimental widely used etc). If ECC worked fine, QC was far off and you wanted to keep people on the NIST curves for as long as possible this is exactly what you would say.

The cryptography community has not exactly covered itself in glory over this situation. It's been nearly 25 years now. There are newer curves that don't have this problem, why are the NIST curves still being used by anything? Where is the effort to phase them out, like there was with SHA1? This article even seems to be advertising them.

I think you're right to be suspicious, especially because the arguments for it not being possible are presented as if they are mathematical but are actually social.

The usual response to these concerns is to argue that academics are so excellent that they would certainly have discovered what the NSA was up to by now, if there was a way to do it, and anyone who doesn't agree with that is as FUDy pleb who just doesn't get it. The article repeats this party line, although it's great to now see the problem being taken more seriously with an organized bounty programme. I'll be surprised but happy if anyone actually finds pre-images. But the frequency with which concerns are blown off here is just not good enough.

I've done some cryptography work in the past and for several years had to regularly review cryptography papers as part of my job. I've attended cryptography conferences, talked with researchers, implemented various "exotic" things with elliptic curve cryptography and so on. Not exactly an insider but not a complete outsider either. The party line here looks very dangerous to me.

Let's recap the arguments here because neither of them seem strong and neither are actually mathematical at their core.

1. If there was a way to execute a kleptographic attack on NIST curve standardization, academics would have found it by now. If not academics, then someone in industry.

2. Dual_EC_DRBG was detected as suspicious immediately, so the public cryptography community is good at spotting back doors.

For (1) why should that be so? It actually seems unlikely to me. Cryptography suffers the same problems as the rest of academia w.r.t. the file drawer problem and "publish or perish" incentives. If you're an up and coming university researcher, which path is more profitable for you? Develop some clever new zero knowledge proof algorithm and be fairly certain to publish some cool new paper that gets cited a lot, or start attacking an algorithm that "everyone" already knows to be incredibly strong and almost certainly come up with nothing. If you take the latter the expected outcome is that you languish in obscurity at best or simply perish at worst (lose funding, exit academia with nothing to show and being seen as a crank).

Put another way the argument for the strength of academic understanding is that lots of really clever people have studied this in depth and found nothing. There is a Consensus Of Experts. But because you don't get to publish null results in academia, there's actually no way to know how much effort has been put towards this kind of problem. That's why assertions about academic crypto-analytic supremacy are always so handwavey and difficult to reason about. There's no actual numerical proof of work being done, and we know that some fields of academia have extreme difficulty with things being declared a "consensus" for social reasons that later have to be walked back.

Moreover, researching kleptography specifically (how to backdoor standards) isn't a good career path because kleptography isn't useful for anything unless you're the NSA, so you probably won't be able to easily transition to a post-academic career in industry on the back of that expertise and you won't get many citations.

The NSA doesn't have any of these problems. It can pay better wages than academia, hire more researchers than all of academia put together, and then assign them full time to research that is likely to be a dead end or which is useful only for backdooring standards. It can also easily build multi-disciplinary teams and fund research that academic cryptography just can't tackle at all due to lack of hardware budgets. And it has been doing exactly that for decades.

If I had to bet on whose understanding of ECC is better, the NSA's or academia's, well, all the firepower is on the side of the government. It's not even a close competition. In fact we can even measure how much firepower the government has, hence the well worn line about how many maths PhDs they hire, but we actually have no idea how much firepower academia levels at this part of the problem space.

So we're left with argument (2), people immediately raised the alarm about Dual_EC_DRBG so the NSA must actually kinda suck at designing backdoors. But this isn't an ideal argument because people immediately raised concern about the NIST curves too. The only difference is that in the former case, there was already a known algorithm that could be used to pull off the needed attack, and in this case there isn't.

Fundamentally there's no reason this debate should even be needed. It's been known for decades how to avoid doubt here, that's the whole reason the NIST curves are the output of SHA1 to begin with. The best time to phase out the NIST curves was decades ago, the second best time is today.