[TLS] Re: WG Last Call: draft-ietf-tls-mlkem-08 (Ends 20 26-07-08)

Hi Viktor,

On 7/8/26 08:04, Viktor Dukhovni wrote:
> On Tue, Jul 07, 2026 at 10:27:56PM -0700, Christian Huitema wrote:
> 
>> I just read Jacob Applebaum's message. Given his description of the
>> late-standardization suspicious change that looks like a backdoor in the
>> ML-KEM specification, I agree with his conclusion. The WG should not ask for
>> publication of the current graph, not until the changes requested by Jacob
>> are made.
> 
> The removal of whitening of the `m` random input to Encaps is not a
> plausible backdoor. 

I note that you do not dispute that it is a plausible covert channel. It 
does not appear to be in dispute that this covert channel is only 
possible by removing the hash over `m`. I called this a `backdoor 
accommodation` and not a `backdoor` in my official comments to NIST in 
2023. The trick I have described requires "mistakes" at multiple layers. 
This kind of problem coincidentally diffuses responsibility so that 
involved parties may plausible simply shrug at the resulting security 
issues. I encourage the IETF to not shrug but to mitigate as the 
original Kyber designers intended.

It is my understanding from a Kyber author that _not_ using the system 
RNG directly was an explicit goal, and that the hash was put into Kyber 
_exactly_ to stop this kind of covert channel from being used by a 
Dual_EC_DRBG-shaped kleptographic construction.

That same author of Kyber explained to me that NIST motivated removal of 
the hash over `m` by discussing the analysis of ML-KEM together with a 
secure RNG considered together as one primitive. Thus the hash function 
wouldn't be needed because by definition, `m` was always going to be 
safe. It is very logical and it appeals to a notion of efficiency. It is 
also dangerous and it is certainly not worth the risk given the history.

> If all you have is a broken RNG, you're free to
> apply whitening to obtain a new less bad RNG and use that instead.
> 

If a client has a broken RNG then its ephemeral ML-KEM key pair is at 
risk, indeed. However, if the server has a _sabotaged_ RNG which is a 
special class of RNG failures relevant to the IETF's history with 
Dual_EC_DRBG, any TLS client can obtain ciphertexts derived from fresh 
server RNG output with this change.

Let us assume that the RNG in question is Dual_EC_DRBG or a similar 
kleptographic construction. An implementation of Dual_EC_DRBG with the 
NIST SP 800-90A points is still present today in at least one widely 
deployed cryptographic library, as I cited in my previous email. I trust 
that this isn't in dispute. That same library implements ML-KEM but it 
does not appear to use Dual_EC_DRBG by default, thankfully.

Unfortunately, the Dual_EC_DRBG kind of sabotage becomes exploitable 
exactly because of NIST's removal of the hash function. What is 
interesting is that when ML-KEM is used in TLS 1.3, then the client is 
able to obtain ML-KEM ciphertexts derived from fresh server RNG output; 
because the client generated the corresponding ephemeral decapsulation 
key and can instrument its own decapsulation, it can recover the 
internal `m` value chosen by the server encapsulation.

The client can repeat this process many times, and such queries look 
like ordinary TLS 1.3 ML-KEM handshakes. This is almost an ideal 
cryptographic oracle and querying it will blend in with normal TLS 1.3 
ML-KEM protected traffic.

If the recovered `m` value leaks enough RNG state in one go, any client 
that can exploit Dual_EC_DRBG will be able to do so once it has 
accumulated enough bits. As it just so happens, ML-KEM's `m` is 32 bytes 
and a suitably truncated 30-byte value can be enough with roughly ~2^16 
trial work in the classic Dual_EC_DRBG P-256 recovery setting.

If the `m` value was hashed, this would not be possible.

So is that an issue with ML-KEM or TLS 1.3's use of ML-KEM?

The answer is that _NIST_ had to change Kyber's design for this result, 
and thus TLS 1.3 should take this reality into account. Together we see 
the practical result.

> Nothing stops an ML-KEM implementation from hashing some input (any
> number of times, mixing in whatever additional inputs, ...) to produce
> its random values. 

The patent situation may make this less simple for implementers than it 
sounds; some implementers will be reluctant to deviate from the exact 
standardized algorithm and associated IPR terms. That may stop many 
implementers from deviating from the standardized algorithm.

Please see FIPS 203 Section 6.2, Algorithm 17, and the informal 
description below it and FIPS 203 section 7.2, Algorithm 20. Algorithm 
20 specifically notes that readers should read Section 3.3. On page 15 
in Section 3.3, NIST states: "While conforming implementations must 
adhere to all of these requirements, adherence does not guarantee that 
the result will be secure" and goes on to say on page 16:

"Randomness generation. Two algorithms in this standard require the 
generation of randomness as an internal step: ML-KEM.KeyGen and 
ML-KEM.Encaps. In pseudocode, this randomness generation is denoted by a 
statement of the form 𝑚 ←− 𝔹32 . A fresh string of random bytes
must be generated for every such invocation. These random bytes shall be 
generated using an approved RBG, as prescribed in SP 800-90A, SP 
800-90B, and SP 800-90C [18, 19, 20]. Moreover, this RBG shall have a 
security strength of at least 128 bits for ML-KEM-512, at least 192 bits 
for ML-KEM-768, and at least 256 bits for ML-KEM-1024."

