Earlier quoted context omitted.
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…
Debunking NIST's calculation of the Kyber-512 security level
161–170 of 219 posts
Re: Debunking NIST's calculation of the Kyber-512 security level
#162Re: Debunking NIST's calculation of the Kyber-512 security level
#163Earlier quoted context omitted.
Re: BLAKE2, I'm not sure it's fair to say that BLAKE2 is more widely used overall. But I do agree BLAKE2 is a bit of an outlier in terms of adoption. I think part of the reason is that SHA2 remains the go-to option, else I'd expect the ecosystem to consolidate around SHA3. 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 prim…
> I'm not sure it's fair to say that BLAKE2 is more widely used overall 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…
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!
Re: Debunking NIST's calculation of the Kyber-512 security level
#164The 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 r…
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.
Re: Debunking NIST's calculation of the Kyber-512 security level
#165Earlier quoted context omitted.
> I'm not sure it's fair to say that BLAKE2 is more widely used overall 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…
I wish chip makers would bake the elliptic curve used in Bitcoin and Ethereum (secp256k) as well, instead of the entire industry coalescing around secp256r, which many suspect was somehow weaker (since its parameters are some weird large number X instead of a hard-to-game number like 15, leading some to believe that the first X-1 candidates were tried and X was found to be weaker). The real reason I would have liked…
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!
Re: Debunking NIST's calculation of the Kyber-512 security level
#166Earlier quoted context omitted.
While I agree with a lot of what you have said, > 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 .
No, true, the post did not explicitly state this. However the post did suggest that NIST is specifically out to get him and take a swipe at the other candidates: > 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…
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?
Re: Debunking NIST's calculation of the Kyber-512 security level
#167An 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 colla…
Correct me if I'm wrong, everything is also being done out in the open for everyone to see. The NIST aren't using some secret analysis to make any recommendations.
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"
Re: Debunking NIST's calculation of the Kyber-512 security level
#168Notwithstanding DJB's importance to cryptography, and the fact that I'm ignorant of a large number of details here, there was a point where he lost a lot of credibility with me. 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…
FWIW, there are two NTRUs: the original one, which had no djb involvement, and NTRU Prime, which does.
Re: Debunking NIST's calculation of the Kyber-512 security level
#169The 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 r…
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 fac…
Re: Debunking NIST's calculation of the Kyber-512 security level
#170Earlier quoted context omitted.
No, true, the post did not explicitly state this. However the post did suggest that NIST is specifically out to get him and take a swipe at the other candidates: > 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…
The evidence seems to at least point to NIST trying to get selected one specific algorithm selected. 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…
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.