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

[John Mattsson <[e-mail]>]

Dan Bernstein wrote:
>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.

TLS libraries such as wolfSSL, Mbed TLS, and BearSSL allow you to choose exactly which components are compiled. For very constrained systems, you typically enable as few algorithms as possible, since storage is often a primary limitation. In these environments, standalone ML-KEM certainly reduces code size, i.e., the size of the compiled binary, compared to ECC+PQ. In constrained systems, I think standalone ML-KEM-512 can be the best option when migrating to PQC.

>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?

I have not made any claims about per-connection cost. You argued that “ECC+PQ has roughly the same performance properties as non-hybrid PQ,” and I pointed out that this is incorrect when you consider cycle counts and code size.

>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.)

This is not correct. On the platform Cloudflare is using, the difference in cycle counts is far from small. ML-KEM-768 is more than twice as fast as X25519.
https://blog.cloudflare.com/pq-2025/#ml-kem-versus-x25519

Whether this performance gain matters is a separate question. For non-constrained environments such as the Web, I agree that the cost is negligible, and in any case, the extra cycles are worthwhile until we have more thoroughly hardened ML-KEM implementations. However, some people on this list have claimed that, for performance reasons, they intend to reuse “ephemeral” X25519MLKEM768 key shares, despite this violating FIPS 203. But likely most instances of static keys in TLS 1.3, are motivated by discouraged interception practices rather than by performance concerns. I think standalone ML-KEM with its superior performance is a good argument against people arguing that key reuse is needed for X25519MLKEM768.

Beyond the substantial security and privacy vulnerabilities, the TLS WG should consider how reuse of ephemeral key shares aligns with the NIST statement that “the licensed patents be freely available to be practiced by any implementer of the ML-KEM algorithm as published by NIST,”. I don't think the IETF should publish any RFC suggesting implementations may skip NIST requirements.

>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?

There is likely no meaningful difference in rejection rates between 800 bytes and 832 bytes. As I have said on the list, I would have liked to see an X25519MLKEM512 option. However, the current situation is that the TLS WG has decided to work only on X25519MLKEM512, SecP256r1MLKEM768, SecP384r1MLKEM1024, ML-KEM-512, ML-KEM-768, and ML-KEM-1024. Among these, only ML-KEM-512 passes through legacy middleboxes. In an ideal world, all of these middleboxes would be updated or replaced. But based on past experience, many of them will likely remain in service for decades. This means that without ML-KEM-512 (or X25519MLKEM512), we will not only need to support, but also actively use, quantum-vulnerable algorithms for far longer than I would like.

Cheers,
John Preuß Mattsson

From: D. J. Bernstein <[e-mail]>
Date: Wednesday, 26 November 2025 at 13:36
To: [e-mail] <[e-mail]>, [e-mail] <[e-mail]>, [e-mail] <[e-mail]>
Subject: [TLS] Re: WG Last Call: draft-ietf-tls-mlkem-05 (Ends 2025-11-26)

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://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fblog.cr.yp.to%2F20240102-hybrid.html&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C46ecbd763485447d571608de2ce86949%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638997573914181259%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=eZ3200H4PIGn4UpewRuwPY96KbNSi2NUq5j5UflLcpQ%3D&reserved=0<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://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fweb.archive.org%2Fweb%2F20250613195524%2Fhttps%3A%2F%2Fmailarchive.ietf.org%2Farch%2Fmsg%2Ftls%2FqFRxBSnEPJcdlt7MO0cIL2kW5qc%2F&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C46ecbd763485447d571608de2ce86949%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638997573914207599%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=hFehDW5CQTQmogHBhRS4h3OXq0WgKtbVoIgbbNEibQE%3D&reserved=0<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://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fmedia.defense.gov%2F2022%2FSep%2F07%2F2003071834%2F-1%2F-1%2F0%2FCSA_CNSA_2.0_ALGORITHMS_.PDF&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C46ecbd763485447d571608de2ce86949%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638997573914229395%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=6t2JJFaJQ82MQpV5OHXjAS%2BHUW3DCPXuwOdSi4TfTSs%3D&reserved=0<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://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fweb.archive.org%2Fweb%2F20220908002358%2Fhttps%3A%2F%2Fmedia.defense.gov%2F2022%2FSep%2F07%2F2003071834%2F-1%2F-1%2F0%2FCSA_CNSA_2.0_ALGORITHMS_.PDF&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C46ecbd763485447d571608de2ce86949%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638997573914249729%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=OtkS64JwAVNlstU7%2B0LWzvI2hJmGnZbSoJi7eacbx34%3D&reserved=0<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://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fweb.archive.org%2Fweb%2F20250827175413%2Fhttps%3A%2F%2Fmedia.defense.gov%2F2025%2FMay%2F30%2F2003728741%2F-1%2F-1%2F0%2FCSA_CNSA_2.0_ALGORITHMS.PDF&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C46ecbd763485447d571608de2ce86949%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638997573914266316%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=UI4f2pLeBrq%2FY1fL39dg0bK5hjJnHsj%2Ba2pJ3gsl%2B1M%3D&reserved=0<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://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fcr.yp.to%2F2025%2F20251024-rules.pdf&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C46ecbd763485447d571608de2ce86949%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638997573914282493%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=RvOOiKVdC9zhJyzsZc5cwsLHXT4ktb6ruudF7UGvi0c%3D&reserved=0.)<https://cr.yp.to/2025/20251024-rules.pdf>

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