Thom Wiggers writes:
> It's specified in Table 1 of the FIPS: for ML-KEM 512, the
> failure rate is 2^-138, the others similarly cryptographically
> negligible.
FIPS 203 _claims_ that the decapsulation failure rates are 2^-138.8,
2^-164.8, and 2^-174.8 for dimensions 512, 768, 1024 respectively, but
as far as I know those are just conjectures rather than theorems. Some
theorems are reported in Table 1 of
https://web.archive.org/web/20250907044602/https://eprint.iacr.org/2025/1562.pdf
but those say merely that the failure rate is <=2^-80, <=2^-95 for
dimensions 768, 1024.
Even if the failure rate is in fact 2^-174.8 for dimension 1024, the
attacker can do better than sending 2^174.8 ciphertexts to trigger a
failure: the attacker can carry out computations, including future
quantum computations, to reduce traffic here. A proof of failure rate
still wouldn't give a proof of the optimal attack tradeoffs. It's not
reasonable to expect proofs to close this part of the attack surface for
Kyber/ML-KEM; instead there's yet another target for cryptanalysts.
A spec aimed at telling people how to _implement_ Kyber/ML-KEM shouldn't
be talking about the failure cases---on the contrary, I'd expect all
sorts of damage from random implementor reactions to hearing about those
failure cases---but from a _security_ perspective the situation here is
not what one expects for a KEM claiming to be as strong as AES-256.
---D. J. Bernstein
P.S. See https://cr.yp.to/papers.html#goppadecoding for formal
verification of a theorem saying that a particular algorithm for
decoding binary Goppa codes always works correctly. This decoding task
is what Classic McEliece decapsulation relies upon, and this algorithm
is what the Classic McEliece software uses.
_______________________________________________
TLS mailing list -- [email protected]
To unsubscribe send an email to [email protected]
