[TLS] Re: WG Last Call: draft-ietf-tls-mlkem-05 (Ends 2025-11-26)

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

John Mattsson writes:
> Dan Bernstein wrote:
> > ECC+PQ has roughly the same performance properties as non-hybrid PQ
> This is not correct. A hybrid such as X25519 + ML-KEM requires
> substantially more cycles and code size than standalone ML-KEM.

All of the complexity arguments in favor of this draft (e.g., code-size
arguments) are getting the situation backwards, as Andrey Jivsov pointed
out during the adoption call. The draft adds PQ as an _extra_ option
_beyond_ ECC+PQ, so it _increases_ the complexity of TLS software.

For example, one advertisement we've heard for this draft is that
OpenSSL added an implementation of the draft. Did this remove the X25519
code from OpenSSL? Of course not. It's wrong to portray the draft as
reducing code size; that's simply not what the draft does.

As for per-connection costs (such as cycles), let's look at the numbers.
https://blog.cr.yp.to/20240102-hybrid.html reviews how to do an X25519
key exchange for roughly 2^-34 dollars of computation (per side) plus
roughly 2^-34 dollars of network traffic (per side). It continues as
follows: "Sending an 800-byte key and receiving a 768-byte ciphertext
for the smallest Kyber option, Kyber-512, costs roughly 2^-29 dollars.
Including X25519 adds roughly 7% to that."

How, then, would one argue that X25519+ML-KEM-512 _doesn't_ have roughly
the same per-connection cost as non-hybrid ML-KEM-512? Sure, people will
have different ideas of what the dividing line is for "roughly", but the
gap in this case is _really_ small. (And even slightly smaller when one
replaces ML-KEM-512 with ML-KEM-768.)

Obviously one can tilt the comparison, maybe even enough to turn 7% into
something that sounds like a big deal, by selecting some tiny CPU (to
pump up the computation costs) attached to high-end network equipment
(to avoid pumping up the networking costs). But corner cases can't
contradict "roughly the same performance properties".

The performance differences between ECC+PQ and PQ are even less
noticeable in the context of overall application costs. For example,
at Meta, only 1 out of every 2000 CPU cycles is used for ECC, so the
computation cost of ECC (and also of ECC+PQ with typical PQ choices) is
roughly 0.

> > This document was introduced in pursuit of "CNSA 2.0 compliance"
> That claim

"Claim"? This is a direct quote from

    https://web.archive.org/web/20250613195524/https://mailarchive.ietf.org/arch/msg/tls/qFRxBSnEPJcdlt7MO0cIL2kW5qc/

which was the motivation statement straight from the document author at
the time of introducing the document. That statement went on to cite

    https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF

which at the time was the 2022 version of NSA's CNSA 2.0 PDF; NSA
doesn't maintain stable URLs but

    https://web.archive.org/web/20220908002358/https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF

has an archived copy.

> is contradicted by the inclusion of ML-KEM-512 and ML-KEM-768

I already pointed out other flaws in the CNSA 2.0 compliance argument.
Most importantly, the compliance claim is flatly contradicted by NSA's
official CNSA 2.0 PDF saying "hybrid solutions may be allowed or
required due to protocol standards". See the last URL above, or

    https://web.archive.org/web/20250827175413/https://media.defense.gov/2025/May/30/2003728741/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS.PDF

which is an archived copy of NSA's official 2025 update of the CNSA 2.0
PDF.

This doesn't change the fact that the document was introduced in pursuit
of "CNSA 2.0 compliance", as I said. I don't understand how you think
you're contradicting this. The fact that there's a flaw in the stated
motivation doesn't mean that it isn't what was stated.

> the large X25519MLKEM768 key shares causes many legacy middleboxes to
> reject the connection. In such environments, I think it is preferable
> to rely on ML-KEM-512

Even assuming, arguendo, that 1184 bytes for ML-KEM-768 cause "many"
problems, that 800 bytes for ML-KEM-512 do much better, and that this
outweighs the additional risks of ML-KEM-512, how is this supposed to be
an argument for omitting the X25519 part? Are you claiming that there's
a big difference in rejection rates between 800 bytes and 832 bytes?

---D. J. Bernstein


===== NOTICES =====

This document may not be modified, and derivative works of it may not be
created, and it may not be published except as an Internet-Draft. (That
sentence is the official language from IETF's "Legend Instructions" for
the situation that "the Contributor does not wish to allow modifications
nor to allow publication as an RFC". I'm fine with redistribution of
copies of this document; the issue is with modification. Legend language
also appears in, e.g., RFC 5831. For further background on the relevant
IETF rules, see https://cr.yp.to/2025/20251024-rules.pdf.)