4 ms·

> the NSA would have had to be aware of a class of weak curves so large that it’s not plausible that no one in academia or industry discovered them in 25 years.

> the NSA would have had to be aware of a class of weak curves so large that it’s not plausible that no one in academia or industry discovered them in 25 years. GCHQ in the U.K. hires more mathematicians than any other research institute or University in the country. Not sure about the US equivalents but I imagine it’s similar. Diffie-Helman key exchange was known about by GCHQ and the NSA prior to it being rediscovered by Diffie and Helman. I think it’s hard to assume anything about the underlying capabilities of intelligence institutions. Not saying they do know this but it’s also not impossible, this stuff is their bread and butter.

geraldwhen 3y ago
The NSA employs US math professors in number theory.
mike_hearn 3y ago
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.
- GTP 3y ago
  I'm still not fully convinced by your point about what's best to fuel an academic career. While putting it as trying to find vulnerabilities into some specific cryptosystem largely believed to be secure indeed doesn't sound that interesting, if you instead put it as finding new attacks for elliptic curve cryptography we're back again the "cool paper with lots of citations" territory. As a side note, in the past a PhD student was tasked with the "not interesting sounding and apparently useless in practice" task of filling the gaps in OCB2's security proof. That's how it was discovered that it was utterly broken.
  - mike_hearn 3y ago
    You only get a cool paper with lots of citations if you actually do find a new attack. If you spend a four year PhD searching and come up with nothing, which is what the field tells you to expect, then you end up with nothing. At the NSA you get a four year salary, maybe even a promotion, who knows.
- cnull 3y ago
  [flagged]

geraldwhen 3y ago

The NSA employs US math professors in number theory.

mike_hearn 3y ago

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.

GTP 3y ago
I'm still not fully convinced by your point about what's best to fuel an academic career. While putting it as trying to find vulnerabilities into some specific cryptosystem largely believed to be secure indeed doesn't sound that interesting, if you instead put it as finding new attacks for elliptic curve cryptography we're back again the "cool paper with lots of citations" territory. As a side note, in the past a PhD student was tasked with the "not interesting sounding and apparently useless in practice" task of filling the gaps in OCB2's security proof. That's how it was discovered that it was utterly broken.
- mike_hearn 3y ago
  You only get a cool paper with lots of citations if you actually do find a new attack. If you spend a four year PhD searching and come up with nothing, which is what the field tells you to expect, then you end up with nothing. At the NSA you get a four year salary, maybe even a promotion, who knows.
cnull 3y ago
[flagged]