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]
