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

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

Blowfish has an unusually slow key-setup phase. Slowness is an advantage for password hashes, since it makes offline attacks harder.

I read the whole thing because of who the author was.

The executive summary is above the fold:

Take a deep breath and relax. When cryptographers are analyzing the security of cryptographic systems, of course they don't make stupid mistakes such as multiplying numbers that should have been added.

If such an error somehow managed to appear, of course it would immediately be caught by the robust procedures that cryptographers follow to thoroughly review security analyses.

Furthermore, in the context of standardization processes such as the NIST Post-Quantum Cryptography Standardization Project (NISTPQC), of course the review procedures are even more stringent.

The only way for the security claims for modern cryptographic standards to turn out to fail would be because of some unpredictable new discovery revolutionizing the field.

Oops, wait, maybe not. In 2022, NIST announced plans to standardize a particular cryptosystem, Kyber-512. As justification, NIST issued claims regarding the security level of Kyber-512. In 2023, NIST issued a draft standard for Kyber-512.

NIST's underlying calculation of the security level was a severe and indefensible miscalculation. NIST's primary error is exposed in this blog post, and boils down to nonsensically multiplying two costs that should have been added.

How did such a serious error slip past NIST's review process? Do we dismiss this as an isolated incident? Or do we conclude that something is fundamentally broken in the procedures that NIST is following?

It's in there.

He first raised the issue in April 2022.

Then in December 2022 he asked about the evaluation of Kyber's security and they posted this[1], which included a 2^40 multiple that he wasn't sure where it came from; if it came from where he thought it did (bogus math on numbers from a paper DJB himself coauthored), then that was troubling.

There was no response, so a few weeks later he posted his assumptions and asked if anyone else could come up with another possible explanation for what the NIST e-mail was assuming.

This did get a response[2], the main thrust of which was:

> While reviewers are free, as a fun exercise, to attempt to "disprove what NIST _appears_ to be claiming about the security margin," the results of this exercise would not be particularly useful to the standardization process. NIST's prior assertions and their interpretation are not relevant to the question of whether people believe that it is a good idea to standardize Kyber512.

After further prodding the response[3] was essentially a rather polite version of "You're the scientist and it's your model, why don't you tell us?" Which DJB considers dodging his question of "How did you get these numbers?"

At this point DJB posts[4] a dissection of the December 2022 e-mail, which is similar to the middle quarter of TFA.

1: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...

2: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...

3: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...

4: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...

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.