Part III, Engineer · Lesson 17

Implementation pitfalls: timing, state and randomness

By Kyeson Blake Utley18 min read1 interactiveMath and code

The short version

A safe lock can still be opened if it clicks louder on the right number. Computers can 'click' too: tiny timing differences, reused one-time keys, or dice that aren't really random. Most real attacks go after these mistakes, not the math.

You'll learn to

Explain what constant-time code means and spot early-exit and variable-time-instruction leaks.
Describe the KyberSlash and clangover issues and what fixed them.
List the ways ML-KEM's implicit rejection can be undone by an implementation.
Explain how state rollback and weak randomness break otherwise sound schemes.

The math is fine. The code is the attack surface.

ML-KEM's security proof says nothing about your CPU's division unit, your compiler's optimizer or your VM snapshot policy. Attackers know this. The memorable breaks of deployed cryptography have mostly come from implementations, not from new mathematics. This lesson covers the three big families for post-quantum code: timing, state and randomness, with real incidents for each.

Constant-time code

"Constant time" doesn't mean every call takes the same number of nanoseconds. It means nothing about the execution depends on secret data:

no branches on secrets (if secret_bit: …);
no memory addresses derived from secrets (table lookups indexed by key bytes);
no instructions whose latency depends on their operands, such as division on many CPUs and, on some CPUs, multiplication.

The textbook leak is an early-exit comparison:

// Leaks how many leading bytes matched
for (i = 0; i < n; i++) if (a[i] != b[i]) return 0;
return 1;

// Constant time: always touches every byte, no secret-dependent branch
unsigned diff = 0;
for (i = 0; i < n; i++) diff |= a[i] ^ b[i];
return diff == 0;

Measured once, the difference is nanoseconds. Measured thousands of times, it is a signal. Averaging defeats noise, and that's the whole game.

Raise the jitter until the attack starts failing, then raise the requests per candidate and watch it succeed again. Switch to the constant-time compare and no amount of averaging helps. The timings here are simulated, but the arithmetic of the attack is real: 16 candidates × 6 positions instead of 16⁶ guesses.

Case study: KyberSlash (2023–2024)

The Kyber reference implementation, the code ML-KEM grew from, had this line in poly_tomsg, which turns decrypted coefficients into message bits:

t  = (((t << 1) + KYBER_Q/2)/KYBER_Q) & 1;

That's Compress_1 from FIPS 203. KYBER_Q is the public constant 3329, but t is secret. On many CPUs, the time a division takes depends on its inputs. Whether the C compiler emits a division instruction at all depends on the platform and flags. On x86, gcc -Os produces a division and gcc -O3 a multiplication. On RISC-V, both produce a division. On a Raspberry Pi 2, the division became a call to a software routine with input-dependent branches.

KyberSlash1 is that division in decryption (poly_tomsg).
KyberSlash2 is the similar divisions in the compression functions used by encryption. Because ML-KEM decapsulation re-encrypts (the FO transform), those run on secret data too.

Timeline. Goutam Tamvada, Karthikeyan Bhargavan and Franziskus Kiefer noticed the issue while writing a formally verified Kyber implementation in Rust, and reported it. The reference repository was patched on 1 December 2023 for KyberSlash1. Daniel J. Bernstein independently found it and announced it publicly on 15 December 2023. Prasanna Ravi and Matthias Kannwischer announced the KyberSlash2 divisions on 30 December 2023, the same day the reference code was patched for them. Many libraries shipped fixes from December 2023 through 2024, and as of August 2025 the KyberSlash site still listed some libraries as unpatched.

Impact. The resulting paper, published in IACR TCHES 2025 (issue 2), demonstrated full secret-key recovery on a Raspberry Pi 2 (Arm Cortex-A7) and an Arm Cortex-M4: within minutes for KyberSlash2 and a few hours for KyberSlash1.

The fix replaces the division with multiply-and-shift arithmetic that has no data-dependent timing. Today's reference poly_tomsg reads:

t <<= 1;
t += 1665;
t *= 80635;
t >>= 28;
t &= 1;

For every coefficient value from 0 to 3328, that gives exactly the same bit as the division, using a precomputed reciprocal instead of a divide.

Encore: the compiler adds a branch (clangover, 2024)

In 2024, Antoon Purnal showed that Clang versions 15–18 could compile the reference poly_frommsg, which was constant-time at the source level, into machine code with a secret-dependent branch. This happened on x86 with options including -Os, -O1, and -O2/-O3 with -fno-vectorize. His proof of concept recovered an ML-KEM-512 secret key in 5–10 minutes from end-to-end decapsulation timings on an Intel Core i7-13700H. It is tracked as CVE-2024-37880 and was fixed upstream in the Kyber reference code.

The lesson is uncomfortable but important: the compiler is part of your threat model. Constant-time source code is a promise the optimizer never signed. Defenses:

