I'm not sure why the decapsulation failure is claimed to only be analysed experimentally, it is fairly straightforward to analyse theoretically: A decapsulation failure occurs if s^t f + e^t r + g is bigger or equal to (q-1)/2. Other than the (not all that important) scalar noise g, this is an inner product which can be seen as coming from the trace form of the maximal totally real subfield of Q[X]/(X^256+1), accounting for the fact that a number field is used, from there you can, as is at least sketched in the Kyber round 3 documentation, use Cauchy-Schwarz and norm equivalence between 2-norm and Minkowski 2-norm to compute this bound. f and r are noise terms coming from the FO-transform, making finding terms with larger than expected norm an exponentially hard problem in the size of the noise terms. I have not double checked that the terms computed by the Kyber group actually shake out to be the claimed values, but these are mathematical reductions, and not experimentally deduced numbers or poorly understood mathematical concepts. We as far as I know do not have reductions for RLWE or MLWE (or NTRU, for that matter) to pure LWE, but this is actully a well understood part or the problem.
On Wed, Sep 24, 2025 at 7:36 AM Deirdre Connolly <[email protected]> wrote: > > some are not (they are explicit rejection) and may have a return code > that can be caught and the protocol/application can change behavior on > > (One example of this is actually an 'accidental > <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Wiu4ZQo3fP8/m/t9UTwG05CAAJ>' > explicit-rejection when the first reference implementation of HQC > <https://github.com/PQClean/PQClean/blob/448c71a8f590343e681d0d0cec94f29947b0ff18/crypto_kem/hqc-128/clean/kem.c#L137> > always returned a return code that changed based on the decryption result, > which was not how this version of the scheme was specified— this has now > been fixed in the latest submission > <https://gitlab.com/pqc-hqc/hqc/-/blob/v5.0.0/src/ref/hqc.c?ref_type=tags#L206> > ) > > On Wed, Sep 24, 2025 at 10:19 AM Deirdre Connolly < > [email protected]> wrote: > >> One thing to consider for the text for -hybrid-design is that while >> ML-KEM and many PQ KEMs are implicit-rejection and always return a >> pseudorandom value on decryption failure, during which TLS cannot detect a >> failure programmatically, some are not (they are explicit rejection) and >> may have a return code that can be caught and the protocol/application can >> change behavior on. This (implicit rejection) is considered a security >> win >> <https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf>as >> failure to correctly interpret the return code as a code, but as a >> pseudorandom key, is insecure. >> >> So, what happens explicitly in TLS 1.3 when the client and server do the >> whole handshake correctly but there is a decaps/decryption failure and the >> handshake secrets disagree? All the downstream secrets in the key >> schedule will disagree. How is this noticed in the protocol? Not as a ` >> handshake_failure >> <https://datatracker.ietf.org/doc/html/rfc8446#section-6.2>`, but I'm >> pretty sure with a `bad_record_mac >> <https://datatracker.ietf.org/doc/html/rfc8446#section-5.2>`. This does >> not seem incorrect. >> >> If we are cool with that then we can remove all mention of KEM failures >> and sleep well at night >> >> On Mon, Sep 22, 2025 at 3:04 PM Eric Rescorla <[email protected]> wrote: >> >>> Hi folks, >>> >>> I see that the hybrid doc continues to have this text: >>> >>> *Failures.* Some post-quantum key exchange algorithms, including ML-KEM >>> [NIST-FIPS-203 >>> <https://www.ietf.org/archive/id/draft-ietf-tls-hybrid-design-16.html#NIST-FIPS-203> >>> ], have non-zero probability of failure, meaning two honest parties may >>> derive different shared secrets. This would cause a handshake failure. >>> ML-KEM has a cryptographically small failure rate; if other algorithms are >>> used, implementers should be aware of the potential of handshake failure. >>> Clients MAY retry if a failure is encountered. >>> >>> There was extensive discussion about this for the pure ML-KEM draft, and >>> my sense was the sentiment was that this should not be discussed, at least >>> for ML-KEM. I think we should remove >>> this whole section. >>> >>> -Ekr >>> >>> _______________________________________________ >>> 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] > -- Sophie Schmieg | Information Security Engineer | ISE Crypto | [email protected]
_______________________________________________ TLS mailing list -- [email protected] To unsubscribe send an email to [email protected]
