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]
signature.asc
Description: OpenPGP digital signature
_______________________________________________ TLS mailing list -- [email protected] To unsubscribe send an email to [email protected]