Notably, this NIST statement from FIPS 203 cites SP 800-90A, whose 
earlier history is directly relevant to this concern. That is the very 
publication that used to contain Dual_EC_DRBG until public reporting on 
the Snowden documents connected Dual_EC_DRBG to the broader PROJECT 
BULLRUN context. NIST presumably means to cite the latest SP 800-90A 
without the widely reported cryptographic sabotage associated with 
Dual_EC_DRBG. Note however again that just because an implementation 
conforms to all of the requirements, they don't guarantee that the 
result will be secure. I think it is fair to read that as saying they 
also don't guarantee that the results will be secure if you deviate from 
meeting the standard's requirements.

Additionally please see page 47 of Appendix C section C.1 and please 
carefully read all four bullet points. NIST says in C.1 that it is 
_required_ to use NIST-approved randomness generation.

Why do their requirements matter? The patent/IPR situation is one 
reason. FIPS 203 explicitly says NIST entered into two patent license 
agreements to facilitate adoption of CRYSTALS-Kyber/ML-KEM.

What do nearly all ML-KEM implementations do as a result? Most 
implementations removed the hash over `m` as NIST's changes to the 
specification _require_ if you implement it "correctly" following their 
change to `ML-KEM.Encaps`. They define ML-KEM, after all.

 > The abstract algorithm starts from the final output> of an adequate 
RNG that requires no further post-processing.
> 

I do not think FIPS 203 supports that distinction. That distinction 
seems to be a semantic game because the "abstract algorithm" is defined 
by FIPS 203. That's ML-KEM, full stop.

NIST changed Kyber’s Encaps() Algorithm 8 [0] by removing the hash over 
`m`; in FIPS 203, public ML-KEM.Encaps samples `m` and passes it to 
`ML-KEM.Encaps_internal()`. NIST freely states this fact which is not in 
dispute. In "Kyber.CCAKEM.Enc" defined in Algorithm 8 Kyber's designers 
directly stated on page 9 "Do not send output of system RNG" - this 
statement remains in the second round design [1], in the third round 
design document [2], in version 3.01 [3], and in version 3.02 [4]. I 
assume you are familiar with the relevant specifications.

NIST does not claim that their change isn't to "the abstract algorithm" 
but rather they simply justify it as secure by qualifying it with a 
requirement. That NIST requirement isn't explicitly stated as required 
in the draft under discussion, why not? Isn't that requirement why some 
of the Kyber team found this to be an acceptable change?

Furthermore, what you're calling "the abstract algorithm" is a 
distinction that does not address the practical consequences of this 
change by NIST in finalizing FIPS 203. That change was _required_ to 
make this exploitable as described. I strongly think the Kyber team 
should not have accepted this change from NIST. This change means that 
the intended security of ML-KEM can be practically bypassed without 
attacking the lattice hardness assumptions. It also has knock-on effects 
for subsequent secrets of any cryptographic primitive used after `m` is 
sampled from the system RNG.

Your analysis is also ignoring that patent licenses are an extremely 
important motivator for a handful of important implementations. Are you 
asserting that variants of `ML-KEM.Encaps()` that restore `m ← H(m)` 
would be covered by the NIST patent license? If so, on what basis do you 
claim that? Such a conclusion would be positive news and indeed, we 
could simply put the hash on `m` again, and be done with the topic.

> There's nothing suspicious about this simplification.  

The original Kyber design included the hash, and the public Kyber 
specification says "Do not send output of system RNG." Removing that 
step reopens exactly the class of RNG-output channel that this line 
avoided. See page 10 for algorithm 8, step 2 "m ← H(m)" which again is 
noted as "Do not send output of system RNG" in the Algorithm definition.

> The critique in
> question makes no sense to me.

That right there is the crux of the issue! Do you need to see an 
implementation with working exploit?

 > Don't use a broken RNG.>

You can use a good one, and the server can use a bad one _without 
knowing it_ because that is how cryptographic sabotage is deployed in 
the real world. Things get worse in the Encrypted Client Hello (ECH) 
scenario as both sides sample the other's respective system RNG by 
ensuring both sides send a ciphertext produced by ML-KEM.Encaps().

The most obvious fix is simple: Fix ML-KEM.Encaps by restoring the `m ← 
H(m)` step before `ML-KEM.Encaps_internal()` is called. The draft could 
easily state this as a concrete security mitigation exactly to avoid 
even the mere appearance of the Dual_EC_DRBG/Extended Random situation 
repeating.

Kind regards,
Jacob Appelbaum

[0] https://pq-crystals.org/kyber/data/kyber-specification.pdf
[1] https://pq-crystals.org/kyber/data/kyber-specification-round2.pdf
[2] https://pq-crystals.org/kyber/data/kyber-specification-round3.pdf
[3] 
https://pq-crystals.org/kyber/data/kyber-specification-round3-20210131.pdf
[4] 
https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf

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