What is the probability of an adversary guessing the correct key? What’s the probability of an honest KEM failure? What’s the effort of computing “deliberate” failure, and how can you do that, except for trying exchanges with the target until the key confirmation fails? And what can an adversary do with it? Say, you managed to create (by what algorithm? At what cost?) N deliberate KEM failures - now what?
— Regards, Uri
Secure Resilient Systems and Technologies MIT Lincoln Laboratory On Sep 25, 2025, at 16:37, Eric Rescorla <e...@rtfm.com> wrote:
On Thu, Sep 25, 2025 at 11: 41 AM D. J. Bernstein <djb@ cr. yp. to> 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
ZjQcmQRYFpfptBannerStart
This Message Is From an External Sender
This message came from outside the Laboratory.
ZjQcmQRYFpfptBannerEnd
On Thu, Sep 25, 2025 at 11:41 AM D. J. Bernstein < d...@cr.yp.to> 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
|
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________
TLS mailing list -- tls@ietf.org
To unsubscribe send an email to tls-le...@ietf.org
