Debunking NIST's calculation of the Kyber-512 security level

An important detail you really want to understand before reading this is that NIST (and NSA) didn't come up with these algorithms; they refereed a competition, in which most of the analysis was done by competitors and other academics. The Kyber team was Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, Damien Stehlé, and also Peter Schwabe, a collaborator of Bernstein's.

The unfortunate reality of this is that while he may be <i>right</i>, it is difficult to classify the responses (or non-response) from the NIST people as deceptive vs just not wanting to engage with someone coming from such an adversarial position. NIST is staffed by normal people who probably view aggressively worded requests for clarification in the same way that most of us have probably fielded aggressively worded bug reports.<p>Adding accusatory hyperbolic statements like: &quot;You exposed three years of user data to attackers by telling people to use Kyber starting when your patent license activates in 2024, rather than telling people to use NTRU starting in 2021!&quot; doesn&#x27;t help. Besides the fact that nobody is deploying standalone PQ for some time, there were several alternatives that NIST could have suggested in 2021. How about SIKE? That one was pretty nice until it was broken last year.<p>Unfortunately, NIST doesn&#x27;t have a sterling reputation in this area, but if we&#x27;re going to cast shade on the algorithm and process, a succinct breakdown of why, along with a smoking gun or two would be great. Pages and pages of email analysis, comparison to (only) one other submission, and accusations that everyone is just stalling so data can be vacuumed up because it is completely unprotected makes it harder to take seriously. If Kyber-512 is actually this risky, then it deserves to be communicated clearly.

That&#x27;s more of a diary than an article -- jargony, disorganized, running in circles, very hard to follow. But the information might be important regardless. There&#x27;s a strong implication that NIST with help of the NSA intentionally standardized on a weak algorithm.<p>We all know that&#x27;s possible.<p>But can someone who follows some of this stuff more closely explain what the play would be? I always assumed that weakening public cryptography in such a way is a risky bet, because you can&#x27;t be sure that an attacker doesn&#x27;t independently find out what you know. You can keep a secret backdoor key (that was the accusation when they released Dual_EC_DRBG), but you can&#x27;t really hide mathematical results.<p>Why would they be willing to risk that here?

Related thread from last year, with 443 comments:<p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=32360533">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=32360533</a> (<i>&quot;NSA, NIST, and post-quantum crypto: my second lawsuit against the US government (cr.yp.to)&quot;</i>)

&gt; <i>Discovering the secret workings of NISTPQC. I filed a FOIA request &quot;NSA, NIST, and post-quantum cryptography&quot; in March 2022. NIST stonewalled, in violation of the law. Civil-rights firm Loevy &amp; Loevy filed a lawsuit on my behalf.</i><p>As much as I generally loathe djb personally, professionally he will always have my support as he’s been consistently willing to take the federal government to task in court. It brings me great joy to see he’s still at it.

Notwithstanding DJB&#x27;s importance to cryptography, and the fact that I&#x27;m ignorant of a large number of details here, there was a point where he lost a lot of credibility with me.<p>Specifically, when he gets to the graphs, he says &quot;NIST chose to deemphasize the bandwidth graph by using thinner red bars for it.&quot; That is just not proven by his evidence, and there is a very plausible explanation for it. The graph that has the thinner bars is a bar chart that has more data points than the other graph. Open up your favorite charting application, and observe the difference in a graph that has 12 data points versus one with 9... of course the one with 12 data points has thinner lines! At this point, it feels quite strongly to me that he is trying to interpret every action in the most malicious way possible.<p>In the next bullet point, he complains that they&#x27;re not using a log scale for the graph... where everything is in the same order of magnitude. That doesn&#x27;t sound like a good use case for log scale, and I&#x27;m having a hard time trying to figure out why it might be justified in this case.<p>Knowing that DJB was involved in NTRU, it&#x27;s a little hard to shake the feeling that a lot of this is DJB just being salty about losing the competition.

Something I&#x27;ve learned from a career of watching cryptographer flame wars: Don&#x27;t bet against Bernstein, and don&#x27;t trust NIST.

<a href="http:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20231003195013&#x2F;https:&#x2F;&#x2F;blog.cr.yp.to&#x2F;20231003-countcorrectly.html" rel="nofollow noreferrer">http:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20231003195013&#x2F;https:&#x2F;&#x2F;blog.cr.yp...</a><p><a href="https:&#x2F;&#x2F;archive.ph&#x2F;NrOG6" rel="nofollow noreferrer">https:&#x2F;&#x2F;archive.ph&#x2F;NrOG6</a>

