The finding
ML-KEM decapsulation must not leak, by timing, whether a ciphertext was accepted or implicitly rejected. FIPS 203 §6.3 is explicit: the implicit-reject flag "shall be destroyed" and returning it "in any form is not permitted." We have found implementations that leak it anyway — some via secret-dependent arithmetic, some via a branch the compiler introduced. Verify the constant-time property at the binary level.
ML-KEM tolerates implicit rejection by design: on an invalid ciphertext it returns a deterministic pseudo-random shared secret rather than an error. The reason the accept/reject comparison exists at all is the Fujisaki–Okamoto transform — decapsulation re-encrypts the decrypted message and compares the result to the input ciphertext (Hofheinz, Hövelmanns & Kiltz, 2017). That comparison, and everything downstream of it, is secret-dependent — so it is only safe if the reject path is indistinguishable, by timing, from the accepting one.
Two real 2024 attacks anchor the class. KyberSlash exploited secret-dependent timing of the division instruction in Kyber's compression code — the source itself divided secret data by q, and hardware division latency leaked it. clangover is the subtler cousin: Clang 15–18 compiled a source-level constant-time routine (`poly_frommsg`) into a secret-dependent branch, recovering an ML-KEM-512 key in minutes through a plaintext-checking oracle. They are the two canonical ways decapsulation goes variable-time: unsafe arithmetic in the source, and a compiler that undoes a constant-time source.
Constant-time, undone by the compiler
The clangover case is worth dwelling on: source code written to be constant-time, compiled into branchy code by the optimiser. The property the developer reasoned about at the source level no longer holds in the binary the machine actually runs — which is exactly why you cannot certify constant-time by reading the source.
Verify at the binary level
Check the constant-time property where it matters — at the binary level. Runtime instrumentation like ctgrind / TIMECOP (Valgrind-based) flags secret-dependent branches and memory access; dudect measures the compiled binary statistically. Source review alone missed clangover; binary-level checking is what catches the compiler-introduced branch.
Weak randomness in keygen
A related and surprisingly common bug: keygen drawing randomness from a non-cryptographic source, or one that has not been seeded. FIPS 203 §3.3 mandates an approved random-bit generator (SP 800-90A/B/C) with at least 128/192/256-bit strength for ML-KEM-512/768/1024 — a working implementation does not prove the RNG path is sound.
References
- The two attacks: KyberSlash (IACR eprint 2024/1049) + its affected-library tracker, and clangover — the compiler-introduced branch.
- NIST: FIPS 203 / ML-KEM — §6.3 flag-secrecy ("shall be destroyed … not permitted") and §3.3 RBG requirements.
- The FO transform (why the secret-dependent comparison exists): Hofheinz, Hövelmanns & Kiltz, "A Modular Analysis of the Fujisaki–Okamoto Transformation" (eprint 2017/604).
- Constant-time testing: dudect — "Dude, is my code constant time?" (eprint 2016/1123).
- Wikipedia: Timing attack, Side-channel attack, Kyber (includes KyberSlash coverage).