I agree, 2^128 is a physically impossible lookup table, and 2^-64 is an unusually conservative bound.
For comparison, we usually say at most 2^32 messages should be encrypted with a 96-bit random nonce, to keep the probability of collisions to 2^-32. If we targeted 2^-64 we'd have to limit messages to 65,536. We should say nothing, or that ML-KEM is not vulnerable to practical multi-target attacks, which is what we generally say about e.g. random 256-bit keys. 2026-02-28 03:11 GMT+01:00 Joshua <[email protected]>: > Hi, > > To confirm I'm reading this right: The attack described is akin to a preimage > attack on a 256-bit space, that is if we send 2^64 hashes to an attacker with > a rainbow table of size 2^128, there is a probability of 2^-64 that the > attacker has that hash in the rainbow table? And inversely, if we send 2^64 > hashes to an attacker, then they will learn a preimage after 2^192 operations > on average? I'd think this is thoroughly in fantasy-land as far as attacks > go. My interpretation of their goal with 'salted' FO is to create domain > separation between each ciphertext such that a fantasy-sized rainbow table > does not work by simply increasing the message space with a public salt > value. This is more relevant for KEMs which use smaller message spaces, eg > 128 bits, where a 2^64 brute force aiming to hit any of 2^64 ciphertexts is > on shakier footing in terms of feasibility. > > I'm not sure we want to say "don't use ML-KEM more than 2^128 times with the > same key" when the attack itself is of complexity greater than 2^128. If I > were writing this, and I had to say something, I would say that "ML-KEM has a > message space of 256 bits and is thus not vulnerable to practical > multi-target attacks", and use a warning such as "<KA> has a message space of > 128 bits, and long-lived keys are vulnerable to multi-target attacks. Public > keys SHOULD NOT be used to encapsulate more than 2^64 ciphertexts." for KEMs > that use 128-bit messages. > > So I would personally chip in my vote for dropping the 2^64 ciphertext limit > and just treating it as a standard 256-bit keyspace. If anything, I think > it'd create more confusion by implying there is actually a practical attack > once that 2^64 threshold is passed, when there is in fact no feasible > (known!) attack. > > Best, > Joshua Nabors. > > On Friday, February 27th, 2026 at 4:33 PM, Deirdre Connolly > <[email protected]> wrote: > > > I'm reupping this question to the group as there's been a lot of traffic on > > this subject line. > > > > TL;DR: Do people want to omit any mention of key reuse, implicitly relying > > on 8446, or include this ~2^64 bounds analysis in some succinct way? > > > > > > This document cannot override RFC 8446(bis), which allows key reuse, but > > the bis now says SHOULD NOT reuse. We currently do not have a good citation > > with numbers on how many is too many reuses for ML-KEM as specified in FIPS > > 203 (not for generic Ring-LWE schemes as done in prior work, which ML-KEM > > isn't— it is a Module-LWE scheme with the FO transform applied). We > > currently gesture at any future analyses that come out. > > > > ML-KEM is of course designed to be IND-CCA, but the multi-target security > > (specifically multi-ciphertext, or multi-challenge) is a distinct property > > that is relevant to a reused keypair, where the collision-resistance in the > > KEM/PKE message space is pertinent. https://eprint.iacr.org/2025/343.pdf > > includes a quick analysis of ML-KEM, saying: > > > > "Targeting 256 bits of security: ML-KEM has 3 variants, targeting 128, 192, > > or 256 bits of security, but all of these use 256-bit messages [Nat24]. We > > note that the parameter nc should not change for the various targeted > > security levels, as it represents a threshold on the amount of times the > > same public key will be used for encapsulation in practical deployments. We > > observe that, > > if one targets 256 bits of security, collision finding attacks become > > relevant again, since an adversary generating 2^128 ciphertexts will find a > > collision with one of 2^64 challenge ciphertexts with probability about > > 2^−64. Thus without salting, even ML-KEM-1024 can only achieve 192 bits of > > multi-target security in the random oracle model." > > > > This appears to indicate an upper bound of reuses for all ML-KEM parameter > > sets to 2^64 (if I'm parsing this wrong, someone correct me). > > > > On Wed, Feb 25, 2026 at 4:23 AM Deirdre Connolly <[email protected]> > > wrote: > > > > > > My constructive suggestion is to remove all text regarding static keys, > > > > as there is no reason for this draft to include them > > > This document cannot override RFC 8446, which allows key reuse. We > > > currently do not have a good citation with numbers on how many is too > > > many reuses for ML-KEM as specified in FIPS 203 (not for generic Ring-LWE > > > schemes as done in prior work, which ML-KEM isn't— it is a Module-LWE > > > scheme with the FO transform applied). We currently gesture at any future > > > analyses that come out. > > > > > > ML-KEM is of course designed to be IND-CCA, but the multi-target security > > > (specifically multi-ciphertext, or multi-challenge) is a distinct > > > property that is relevant to a reused keypair, where the > > > collision-resistsnce in the KEM/PKE message space is pertinent. > > > https://eprint.iacr.org/2025/343.pdf has some nice analysis of such > > > security of salted-FO KEMs (Ml-KEM is not salted) but also include a > > > quick analysis of ML-KEM, saying: > > > > > > "Targeting 256 bits of security: ML-KEM has 3 variants, targeting 128, > > > 192, or 256 bits of security, but all of these use 256-bit messages > > > [Nat24]. We > > > note that the parameter nc should not change for the various targeted > > > security levels, as it represents a threshold on the amount of times the > > > same public key will be used for encapsulation in practical deployments. > > > We observe that, > > > if one targets 256 bits of security, collision finding attacks become > > > relevant again, since an adversary generating 2^128 ciphertexts will find > > > a collision with one of 2^64 challenge ciphertexts with probability about > > > 2^−64. Thus without salting, even ML-KEM-1024 can only achieve 192 bits > > > of multi-target security in the random oracle model." > > > > > > This appears to indicate an upper bound of reuses for all ML-KEM > > > parameter sets to 2^64 (if I'm parsing this wrong someone correct me). > > > > > > Do people want to omit any mention of key reuse, implicitly relying on > > > 8446, or include this bounds analysis in some succinct way? > > > > > > On Wed, Feb 25, 2026, 2:31 AM John Mattsson > > > <[email protected]> wrote: > > > > > > > Hi > > > > > > > > I received an offline comment from a senior IETF participant suggesting > > > > that I had misunderstood the draft and that the key reuse in question > > > > referred to reuse within a single session. That is not accurate. The > > > > draft talks about static keys, i.e., keys used in more than one > > > > key-establishment. > > > > > > > > Given the apparent confusion between 1. reuse of ephemeral keys within > > > > a session, 2. reuse of ephemeral keys across sessions, and 3. static > > > > keys, each of which carries distinct privacy and security implications, > > > > I recommend that the AD ensure that all not yet published drafts use > > > > very precise terminology. Specifically, a key used in more than one > > > > key-establishment should use the well-established term “static key”. > > > > > > > > --- > > > > > > > > 1. Reuse of ephemeral keys within a session: > > > > > > > > - Session A: ClientHello with MLKEM768 KeyShareEntry1 and > > > > X25519MLKEM768 KeyShareEntry2 both containing the same ML-KEM public > > > > key. > > > > > > > > 2. Reuse of ephemeral keys across sessions: > > > > > > > > - Session B1. ClientHello with MLKEM768 KeyShareEntry3 and X25519 > > > > KeyShareEntry4. Sever picks X25519 KeyShareEntry4. > > > > > > > > - Session B2. ClientHello with MLKEM768 KeyShareEntry3 and X25519 > > > > KeyShareEntry5. > > > > > > > > 3. Static keys > > > > > > > > - Session C1. ClientHello with MLKEM768 KeyShareEntry6. Sever picks > > > > MLKEM768 KeyShareEntry6 > > > > > > > > - Session C2. ClientHello with MLKEM768 KeyShareEntry6. Sever picks > > > > MLKEM768 KeyShareEntry6 > > > > > > > > --- > > > > > > > > Issues with the text on static keys were clearly raised during the > > > > first WGLC and should have been addressed before the second. Having to > > > > repeat the same issues is both frustrating and a waste of time. > > > > > > > > The major issues, that the draft lacks proper security considerations > > > > for the use of static keys (they should be quite negative), and that it > > > > does not explain how an implementation using static keys can be > > > > conformant with NIST specifications, were raised during the first WGLC > > > > and have not been addressed. During the second WGLC, it was identified > > > > that conformance is intrinsically linked to the patent license. > > > > > > > > My constructive suggestion is to remove all text regarding static keys, > > > > as there is no reason for this draft to include them. I do not believe > > > > comparisons with draft-ietf-tls-hybrid-design are relevant, since that > > > > document serves a completely different purpose and does not register > > > > code points. > > > > > > > > If the draft intends to retain any text on static keys, NIST SP > > > > 1800-37, Addressing Visibility Challenges with TLS 1.3 within the > > > > Enterprise, is a useful reference regarding the negative privacy and > > > > security implications of static keys. I do not have specific guidance > > > > on how to achieve conformance with NIST specifications when using > > > > static keys, but that issue must clearly be resolved. > > > > > > > > I do not find any text in RFC 8446 that allows the use of static keys. > > > > If the TLS WG intends to explicitly permit static keys again, their use > > > > should be explicitly negotiated, as done in TLS 1.2 or > > > > draft-rhrd-tls-tls13-visibility. > > > > > > > > As I have seen no response from the authors indicating that they plan > > > > to address this issue, I am opposed to publishing this document. > > > > > > > > Cheers, > > > > > > > > John > > > > > > > > > > > > > > > > From: Russ Housley <[email protected]> > > > > Date: Thursday, 12 February 2026 at 22:38 > > > > To: Joseph Salowey <[email protected]> > > > > Cc:<[email protected]>, John Mattsson <[email protected]> > > > > Subject: Re: [TLS] WG Last Call: draft-ietf-tls-mlkem-05 (Ends > > > > 2026-02-27) > > > > > > > > I support the publication of this document as an RFC. I would prefer to > > > > have the clarity about ephemeral vs. static ML-KEM keys as posted by > > > > John Mattsson, but I can live with it as-is. > > > > > > > > Russ > > > > > > > > > > > > > > > > > On Feb 12, 2026, at 3:08 PM, John Mattsson > > > > > <[email protected]> wrote: > > > > > > > > > > Hi, > > > > > > > > > > I support publication iff all text related to “key reuse” is removed. > > > > > In its current form, I do not believe -07 should be published. > > > > > > > > > > Major Comments: > > > > > > > > > > - FIPS 203 states that: > > > > > > > > > > “the licensed patents be freely available to be practiced by any > > > > > implementer of the ML-KEM algorithm as published by NIST.” > > > > > > > > > > “requirements for the secure use of KEMs in applications, see SP > > > > > 800-227.” > > > > > > > > > > A reused key is, by definition, a static key. SP 800-227 imposes > > > > > additional requirements for static keys compared to ephemeral keys. > > > > > The draft does not explain how an implementer can satisfy these > > > > > requirements. This creates potential non-conformance with NIST > > > > > specifications. > > > > > > > > > > - The draft does not describe the significant security and privacy > > > > > problems associated with key reuse. IND-CCA is a theoretical property > > > > > of the algorithm. However, the security and privacy problems are > > > > > related to the reuse of keys in the TLS 1.3 protocol in deployments. > > > > > > > > > > Minor Comments: > > > > > > > > > > - The discussion of randomness reuse in ciphertexts and references to > > > > > SP 800-227 do not belong in a “key reuse” section. Ciphertexts are > > > > > not keys, and SP 800-227 contains broader guidelines and requirements > > > > > beyond static keys. > > > > > > > > > > - “The client's shares are listed in descending order of client > > > > > preference; the server selects one algorithm and sends its > > > > > corresponding share.” > > > > > > > > > > The server may also select no share and respond with a > > > > > handshake_failure or a HelloRetryRequest (HRR). Since this is already > > > > > specified in RFC 8446, it would be better to remove this text and > > > > > simply reference RFC 8446. > > > > > > > > > > - Section 5.1 appears to mix different concepts: hybrids, PQ/T > > > > > hybrids, and lattice-based PQ/T hybrids. I assume the person asking > > > > > for this section wanted a comparison with [ECDHE-MLKEM]. I suggest > > > > > doing that. In the future, PQ/T hybrids will likely become less > > > > > common, but it is unclear whether other hybrids (e.g., ML-KEM + > > > > > HQC-KEM) will gain adoption. > > > > > > > > > > Cheers, > > > > > John > > > > > > > > > > From: Joseph Salowey <[email protected]> > > > > > Date: Thursday, 12 February 2026 at 20:06 > > > > > To: > > > > > <[email protected]> > > > > > Subject: [TLS] WG Last Call: draft-ietf-tls-mlkem-05 (Ends 2026-02-27) > > > > > This message starts the second Working Group Last Call for the pure > > > > > ML-KEM document (draft-ietf-tls-mlkem-07). > > > > > > > > > > The file can be retrieved from: > > > > > https://datatracker.ietf.org/doc/draft-ietf-tls-mlkem/ > > > > > > > > > > The diff with the previous WGLC draft (-05) is here: > > > > > > > > > > https://author-tools.ietf.org/iddiff?url1=draft-ietf-tls-mlkem-05&url2=draft-ietf-tls-mlkem-07&difftype=--html > > > > > > > > > > The main focus of this WGLC is to review new text providing more > > > > > context around the use of pure ML-KEM. For those who indicated they > > > > > wanted this text, please let us know if the new text satisfies you > > > > > and if you support publication. This working group last call will end > > > > > on February 27, 2026. > > > > > > > > > > Thank You. > > > > > _______________________________________________ > > > > > TLS mailing list -- [email protected] > > > > > To unsubscribe send an email to [email protected] > > > > > > > > > > > > _______________________________________________ > > > > TLS mailing list -- [email protected] > > > > To unsubscribe send an email to [email protected] > _______________________________________________ > TLS mailing list -- [email protected] > To unsubscribe send an email to [email protected] > > > *Attachments:* > • signature.asc
_______________________________________________ TLS mailing list -- [email protected] To unsubscribe send an email to [email protected]
