Comment by thadt
2 years ago
The unfortunate reality of this is that while he may be right, 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.
Adding accusatory hyperbolic statements like: "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!" doesn'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.
Unfortunately, NIST doesn't have a sterling reputation in this area, but if we'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.
This is 100% in line my reading of the submission.
Also noting that the page contains seventeen thousand words. That many words of harry potter take an average person 70 minutes to read. This text is no harry potter: it's chock-full of numbers, things to consider, and words and phrasings to weigh (like when quoting NIST), so you're not going to read it as fast as an average book, if you know enough about PQC to understand the text in the first place.
I even got nerdsniped near the beginning into clicking on "That lawsuit has been gradually <revealing> secret NIST documents, shedding some light on what was actually going on behind the scenes". That page (linked by the word <revealing>) is another 54000 words. Unaware, due to not having a scroll bar on mobile (my fault, I know), I started skimming it linearly to see what those revelations might be. Nothing really materialized. At some point I caught on that I seemed to have enrolled for a PhD research project and closed that tab to continue reading the original page...
Most HN readers, who are often smart and highly technical but in various fields, cannot reasonably weigh and interpret the techobabble evidence for "nist=bad". Being in an adjacent field, I would guess that I understand more than the average reader, but still don't feel qualified to judge this material without really giving it a thorough read. The page reasonably gives context and explains acronyms, but there's just so much of it that I can't imagine anyone who doesn't already know would want to bother with it. Not everyone understanding a submission is okay, but this is about accusations, and that makes me feel like it is not a good submission for HN.
HN readers that don't want to read the piece in full can take solace in that PQC has not been proven viable. Thus, what algorithms we should use to protect ourselves once what we thought was intractable becomes tractable may be a moot point. Shor's algorithm is capable of factoring 21 into 7 x 3. That's a long way off from factoring the thousands of digits-long numbers used for modern cryptography.
> Shor's algorithm is capable of factoring 21 into 7 x 3. That's a long way off from factoring the thousands of digits-long numbers
That is quite misleading, per my understanding.
Today's or near-future quantum computers can do this level of arithmetic, but Shor's algorithm does not have hardware limitations because it's an algorithm and not a computer. You can apply it to a thousand digits as well as to one. Apparently the thousand digits requires a certain number of qubits, i.e. a big enough quantum computer, but that's kind of the point: many people expect that we will gain that capability (keeping enough qubits stable for long enough to do the computation) sooner or later. Security agencies are saying to expect it in about ten years from now. Maybe you know better, yes can be, but that is not where I am going to put my money.
There now exist algorithms that can mitigate this risk, might as well use them. Why try to convince people they shouldn't bother?
1 reply →
Edit: Just realized the author is djb, Daniel Bernstein, which I guess is semi-ironic for me because I was recently praising him on HN for an old, well-read blog post on ipv6. Thus, I guess I may take back a bit of what I said below, or least perhaps it would be better to say that I can better understand the adversarial tone given djb's history with NIST recommendations (more info at https://en.wikipedia.org/wiki/Daniel_J._Bernstein#Cryptograp...).
> The unfortunate reality of this is that while he may be right, 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.
Couldn't agree with this more. I don't like to harp on form over substance, but in this case the form of this blog post was so bad I had difficulty evaluating whether the substance was worthwhile. I'm not in the field of cryptography, so I'm not qualified to assess on the merits, but my thoughts reading this were:
1. All the unnecessary snark and disparagement made me extremely wary of the message. It seemed like he was making good points, but the overall tone was similar to those YouTube "WhaT ThE ElITe DoN'T WanT YoU TO KnoW!!" videos. Frankly, the author just sounds like kind of an asshole, even if he is right.
2. Did anyone actually read this whole thing?? I know people love to harp on "the Internet has killed our attention spans", and that may be true, but the flip side is we're bombarded with so much info now that I take a very judicious approach to where I'll spend my time. On that point, if you're writing a blog post, the relevant details and "executive summary" if you will should be in the first couple paragraphs, then put the meandering, wandering diary after. Don't expect a full read if important tidbits are hidden like Where's Waldo in your meandering diary.
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?
> I know people love to harp on "the Internet has killed our attention spans"
Not just that. Give your parent or grandparent a 75-page booklet to read, full of accusations and snark, and let's say it's about something they care about and actually impacts their lives (maybe a local government agency, idk). What are the odds they are going to read that A-Z versus waiting for a summary or call-to-action to be put out? The latter can be expected to happen if there is actually something worthwhile in there.
This is objectively too long for casual reading, nothing to do with anyone's attention span.
(The 75-page estimate is based on: (1) a proficient reader doing about a page per minute in most books that I know of, so pages==minutes; (2) the submission being 17.6k words; (3) average reading speed is ~250 wpm, resulting in 17.6e3/250=70 minutes; (4) this is not an easy text, it has lots of acronyms and numbers, so conservatively pad to 75.)
People read it because of djb’s reputation. I’m the future, when someone smarter than you writes something it might benefit you to put aside your tone scolding and receive the information. It might be important.
1 reply →
> Did anyone actually read this whole thing?
Yup. I'm not a cryptographer, so I didn't understand most of the detail. I realized it ws DJB after a couple of paragraphs.
> the relevant details and "executive summary" if you will should be in the first couple paragraphs
It wasn't written for "executives".
> It wasn't written for "executives".
When writing about real-world topics (especially where the goal is to educate or change opinions), it's usually a good idea to summarize the overall piece at the beginning, regardless of the intended audience. If the piece is broken up into chapters, sections, etc., it often helps to open each of those with a summary as well.
Like a lot of technical people, my default writing style tends to be a linear/journal-entry structure that tells a story more or less in the order it occurred. Over time I've learned that that type of structure only really works if someone is already interested in the material. Otherwise, they're likely to see a wall of text and move on.
Summarizing the overall piece as well as sections lets the reader immediately figure out if what they're reading is relevant to them, what the author's goals are, and if there are parts they can skip over because they're already familiar with those topics.
Even worse, I expected to find a part when he reports it and includes the responses/follow-up from that... But this is the first time it's published a far as I understand? Did I miss it in the wall of text? Or is it really a huge initial writeup that may end up with someone responding "oh, we did mess up, didn't we? Let's think how to deal with that."
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...
3 replies →
That's pretty selective quoting of the issues. He even says himself that the waiting for the patent is one of the minor issues.
The many questions he asks is why did they repeatedly change the evaluation criteria after the fact, presented results in a misleading ways, and made basic calculation errors (remember these guys are experts). All these in favor of one algorithm.
Now to someone like me this points to the fact that they really wanted that algorithm to be the standard. If we add to that the fact that there was significantly more NSA involvement than indicated and that they did their best to hide this, leads me to be extremely skeptical of the standard.
Because someone likely stood to benefit from it. The question is who and how?
> If Kyber-512 is actually this risky, then it deserves to be communicated clearly.
The statement djb seems to be making: It is not known if Kyber-512 is as cryptographically strong as AES-128 by the definitions provided by NIST.
This is an issue because these algorithms will be embedded within hardware soon.
> Besides the fact that nobody is deploying standalone PQ for some time
Now that an implementation has been chosen to be standardized, hardware vendors are likely to start designing blocks that can more efficiently compute the FIPS 203 standard (if they haven't already designed a few to begin with).
Given that the standard's expected publication is in 2024, and the 1-2 year review timeline for NIST CMVP review on FIPS modules, I wouldn't be surprised to see a FIPS 140-3 Hardware Module with ML-KEM (Kyber-etc.) by mid 2026.
> a succinct breakdown of why
The issue seems to be his statement from [1]: "However, NIST didn't give any clear end-to-end statements that Kyber-512 has N bits of security margin in scenario X for clearly specified (N,X)."
djb succinctly outlines the "scenario X" he referred to in [2], in which he only needs a yes or no answer. He is literally asking the people who should know and be able to discuss the matter, who would have the technical background to discuss this matter. He had received no response, which is why he had posted [1].
NIST's reply in [3] is a dismissal of [1] without a discussion of the security itself. The frustrating part for me to read was the second paragraph: "The email you cited (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...), speaks for itself. NIST continues to be interested in people's opinions on whether or not our current plan to standardize Kyber512 is a good one. 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."
If NIST views the reviewers' claims about security to be "not particularly useful to the standardization process," (and remember: the reviewers are themselves cryptographers) then why should the public trust the standard at all?
> a smoking gun or two would be great
There wouldn't be a smoking gun because the lack of clarification is the issue at hand. If they could explain how they calculated the security strength of Kyber-512, then this would be a different issue.
The current 3rd party estimates of Kyber-512's security strength (which is a nebulous term...) puts it below the original requirements, so clarification or justification seems necessary.
[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...
> The current 3rd party estimates of Kyber-512's security strength (which is a nebulous term...) puts it below the original requirements
More to the point, (at least to my understanding) it puts it on par with another contender that was rejected from the NIST competition for being too weak a security construct.
If TFA were by a nobody I might agree, but TFA is by DJB and/or Tanja Lange, and they're not nobodies. These things need to be at least somewhat adversarial partly because that's what it takes to do cryptanalysis, and partly because of past shenanigans. It goes with the territory and the politics. It's unavoidable.
One can be combative and adversarial and still write succinctly and persuasively.
This text does DJB no favors. He comes across like a conspiracy theorist, based on the form of the content alone.