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

["D. J. Bernstein" <[e-mail]>]

> > 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://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://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