Debunking NIST's calculation of the Kyber-512 security level
blog.cr.yp.to
blog.cr.yp.to
I don't know of any cryptographer or cryptography engineer that takes the SHA3 innuendo seriously. Do you?
Additional backstory that might be helpful here: about 10 years ago, Bernstein invested a pretty significant amount of time on a research project designed to illustrate that "nothing up my sleeves" numbers, like constants formed from digits of pi, e, etc, could be used to backdoor standards. When we're talking about people's ability to cast doubt on standards, we should keep in mind that the paragon of that idea believes it to be true of pi.
I'm fine with that, for what it's worth. Cryptography standards are a force for evil. You can just reject the whole enterprise of standardizing cryptography of any sort, and instead work directly from reference designs from cryptographers. That's more or less how Chapoly came to be, though it's standardized now.
My understanding of the Dual-EC problem may be different than yours. As I understand it, the construction is such that if you choose the two constants randomly, it's fine, but if you derived them from a known secret, the output was predictable for anyone who knows the secret. The NIST did not provide proof that the constants used were chosen randomly.
Random choice would be equivalent to encrypting with a public key corresponding to an unknown private key, while the current situation has some doubt about whether the private key is known or not.
First, because its output has unacceptable biases [1,2].
Second, because its presence allows an attacker to create a difficult-to-detect backdoor simply by replacing the key, as apparently happened with Juniper NetScreen devices [3,4].
--- [1] Kristian Gjøsteen, Comments on Dual-EC-DRBG/NIST SP 800-90, draft December 2005. Online: https://web.archive.org/web/20110525081912/https://www.math....
[2] Berry Schoenmakers and Andrey Sidorenko, Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, May 2006. Online: https://eprint.iacr.org/2006/190.pdf
[3] Stephen Checkoway, Jacob Maskiewicz, Christina Garman, Joshua Fried, Shaanan Cohney, Matthew Green, Nadia Heninger, Ralf-Philipp Weinmann, Eric Rescorla, and Hovav Shacham, A Systematic Analysis of the Juniper Dual EC Incident, October 2016. Online: https://www.cs.utexas.edu/~hovav/dist/juniper.pdf
[4] Ben Buchanan, The Hacker and the State, chapter 3, Building a Backdoor. Harvard University Press, February 2020.
What's a "verifiably random" key?
It's both.
It is bad enough even without the constants
https://blog.cryptographyengineering.com/2013/09/18/the-many...
NIST may or may not consort with your friendly local neighborhood NSA people, who are bright and talented contributors in their own right. That's simply in addition to reading the same mailing lists
At the end, NIST gets to pick a winner and explain their reasonning. What influenced the decision is surely a combination of things, some of which may be internal or private discussions
Is that not the case?
Or the s-boxes in DES, that the NSA suggested to IBM + NIST's predecessor, so as to be resistant to then-not-widely-known differential cryptanalysis? https://web.archive.org/web/20120106042939/http://securespee...
There is a widely held belief that the US IC changed fundamentally in terms of their regard for their own raison d’etre that day.
I'd like to think the US is in the midst of that now, with the Afghan withdrawal and Ukraine war.
> I filed a FOIA request "NSA, NIST, and post-quantum cryptography" in March 2022. NIST stonewalled, in violation of the law. Civil-rights firm Loevy & Loevy filed a lawsuit on my behalf.
> That lawsuit has been gradually revealing secret NIST documents, shedding some light on what was actually going on behind the scenes, including much heavier NSA involvement than indicated by NIST's public narrative.
even if I had never heard of DUAL_EC_whatsit, there's enough here to make me mistrust NIST.
It is worth noting that while breaking codes is a big part of the NSA's job, they also have a massive organization (NSA Cybersecurity, but I prefer the old name Information Assurance) that works to protect US and allied systems and cryptographic applications.
In the balance, weakening American standards does little to help with foreign collection. Their efforts would be much better spent injecting into the GOST process (Russia and friends) or State Cryptography Administration (China and friends).
While that makes logical sense, the previous actions of the NSA has demonstrated they're not a logical actor in regards to this stuff, or that there's more going on.
Though it can be greatly beneficial for domestic collection. Further, so long as the US remains a dominant player in Tech and Tech-influenced fields like finance, odds are a lot of the world is going to be at least de facto using US standards.
I've seen enough blatant disregard for humanity to assume any kind of honesty in the powers that were.
No one can say they pushed some useless or overtly backdoored encryption. That's rarely how Intel agencies work. It's also not how they need to work to maintain their effectiveness indefinitely.
When the CIA is trying to recruit for HUMINT if they can get claws into anything whether it's a business conference that has a 0.1% chance they'll meet some pliable young but likely future industry insider that may or may not turn into a valuable source then they'll show up to every single year to that conference. It's a matter of working every angle you can get.
They aren't short of people, time, or money. And in security tiny holes in a dam turn into torrents of water all the time.
The fact NIST is having non public backroom meetings with NSA, concealing NSA employee paper authors, generating a long series of coincidental situations preferencing one system, and stonewalling FIOAs from reputable individuals. IDK, if was a counter intelligence officer in charge of detecting foreign IC work I'd be super suspicious of anything sold as safe and open from that org.
Well, everything apart from the secret stuff:
"I filed a FOIA request "NSA, NIST, and post-quantum cryptography" in March 2022. NIST stonewalled, in violation of the law. Civil-rights firm Loevy & Loevy filed a lawsuit on my behalf.
That lawsuit has been gradually revealing secret NIST documents, shedding some light on what was actually going on behind the scenes, including much heavier NSA involvement than indicated by NIST's public narrative"
Every single document will be reviewed by a court before being opened up, and any which say "We did this so we can hoodwink the public and snoop on russia and china" won't be included.
Ever since Snowdon we know it's actually "hoodwink the public and snoop on the public"
Russia and China are just an excuse.
BUT. On security margins, you could argue the Serpent designers were too conservative: https://eprint.iacr.org/2019/1492 It is also true that cryptanalytic attacks appear to fare slightly better against AES than Serpent. What does this mean? A brute force attack has the same number of operations as the claimed security level, say, 2^128 for 128-bit. An attack is something better than this: fewer operations. All of the attacks we know about achieve slightly less than this security level - which is nonetheless still impossible to do - but that comes at a cost: they need an infeasible amount of memory. In terms of numbers: 9000 TB to reduce 2^128 to 2^126 against full-round AES according to a quick check of wikipedia. For reference, the lightweight crypto competition considered 2^112 to be sufficient margin. 2^126 is still impossible.
In practice, the difference between Serpent and AES in terms of cryptanalytic security is meaningless. It is not an example of NIST picking a weaker algorithm deliberately, or I would argue, even unintentionally. It (AES) was faster when implemented in software for the 32-bit world that seemed to be the PC market at the time.
Regardless, the comparison wasn't intended to argue for a meaningful difference in security margin, but to show that that the winner of the competition, well, wins (in adoption).
Thanks for digging that paper out again. It is really telling that AES only gets a bit of a bump (10-30%) while the other ones gain like 2x or more.
I was about to comment that the competitors to AES were definitely too conservative, and it bit them because of how much slower it made them in software and larger in hardware.
Often, yes. But also consider the SHA-3 competition.
BLAKE2 seems more widely used than what was chosen for SHA-3 (Keccak). What was submitted for the SHA-3 competition was BLAKE1 (it didn't have a number back then but I think this is clearer) so it's not like NIST said that Keccak is better than BLAKE2, they only said it's better than BLAKE1 (per their requirements, which are unlikely to align with your requirements because of the heavy weighing of speed-in-hardware), but still this is an example of a widely used algorithm that is not standardized.
> how often do you see Serpent being mentioned, despite it having a larger security margin than Rijndael
The goal of an encryption algorithm is not only to be secure. Sure, that has to be a given: nobody is going to use a broken algorithm when given a choice. But when you have two secure options, the more efficient one is the one to choose. You could use a 32k RSA key just to be sure, or a 4k RSA key which (to the best of my knowledge) everyone considers safe until quantum. (After quantum, you need something like a 1TB key, as djb humorously proposed.)
Wikipedia article on Serpent: "The 32 rounds mean that Serpent has a higher security margin than Rijndael; however, Rijndael with 10 rounds is faster and easier to implement for small blocks."
I don't know that nobody talks about Serpent solely because it was not chosen as winner. It may just be that Rijndael with 256-bit keys is universally considered secure and is more efficient at doing its job.
Re: Serpent, there are many things to unpack here but, in summary, you don't know a priori how large of a security margin you need (given the primary function of a cipher, you want to pick the conservative option), efficiency concerns become much less relevant with hardware-accelerated implementations and years of Moore's law performance uplifts, low-power devices can take advantage of much lighter algorithms than Rijndael OR Serpent, ease of implementation does not equal ease of correct/secure implementation vis-a-vis side channel attacks, and certainly if Serpent was chosen you wouldn't see Rijndael talked about much.
Speculatively, if SHA2 is broken without breaking Merkle-Damgard hashes in general, Blake2/3 could well become SHA4.
Ah, maybe my experience is biased then. I keep coming across BLAKE2 implementations, but rarely hear so much as people considering to use SHA-3 somewhere. If anyone has actual numbers on this, that would be interesting.
It would be good if SHA-3 is being used because then chip makers have a reason to bake it into their hardware, which is exactly where the biggest gain over SHA-2 is expected. If that happens, and all else being equal (no cracks appear in Keccak), I'd be surprised if BLAKE2 remains as popular!
> you don't know a priori how large of a security margin you need
True, so this can be argued to be an educated guess at first. But then confidence increases over time. It seems to be expected that, more than 20 years later, people aren't considering Serpent anymore. Is it because it wasn't chosen as AES? Certainly partially, but BLAKE2 (I'll admit it does seem like an outlier) likely will still be talked about in the future so standardization is not the only factor.
I didn't see actual benchmarks, but Serpent sounds at least three times slower than Rijndael for, by now, no tangible benefit. What would be interesting is if there were AES competitors that are also fully unbroken and are more efficient than Rijndael, or easier to implement, etc.
The real reason I would have liked that to be the case is so that one could use WebAuthn and Subtle Web Crypto to sign things and have the blockchain natively verify the signature.
As it is, I am hoping that EVM will roll out a precompiled signature verifier for secp256r, which is on the roadmap — they say!
Work is also being done on SNARK-based cross-curve signature verification
But I fully agree, especially with the growing popularity of account abstraction, the EVM desperately needs a secp256r1 precompile!
You can read the original report on the candidates: https://nvlpubs.nist.gov/nistpubs/jres/106/3/j63nec.pdf
To save you some time, one software evaluation is on page 531. Serpent performs worse in software than Rijndael (AES) just about everywhere (note they use categories rather than precise metrics, but you can dig into that if you want). By contrast, one hardware evaluation is on page 539. Serpent has the highest throughput for the lowest "area" i.e. required. These results repeat on p541.
So it depends on whether you are comparing a software or hardware implementation.
There's also BLAKE3 and it is amazing. How is its adoption going?
Almost all of these downsides are helpful for password has validation function like bcrypt() because there is nothing to an attacker can to guess much faster than a desktop CPU.
Blowfish was a good cipher at a time when CPUs lacked dedicated trustworthy crypto engines, wide and deep OoO execution capability, and packed-SIMD support. AES and SHA1/2 are commonly implemented in hardware on modern server, desktop and mobile CPUs. Where hardware offloading isn't available ciphers can take advantage of OoO and SIMD to perform vastly more useful work per cycle than stalling on memory accesses.
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.
> 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.
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.)
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...
That seems to be an extraordinarily strong claim to make, without detailed explanation, which apparently wasn't provided.
I think there was also a bit of DJB wanting to engage NIST in a scientific debate (and getting increasingly abrasive when this didn't happen), while NIST wanted none of that, preferring that such debates be between researchers.
However from the point of view advanced in TFA, the best published papers implied that Kyber's security was likely very close to another algorithm (that the author of TFA preferred) that was disqualified for being insufficiently strong.
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?
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".
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.
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.
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?
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...
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.
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.
This text does DJB no favors. He comes across like a conspiracy theorist, based on the form of the content alone.
We all know that's possible.
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't be sure that an attacker doesn'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't really hide mathematical results.
Why would they be willing to risk that here?
Certain types of attacks basically make it so you need to have a specific private key to act as a backdoor. That's the current guess on what may be happening with the NIST ECC curves.
If so, this can be effectively a US-only backdoor for a long, long time.
The problem with the NIST ECC curves are that we still do not know where the heck that seed came from and why that seed specifically.
On the other hand, there is a lot of reasons to use elliptic curve that was intentionally designed, so, DJB's designs. And well, in 2009 I would not imagine that the kinds of stuff that DJB publishes will end up being TLS1.3.
Hypothesis 1: because the NSA sees evidence that more efficient cryptographic algorithms are easier to crack for them.
To give some weak evidence for this: if you need brute force to crack the cipher (or hash function), a more efficient algorithm need less computation power to crack.
Hypothesis 2: A more efficient algorithm is likely to become applied in more areas than a less efficient one (think of smartcards or microcontrollers). So if the NSA finds a weakness or is capable of introducing a backdoor in it, it can decrypt a lot more data from more areas.
see: colonial oil pipeline hack
Industries with secure fences that are regularly patrolled are entirely different to industries with partial coverage by unpatrolled rusty fences and a freestanding door frame that has a titanium unpickable lock.
Passwords get compromised that's a fact.
How the single employee password that got breached was obtained is still (AFAIK) a mystery - but this will always happen ... given many employess, at least one will eventually make a mistake.
After that, the VPN had no multifactor authentication, the network had no internal honey subnets, canary accounts, sanity checks, etc.
High-quality crypto alone does not make for secure systems.
And systems can be secure with lower quality crypto if the systems are robust.
It's not entirely known how every step of that attack went down, but "breaking low quality crypto" hasn't factored into any incident write up I've ever seen.
However, nearly all ransomware uses rsa. Therefore in this particular case, high quality crypto caused harm.
(To state the obvious, I'm not advocating for bad crypto, just discussing this case).
https://news.ycombinator.com/item?id=32360533 ("NSA, NIST, and post-quantum crypto: my second lawsuit against the US government (cr.yp.to)")
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.
However, the man has done so much to advance privacy and cryptography I think he’s earned the right to be a bit snippy, especially when he’s discussing something so complex 99% of the comments are “too long to read” and “I read it but I still don’t understand it”.
Specifically, when he gets to the graphs, he says "NIST chose to deemphasize the bandwidth graph by using thinner red bars for it." 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.
In the next bullet point, he complains that they're not using a log scale for the graph... where everything is in the same order of magnitude. That doesn't sound like a good use case for log scale, and I'm having a hard time trying to figure out why it might be justified in this case.
Knowing that DJB was involved in NTRU, it's a little hard to shake the feeling that a lot of this is DJB just being salty about losing the competition.
There isn't a lot of people in the world with the technical know-how for cryptography. It's clear that competitors in this space are going to be reviewing eachothers work.
Given the long and detailed history of various governments and government agencies purposefully attempting to limit the public from accessing strong cryptography, I tend to agree with the "assume malice by default" approach here. Assuming anything else, to me at least, seems pretty naive.
If you read his posts there, it’s hard not to come away with the impression that he’s just upset his favourite scheme wasn’t chosen.
The actual way that the NSA had tried to limit DES was to cap its key length at 48 bits, figuring that their advantage in computing power would let them brute force it when no one else could. (NIST compromised between the NSA's desire for 48 and the rest of the world's desire for 64, which was why DES had the always bizarre 56 bit key.) So sometimes they strengthen it, sometimes they weaken it, and so I'm not sure it appropriate to presume malice.
If you had a dog that sometimes licked you and sometimes bit you, would you let it sleep with you?
Neither NSA nor NIST can be trusted. They brought this on themselves.
The skepticism around standardization, advocating instead for direct adoption from cryptographers, sheds light on potential shortcomings in the current system.
There is definitely a need for a more transparent or open scrutiny in algorithm standardization to ensure security objectives are met.
Got my wires crossed.
I wrote some more details here: https://community.signalusers.org/t/signal-blog-quantum-resi...
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.
Also, he basically founded the field of post-quantum cryptography.
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.
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't know the story).
> The point isn't that NIST is trustworthy. The point is that the PQC finalist teams are comprised of academic cryptographers from around the world with unimpeachable reputations, and it's ludicrous to suggest that NSA could have compromised them. The whole point of the competition structure is that you don't simply have to trust NIST; the competitors (and cryptographers who aren't even entrants in the contest) are peer reviewing each other, and NIST is refereeing.
> What Bernstein is counting on here is that his cheering section doesn't know the names of any cryptographers besides "djb", Bruce Schneier, and maybe, just maybe, Joan Daemen. If they knew anything about who the PQC team members were, they'd shoot milk out their nose at the suggestion that NSA had suborned backdoors from them. What's upsetting is that he knows this, and he knows you don't know this, and he's exploiting that.
---
> I spent almost 2 decades as a Daniel Bernstein ultra-fan --- he's a hometown hero, and also someone whose work was extremely important to me professionally in the 1990s, and, to me at least, he has always been kind and cheerful... I know what it's like to be in the situation of (a) deeply admiring Bernstein and (b) only really paying attention to one cryptographer in the world (Bernstein).
> But talk to a bunch of other cryptographers --- and, also, learn about the work a lot of other cryptographers are doing --- and you're going to hear stories. I'm not going to say Bernstein has a bad reputation; for one thing, I'm not qualified to say that, and for another I don't think "bad" is the right word. So I'll put it this way: Bernstein has a fucked up reputation in his field. I am not at all happy to say that, but it's true.
---
> What's annoying is that [Bernstein is] usually right, and sometimes even right in important new ways. But he runs the ball way past the end zone. Almost everybody in the field agrees with the core things he's saying, but almost nobody wants to get on board with his wild-eyed theories of how the suboptimal status quo is actually a product of the Lizard People.
(https://news.ycombinator.com/item?id=32365259, https://news.ycombinator.com/item?id=32368598, https://news.ycombinator.com/item?id=32365679)
Of course I'm not saying that either of those things happened, nor that they would be easy to accomplish. Hell, maybe they're literally impossible and I just don't understand enough cryptography to know why. Maybe the NIST truly has our best interest at heart this time. I'm just saying that, to me, it doesn't seem impossible for the NIST to ensure that the winner of their cryptography contests is an algorithm that's subtly broken. And given that there's even a slight possibility, maybe distrusting the NIST recommendations isn't a bad idea. They do after all have a history of trying to make the world adopt subtly broken cryptography.
But we must also recognize a difference in degree. In a competition where the US has no official influence over the result, there has to be a huge conspiracy to affect which algorithm is chosen. But in the competition which actually happened, they may potentially just need a single plant on one of the strong teams, and if that plant is successful in introducing subtle brokenness into the algorithm without anyone noticing, the NIST can just declare that team's algorithm as the winner.
I think it's perfectly reasonable to dismiss this possibility. I also think it's reasonable to recognize the extreme untrustworthiness of the NIST and decide to not trust them if there's even a conceivable way that they might've messed with the outcome of their competition. I really can't know what the right choice is.
For what it's worth, I do think the US government could corrupt academic cryptographers. If I was an academic cryptographer, and someone from the US government told me to do something immoral or else they would, say, kill my family, and they gave me reason to believe the threat was genuine, I'm not so sure I wouldn't have done what they told me. And I know this sounds like spy movie shit, but this is the US government.
One last thing though, if you're giving me the black and white choice between blindly trusting the outcome of a US government cryptography standard competition or distrusting the field of cryptography altogether, I choose the latter.
Note that the “forcing someone to comply” thing was just meant as one possibility among many, I don’t see why you completely dismiss the idea of someone who’s good at cryptography being in on the US’s mission to intercept people’s communications. I mean the NSA seems to be full of those kinds of people. You also dismiss the possibility that they just … picked the algorithm that they thought they could break after analysing it, with no participant being in on anything. But I get the feeling that you’re not really interested in engaging with this topic anymore, so I’ll leave it at that. It’s already late here.
Secrets are hard to keep at scale. Trying to do it with coercion, to a group of people who's entire field of study is covert communication, seems like an unenviable prospect.
Nobody says that (not that I've seen).
My reading is that he's a combative academic, railing against a standards body that refuses to say how they're working, with a deserved reputation for dishonesty and shenanigans.
Can I point out that Ted Kaczynski was also actually a mathematical prodigy, having been accepted into Harvard on a scholarship at 16?
1) single-handedly killed US government crypto export restrictions - Bernstein certainly litigated, but was not the sole actor in this fight. For example, Phil Zimmerman, the author of PGP, published the source code of PGP as a book to work around US export laws, which undoubtedly helped highlight the futility of labelling open source software as a munition: https://en.wikipedia.org/wiki/Pretty_Good_Privacy#Criminal_i...
2) Bernstein "founded" the field of post quantum cryptography: Uh. Ok. That's not how academia works. Bernstein was certainly an organiser of the first international workshop on post quantum cryptography, but that's not the same as inventing a field. Many of the primitives that are now candidates were being published long before this, McEliece being one of the oldest, but even Atjai's lattice reductions go back to '97.
3) The dual_ec rng was backdoored (previously read was and is fishy, poor wording on my part), but nobody at the time wanted NIST to standardize it because it was a _poor PRNG anyway_: slow and unnecessarily complicated. Here is a patent from Scott Vanstone on using DUAL_EC for "key escrow" which is another way of saying "backdoor": https://patentimages.storage.googleapis.com/32/9b/73/fe5401e... - filed in 2006. In case you don't know Scott Vanstone, he's the founder of Certicom. So at least one person noticed. This was mentioned in a blog post as a result of the Snowden leaks working out how the backdoor happened: https://blog.0xbadc0de.be/archives/155
NSA have been caught in a poor attempt to sabotage a standard that nobody with half a brain would use. On the other hand NSA also designed SHA-2, which you are likely using right now, and I'm not aware of anyone with major concerns about it. When I say NSA designed it, I don't mean "input for a crypto competition" - a team from the NSA literally designed it and NIST standardized it, which is not the case for SHA-3, AES or the current PQC process.
DJB is a good cryptographer, better than me for sure. But he's not the only one - and some very smart, non-NSA, non-US-citizen cryptographers were involved in the design of Kyber, Dilithium, Falcon etc.
I had the same take on Dual EC prior to Snowden. The big revelation with Snowden wasn't NSA involvement in Dual EC, but rather that (1) NSA had intervened to get Dual EC defaulted-on in RSA's BSAFE library, which was in the late 1990s the commercial standard for public key crypto, and (2) that major vendors of networking equipment were --- in defiance of all reason --- using BSAFE rather than vetted open-source cryptography libraries.
DJB probably did invent the term "post-quantum cryptography". For whatever that's worth.
I'll believe he invented the term - I have a 2009 book so-named for which he was an editor surveying non-DLP/non-RSA algorithms. Still, the idea that he's "the only one who can produce the good algorithms" and literally everyone else on the pqc list (even if we subtract all the NIST people) is wrong is bonkers.
>Still, the idea that he's "the only one who can produce the good algorithms"
The parent post did not, at all, make the claim that Bernstein is the only one.
> 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.
"Crappy" algorithms that were designed by well-regarded cryptographers, none of whom work for NIST or the NSA, many of whom are not US nationals.
Foreign nationals don't meet the "Unquestioning loyalty to the US" criterion for security clearance, meaning it is much less likely they might collaborate willingly with the US. They're also less exposed to pressure from the US Government, especially if they are not resident/GC holders.
I personally think it is quite paranoid to assume that any US resident or national cryptographer is in cahoots with the NSA but if we are strictly considering risks, then this process is open to scrutiny by world-wide participants, many of whom may not sit on a vulnerability at the behest of the US GOV - actually, for many of them, finding such a vulnerability would likely mean a top tier paper at CRYPTO/EUROCRYPT probably with best paper awards and all the plaudits that make an academic career for life.
How else do you explain the after-the-fact changing of evaluation criteria (all favoring one algorithm) and the weird calculation error (which as I understand the text didn't come from the Kyber designers but the evaluation committee)?
Add to that the lack of transparency in particular why not follow the FOI requests ? and the much more significant involvement of NSA employees in the process (contrary to their own statement). Shouldn't that make everyone very suspicious?
The evaluation criteria are, naturally, in a state of constant evaluation. It would make no sense to fix them in 2019, and never update them in response to research.
It seems that DJB is not necessarily representing what NIST is saying honestly with regards to security levels: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu... , https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu... - It also seems that the improved dual lattice attack from MATZOV (Israeli spooks) isn't actually as practical as thought: https://eprint.iacr.org/2023/302 (this paper was published in CRYPTO, which is purely run by academia, and top-tier academic at that). What actually the answer should be depends on various cost models, but the overall conclusion seems to be there is not a lot between Kyber and SNTRUP - on the other hand, it may be an open problem (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4iaf...).
Security bounds, however, are not the only reason to pick an algorithm. To take Curve25519, the prime order subgroup has order 2^252 + a bit, so it falls just short of the 128-bit security level. Should we reject it for this? Absolutely not: X25519 is excellent from an implementation perspective. This is more qualitative than quantitative, but such considerations also count.
Pointing out further notes by Peikert on SNTRUP, here is a detailed risk analysis: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/G0Do... with responses from others: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/G0Do... - to summarize: a) it seems the patent risk of Kyber might also apply to SNTRUP, and b) SNTRUP makes modifications over plain NTRU that are not clear. DJB also tried to argue against Kyber's performance: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/ik1p... . It is not clear that SNTRUP is necessarily a better choice either; quoting directly from NIST IR 8413 (note that the SIKE section is out of date; SIKE is definitively broken pre-quantum now):
> The current version of NTRU Prime has performance and concrete security estimates > (e.g., quantitative estimates of the computational resources required for usage and > cryptanalysis) that are roughly comparable to other lattice-based cryptosystems.13 As a > result, the current version of NTRU Prime is notable more for its unusual design features, > and claims that it offers higher security in a qualitative sense. > > One particular issue is the choice of the NTRU Prime ring (rather than a cyclotomic > ring), which is claimed to eliminate the possibility of certain kinds of algebraic attacks. > To date, most work on the cryptanalysis of algebraically structured lattices (see Appendix > C) has focused on cyclotomic rings, because they are widely used and simpler to analyze. > Relatively little is known about the security of cryptographic schemes that use the NTRU > Prime ring.
As for the involvement of NSA employees - they show up to NIST forums on standardization and take part in the process, and if you go, it isn't exactly hard to work out who they are. NSA also has an information assurance mission. If we take what is said in https://www.youtube.com/watch?v=qq-LCyRp6bU (Richard George, an NSA targeting retrospective) to be accurate then NSA Suite-A are almost drop-in replacements for NSA Suite-B (the algorithms mandated for use across US FedGov) so the NSA team have an interest in the outcome, because future choices of cryptography suites will follow on from what is standardized.
As for FOIA: if the NSA does know about a backdoor they don't think anyone else does, don't you think they'd classify it? Wouldn't that make it exempt from any FOIA lawsuit you care to raise? If we are attributing competence to them beyond what is available publicly, then surely they wouldn't be so careless as to discuss the backdoor they'd discovered in FOIA-able channels, would they?
I'm 100% for scrutinizing the process to make sure neither the NSA (nor anyone else) can sneak in a backdoor either deliberately or by allowing it to pass through unremarked. I am not convinced by DJB's writeup: I agree that NIST have a preference for Kyber, but I do not currently see any evidence that this is an unreasonable conclusion to arrive at, or that they have substantially ignored serious flaws in the design.
> However, this man is one of the foremost cryptographers in the world […]
It's possible to be both (not saying Bernstein is).
Plenty of smart folks have 'jumped the shark' intellectually: Ted Kaczynski, the Unabomber, was very talented in mathematics before he went off the deep end.
Kaczynski dropped out of society to live in a cabin alone at 29. He delivered his first bomb at 35. I'm not sure this is a reasonable comparison to invoke in any way whatsoever.
When DJB starts posting about the downfall of modern society from his remote cabin in Montana, perhaps, but as far as I know he's still an active professor working from within the University system.
If DJB is unhinged but similarly insightful about a crypto algo, I think we’d all be better off. Assuming he lays off the mailbombs anyway.
In this particular case it's worth noting that neither BSI (Germany) nor NLNCSA (The Netherlands) recommend Kyber.
Unfortunately, alternative algorithms are more difficult to work with due to their large key sizes among other factors, but it's a price worth paying. At Backbone we've opted not to go down the easy route.
Also, the schemes he’s railing against are also the work of top cryptographers in the space.
What worries me is that it'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.
It's hard to get good people these days. A lot of people stopped caring. Even amongst the young and eager. Whether it'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.
Maybe that's just my own fatigue, but in security we have to vigilant all the time and there's only so much energy humans can bring to that. That's why I worry that we will lose against AI. Not because it's smarter, but because it doesn't have to _care_, whereas we do.
There are a lot of symptoms to distract yourself with. Focus on the game instead.
A society full of good people will sort out the rest.
This is the lasting legacy of the Internet, now. Not freedom for all to seek and learn, but freedom for the negativity engines to seek out your brain and suck you into personal obliteration.
A society of good people? Nobody really cares any more. And I do agree with the gp; if you look, you can see it everywhere. What is this going to become? Collective helplessness as we eek out what little bits of personal fulfillment we can get in between endless tragedy and tantalizing promise?
Everything you listed is valid (through one lens), but they are symptoms. Distract yourself with symptoms and you'll never solve the problem.
Application Service Providers, as they exist today, are bad systems.
They provide tremendous value, that's why they exist. But they also carry tremendous cost. So far, nobody has solved the cost without compromising the value.
If you want to fix the web, moving us closer to a free and open web, stay hyper focused on solving the cost without compromising the value.
First past the post voting is a bad system.
In the U.S. you don't solve politics by voting for candidates, that's treating symptoms.
If you are a staunch republican, vote republican. If you are a staunch democrat, vote democrat.
Everyone else should be hyper focused on one thing: ballot reform.
If you want to solve the problem, focus on the game and solve it. A society full of good, but currently defeated, people will do the rest.
First-past-the-post is one of the objectively worst, seemingly sensible, voting systems.
https://en.wikipedia.org/wiki/First-past-the-post_voting#Vot...
The NSA is very good at math, so I'm be thoroughly surprised if this analysis was error by mistake rather than error through intent.
Which is generally known, so I'm surprised by your argument. Even if the NSA knows more than they are telling us, this doesn't result in most of us feeling less worried, as their ends may not be strengthening the public's cryptography!
I have no reason to doubt that a lot of math has been made more difficult than necessary just because it is known to give a subtle military advantage in some cases, but this isn't new;
Also, we still to this day do not know where the seed for P256 and P384 came from. And we're using that everywhere. There is a non-zero chance that the NSA basically has a backdoor for all NIST ECC curves, and no one actually seems to care.
In my mind's eye, it's cooler: it's like, you render the ciphertext as a raster image, and then "de-lattice" it to reveal the underlying plaintext, scanline by scanline.
but i can imagine, based on my own ignorance, creativity, and lack of correct understanding, would be some kind of factorization.
as I think while trying to better know what's a lattice, I imagine a lattice like a coordinate pair, but instead of each coordinate existing on a line, they exist on a binary tree (or some other directed graph explored from a root outwards without cycles)
which means you have two such binary-trees (not necessarily binary, but it's just easier to work with them seemingly)
and then you combine these into ONE lattice. so then, to de-lattice means to recover the binary trees.
but when I say binary tree I'm thinking about rational numbers (because stern broccott trees)
Somebody would leak or steal that as it would be a GIGANTIC leap forward in our engineering skill at the quantum level.
Getting more than a handful of qubits to stay coherent and not collapse into noise is a huge research problem right now, and progress has been practically non-existent for almost a decade.
If your codebase is hairy enough, and the problem to be solved is fundamentally fairly simple, sometimes it's better to rewrite than refactor. Doubly so if you believe a clever adversary has attempted to insert a subtle backdoor or bugdoor.
What would a better crypto selection process look like? I like the idea of incorporating "skin in the game" somehow... for example, the cryptographer who designs the scheme could wager some cash that it won't be broken within a particular timeframe. Perhaps a philanthropist could offer a large cash prize to anyone who's able to break the winning algorithm. Etc.