Comment by ziddoap

2 years ago

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.

6 comments

ziddoap

Reply
zahllos  2 years ago

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 of whom are not US nationals.

  • cycomanic  2 years ago

    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 ? and the much more significant involvement of NSA employees in the process (contrary to their own statement). Shouldn't that make everyone very suspicious?

    • zahllos  2 years ago

      It is NIST's competition. They've been open that if there are good reasons not to standardize Kyber then they won't, but, absent good reasons then they'll pick what they want.

      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.