check the binary, not just the source: tools that flag secret-dependent branches, memory accesses and variable-time instructions (the KyberSlash authors patched Valgrind to detect variable-time instructions on secret data);
use value barriers and the hardened idioms your library provides, and re-test when you change compilers or flags;
prefer well-reviewed libraries that track these issues over your own implementation.

Don't hand back the FO flag

As Inside ML-KEM explained, decapsulation re-encrypts and, on mismatch, returns a pseudorandom key J(z ‖ c). That design only works if the attacker truly can't tell which branch happened. Implementations can leak it by:

returning an error code or logging "decapsulation failed";
comparing c and c′ with an early-exit compare;
selecting between K′ and K̄ with a branch instead of a constant-time conditional copy;
doing different amounts of work afterwards, for example aborting the handshake earlier on one path.

FIPS 203 is explicit: the match/mismatch flag is secret intermediate data that "shall be destroyed," and returning it "in any form is not permitted." It also mandates input checks: the encapsulation-key modulus check, the decapsulation-key hash check, and a ciphertext length check on every decapsulation. Skipping them is non-conformance, not a performance tweak.

State: one-time means one time

Stateful hash-based signatures (LMS, XMSS) fail catastrophically if any one-time key signs twice. You built the attack in the Lamport lesson and the rollback scenario in the Merkle lesson. NIST SP 800-208 responds with hard rules: hardware modules, no private-key export, and the incremented leaf index written to nonvolatile storage before the signature is released. It also names a subtle trap: writing to a file isn't enough if the OS caches the write and the machine loses power.

Operational state hazards to design out:

restoring a signer from backup or a VM snapshot;
two HSMs or cluster nodes holding the same key "for availability";
a CI job that spins up a signer from a golden image;
a crash between producing a signature and persisting the counter.

If availability matters, use separate keys or a multi-tree (HSS, XMSS^MT) design with subtrees on different modules, as SP 800-208 suggests. Or choose a stateless scheme (ML-DSA, SLH-DSA).

Randomness: the quiet single point of failure

Every scheme in this course assumes good random numbers. History says that assumption fails in ordinary ways.

Debian OpenSSL (CVE-2008-0166). A Debian-specific patch made OpenSSL's random number generator predictable. Affected packages started with version 0.9.8c-1, uploaded in September 2006, and the advisory came on 13 May 2008. All SSH, OpenVPN, DNSSEC and X.509 key material generated on affected systems had to be regenerated. Debian also advised treating every DSA key used on those systems as compromised, because DSA signing consumes secret randomness.
Android SecureRandom (2013). An August 2013 Bitcoin security alert reported that a component of Android that generates secure random numbers had critical weaknesses. Bitcoin wallets that generated keys on Android phones were exposed to theft, and users were told to move their funds to fresh keys.

For ML-KEM, the danger is concrete. Encapsulation picks 32 random bytes m, and the shared secret comes from (K, r) = G(m ‖ H(ek)). Anyone who can predict m can compute K from the public key alone, no lattice required. That's why FIPS 203 ties each parameter set to a minimum random-bit-generator strength (128, 192 or 256 bits) and requires encapsulation to return an error if randomness generation fails. Key generation is just as exposed: its seeds d and z determine the entire key pair.

A pitfall checklist

Area	Ask
Timing	Was the compiled code checked for secret-dependent branches, indices, divisions and multiplications on every target and flag set we ship?
FO / KEM	Is decapsulation failure indistinguishable to callers, logs and timing? Are the FIPS 203 input checks in place?
State	Can any signer ever sign with a rolled-back or duplicated counter? What happens on power loss mid-signature?
Randomness	Does every key and encapsulation use an approved, properly seeded RBG, and fail closed when it can't?
Dependencies	Do we track advisories for our PQC library (KyberSlash-style fixes landed library by library)?

Summary

Constant time means no secret-dependent branches, memory indices or variable-latency instructions, checked in the binary.
KyberSlash: secret division by q = 3329 in Kyber code leaked timing; key recovery was demonstrated on Cortex-A7 and Cortex-M4; fixed with multiply-and-shift.
Clangover (CVE-2024-37880): Clang 15–18 turned constant-time source into a secret branch; the compiler is in your threat model.
ML-KEM's implicit rejection fails if the mismatch flag leaks via errors, logs, early-exit compares or branches.
Stateful signatures need the counter persisted before release; backups, snapshots and clones are the classic reuse paths.
Predictable randomness breaks everything: Debian OpenSSL (2008), Android SecureRandom (2013); in ML-KEM, a predictable m reveals K.

Questions

Get five of six right to mark the lesson complete. They also feed the final exam.

Sources

Drawn byKyeson Blake Utley

CourseQuantum Defense

Sheet17 of 18

PartIII · Engineer

Rev.18 Oct 2026

Sources8 cited

Found an error?Send a correction