NIST responded: <a href="https:&#x2F;&#x2F;groups.google.com&#x2F;a&#x2F;list.nist.gov&#x2F;g&#x2F;pqc-forum&#x2F;c&#x2F;W2VO" rel="nofollow noreferrer">https:&#x2F;&#x2F;groups.google.com&#x2F;a&#x2F;list.nist.gov&#x2F;g&#x2F;pqc-forum&#x2F;c&#x2F;W2VO</a>...

I&#x27;m not sure N(IST)SA has any credibility left. Polularity of curve 25519 over their P curves is encouraging and it would be great to see the community continue this direction and largely ignore them going forward. The government shouldn&#x27;t be leading or deciding, it would be better organized around gathering current consensus and following when it comes to FIPS, regulation, etc.

The NIST standardization process, appears to have a grey area particularly around the selection of constants.<p>The skepticism around standardization, advocating instead for direct adoption from cryptographers, sheds light on potential shortcomings in the current system.<p>There is definitely a need for a more transparent or open scrutiny in algorithm standardization to ensure security objectives are met.

Related note: Government employees (including military, intel) are just people, and worse, bureaucrats. They aren&#x27;t magical wizards who can all do amazing things with mathematics and witchcraft. If they were good at what they do, they wouldn&#x27;t need ever increasing funding and projects to fix things.

My takeaway (impression) from the DJB post is that the evaluation by the NISTPQC seems not to provide algorithms with a firm level of security. That the evaluation is not clear cut, and not provide a good, conservative lower bound for the security provided by the algorithms selected.

&quot;Security is supposed to be job #1. So I recommend eliminating Kyber-512.&quot;

It would be interesting to see Signal Sciences response to this Bernstein’s post

Minor typo. &quot;How can NIST justify throwing NIST-509 away?&quot; should be &quot;How can NIST justify throwing NTRU-509 away?&quot;

Scorpions and frogs as usual.

If you have never heard of Bernstein, this may look like mad ramblings of a proto-Unabomber railing against THE MAN trying to oppress us.<p>However, this man is one of the foremost cryptographers in the world, he has basically single-handedly killed US government crypto export restrictions back in the days, and (not least of all because of Snowden) we know that the NSA really is trying to sabotage cryptography.<p>Also, he basically founded the field of post-quantum cryptography.<p>Is NIST trying to derail his work by standardizing crappy algorithms with the help of the NSA? Who knows. But to me it does smell like that.<p>Bernstein has a history of being right, and NIST and the NSA have a history of sabotaging cryptographic standards (google Dual_EC_DRBG if you don&#x27;t know the story).

Love the narrative style of this writing second-guessing the erroneous thought processes. Are they deceptive? Who knows.<p>What worries me is that it&#x27;s neither malice nor incompetence, but that a new darker force has entered our world even at those tables with the highest stakes.... dispassion and indifference.<p>It&#x27;s hard to get good people these days. A lot of people stopped caring. Even amongst the young and eager. Whether it&#x27;s climate change, the world economic situation, declining education, post pandemic brain-fog, defeat in the face of AI, chemicals in the water.... everywhere I sense a shrug of slacking off, lying low, soft quitting, and generally fewer fucks are given all round.<p>Maybe that&#x27;s just my own fatigue, but in security we have to vigilant <i>all the time</i> and there&#x27;s only so much energy humans can bring to that. That&#x27;s why I worry that we will lose against AI. Not because it&#x27;s smarter, but because it doesn&#x27;t have to _care_, whereas we do.

Unfortunately, the NSA &amp; NIST most likely is recommending a quantum-proof security that they&#x27;ve developed cryptanalysis against, either through high q-bit proprietary technology or specialized de-latticing algorithms .<p>The NSA is very good at math, so I&#x27;m be thoroughly surprised if this analysis was error by mistake rather than error through intent.

Assuming djb is correct and the current process is broken... is trying to expose it and then fix it through FOIA requests really the best approach?<p>If your codebase is hairy enough, and the problem to be solved is fundamentally fairly simple, sometimes it&#x27;s better to rewrite than refactor. Doubly so if you believe a clever adversary has attempted to insert a subtle backdoor or bugdoor.<p>What would a better crypto selection process look like? I like the idea of incorporating &quot;skin in the game&quot; somehow... for example, the cryptographer who designs the scheme could wager some cash that it won&#x27;t be broken within a particular timeframe. Perhaps a philanthropist could offer a large cash prize to anyone who&#x27;s able to break the winning algorithm. Etc.