[TLS] Re: [EXT] Re: Concerns about the current draft.

[John Mattsson <[e-mail]>]

NIST has typically used terms like "computational resources comparable to or greater" and  "highly unlikely that the known sources of uncertainty are large enough to make Kyber512 signifcantly less secure than AES128" [1-2].

Ragarding 2022/1750, there has already been a lengthy discussion on PQC forum, where you accused NIST of being stupid and not being able to count [3]. The majority of PQC forum agreed with NIST. The only thing that should be withdrawed are your personal attacks on the NIST cryptography team.

The new de facto standard is X25519MLKEM768, which has a very large practical security margin. The applications of ML-KEM-512 would be IoT or maybe resumption, where it is a very appropriate choice.

[1] https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

[2] https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/faq/Kyber-512-FAQ.pdf

[3] https://blog.cr.yp.to/20231003-countcorrectly.html

Cheers,
John

From: D. J. Bernstein <[e-mail]>
Date: Saturday, 30 August 2025 at 00:58
To: [e-mail] <[e-mail]>
Subject: [TLS] Re: [EXT] Re: Concerns about the current draft.
> > One of the talks at Crypto 2025 last week said that none of the Kyber
> > parameters meet their claimed security levels.
> Details and specifics, please?

The paper is a recent update of https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Feprint.iacr.org%2F2022%2F1750&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C84aa96b51e3142504b1108dde74f9dbe%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638921051328811744%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=CyPUk%2FsrE0d0wyU3Hqc5pcv4tXbqix1UnxT1CU80tC0%3D&reserved=0:<https://eprint.iacr.org/2022/1750> "the
security levels for Kyber-512/768/1024 are 3.5/11.9/12.3 bits below the
NIST requirements (143/207/272 bits) in the same nearest-neighbor cost
model as in the Kyber submission".

The numbers should have been reported as ranges: analyzing the costs of
known lattice attacks actually involves many uncertainties that together
can push the security levels up or down by >10 bits. For the same
reason, I agree with a comment "there remains a few bits to be gained by
cryptanalysts before the security levels would be convincingly crossed"
from a member of the Kyber team in April. But the same analysis fog,
together with the attack improvements, means that Kyber could have even
_lower_ security levels against the paper's attack than the paper says,
never mind further attack improvements.

The Kyber team's last security analysis was in 2021 and claimed 151 bits
plus or minus various uncertainties. This new paper just a few years
later is >10 bits better. This _isn't_ from the originally identified
uncertainties being resolved in a way that happened to be unlucky for
Kyber. Specifically, the 2021 analysis

    https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fweb.archive.org%2Fweb%2F20230310174959%2Fhttps%3A%2F%2Fpq-crystals.org%2Fkyber%2Fdata%2Fkyber-specification-round3-20210804.pdf&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C84aa96b51e3142504b1108dde74f9dbe%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638921051328833590%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=A0%2FnrZqUkSvTt40piWWndCAMN%2FzZl7Ofy9JI%2FbPvzYM%3D&reserved=0<https://web.archive.org/web/20230310174959/https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf>

said "Our first point is that, while the core-SVP hardness methodology
suggest that the dual attack is slightly cheaper than the primal one, it
is in fact significantly more expensive"; the new paper is a much faster
dual attack (and avoids the disputes about some earlier dual attacks).
Primal attacks have also improved by >10 bits, for example via "hybrid"
attacks; the 2021 analysis had portrayed those attacks as merely
threatening "very low noise" and not Kyber.

Dismissing the advances here because the attack costs haven't reached
the demo level yet is the same conceptual mistake as dismissing quantum
computation because Shor's algorithm hasn't been demonstrated on any
real examples yet. One can, of course, hope for the advances to stop,
but this doesn't mean one should be blind to the advances.

In any event, Kyber's original security claims are not justifiable
today. For the same reason, NIST should withdraw its claims that ML-KEM
is as hard to break as AES-128/192/256.

---D. J. Bernstein

_______________________________________________
TLS mailing list -- [e-mail]
To unsubscribe send an email to [e-mail]