Also mentioned
ML-KEMML-KEMModule-Lattice-based Key Encapsulation MechanismModule-Lattice-Based Key-Encapsulation Mechanism, the NIST-standardized post-quantum KEM derived from CRYSTALS-Kyber and specified in FIPS 203.Read the full entry (new tab), FIPSFIPSFederal Information Processing StandardFederal Information Processing Standards, publicly announced standards developed by NIST for use in U.S. government computer systems, including cryptographic algorithms and modules.Read the full entry (new tab), NISTNISTNational Institute of Standards and TechnologyThe U.S. National Institute of Standards and Technology, the agency that develops and publishes cryptographic standards, including the FIPS series and post-quantum algorithms.Read the full entry (new tab) are defined in the glossary.
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. That behaviour is itself a conformance requirement, and a battery can check it even though it cannot check the timing. 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. A conformance battery driving the interface cannot see it either; the property has to be checked where the code runs. We have since found an unmaintained crate carrying the KyberSlash advisory inside a shipping product, and that review is published.
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, and it is one of the checks we run in an implementation audit.
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).