Hi Eric, The attacker knows the distribution of the coefficients of the private key s-hat and the attacker runs their own Encap. Looking at the computations in Decrypt (Algorithm 15), the attacker can search for ciphertext (by running the Encaps with his choices of m) which has higher decryption failure probability than the natural case.
So, the attacker must find a ciphertext which has high probability to cause decryption failure or more ciphertexts which have lower decryption failure probabilities (than the single ciphertext case) to have some chance of decryption failure happening. This is expected to be a massive computation since the attacker does not know the private key. (*) ( I don't plan to quantify this attack.) Assume an attacker finds a ciphertext and they know that decryption failure happens with this ciphertext, the Decap function outputs a pseudorandom value which has nothing to do with the decryption key. So, seeing the output of Decap does not give the attacker any information about the decryption key. Assume the case with high decryption failure rate (a broken version of "ML-KEM" somewhere), when trying with normal ciphertexts and the attacker knows instances of decryption failure, then the attacker can get information about the decryption key, especially when the failure cases happen much more than the expected decryption failure rate. But with the attack (*) above, when the attacker deliberately finds ciphertexts which have higher chances to cause decryption failure than the normal ciphertexts generated by Encap then when decryption failure actually happens (as the attacker wishes), it seems to give the attacker much less information about the decryption key than the decryption failure instances of the non-attack generated ciphertexts case. In TLS, if ephemeral keys are used, then the attack (*) is useless to the attacker. So, use ephemeral keys whenever possible. ML-KEM's key gen is cheap/fast. Regards, Quynh. From: Eric Rescorla <[email protected]> Sent: Thursday, September 25, 2025 4:34 PM To: [email protected] Subject: [EXTERNAL] [TLS] Re: ML-KEM failures On Thu, Sep 25, 2025 at 11:41 AM D. J. Bernstein <[email protected]<mailto:[email protected]>> wrote: > “The failure rate for ML-KEM is > sufficiently low that it is highly unlikely that any implementation will > ever encounter it in practice.” That's not known. It's important to distinguish two different situations here. Situation 1 is _legitimately generated ciphertexts_. For that situation, Table 1 of https://web.archive.org/web/20250907044602/https://eprint.iacr.org/2025/1562.pdf reports proofs that the failure rate is <=2^-80, <=2^-95 for dimensions 768, 1024. Also, the failure rate is _conjectured_ to be 2^-138.8, 2^-164.8, and 2^-174.8 for dimensions 512, 768, 1024 respectively. If this conjecture is correct then legitimate users would have to be amazingly unlucky to generate a failing ciphertext. Situation 2 is _ciphertexts generated by attackers_. The reason this is different is that attackers can spend tons of computation searching for ciphertexts that are enc outputs but more likely to fail than average enc outputs are. As an example of how it's not obvious what the best tradeoffs are here, page 23 of the original Kyber documentation https://web.archive.org/web/20190214071008/https://pq-crystals.org/kyber/data/kyber-specification.pdf claimed that a particular approach was "probably" the "best strategy"; that turned out to _not_ be the best attack. The paper https://web.archive.org/web/20250708141344/https://eprint.iacr.org/2021/193.pdf gives you an idea of how complicated it can be to optimize attacks using some of the available structure. Thanks for the expanded discussion. It seems to me that the relevant question for the purposes of this document is whether the client should do anything in this case other than just report a connection failure and handle it like any other connection failure. -Ekr
_______________________________________________ TLS mailing list -- [email protected] To unsubscribe send an email to [email protected]
