Timing Side-Channel Analysis of ML-KEM-768 in liboqs

Summary

ML-KEM decapsulation is written to run in constant time — no branch, no memory access should ever depend on the secret key, because if one did, an attacker who could time enough decryption attempts could recover the key one bit at a time. The design claim is well documented; whether the compiled binary actually holds to it is a separate question, since a compiler is free to turn careful, branchless C into branching machine code without anyone noticing.

This tested that question directly against liboqs's real, compiled ML-KEM-768, using two independent methods — a statistical timing harness against the actual OQS_KEM_decaps() call, and a Valgrind-based static check of the actual machine code — on both the CPU-optimized (AVX2) and portable-C code paths. Neither method found a dependency on secret data in either path. Getting to that answer took building the harness, then fixing three separate bugs in the harness itself that were producing false signals — which turned out to be most of the actual work.

Building the timing harness

The approach: call OQS_KEM_decaps() up to a million times, timed with nanosecond precision (CLOCK_MONOTONIC_RAW), randomly split into two classes — say, a valid ciphertext vs. a random invalid one — and compare the two timing distributions with Welch's t-test, the same statistic dudect uses. |t| > 4.5 was the alarm threshold.

Every real test was bracketed by two controls: a null control (both classes statistically identical — should never alarm) and a positive control (a small, known artificial delay injected into one class — must alarm, or the session's too noisy to trust). VM timing noise turned out to swing wildly between sessions — the same test could resolve a 5 ns difference one minute and miss a 50 ns one twenty minutes later — so nothing counted as a result unless bracketed by a passing control in the same session.

A false alarm, and then a real one

First version of the harness picked each sample's input with an if statement inside the timed loop. The null control started falsely alarming on the noise-cropped data — a tell that something in the harness, not the library, was leaking. Root cause: branch prediction treated the two classes slightly differently before the stopwatch even started. Fixed by precomputing every input and label before the timing loop begins, so the loop body is byte-identical between classes.

Second false alarm, later: comparing one fixed, reused ciphertext against ciphertexts pulled from a random pool showed a suspicious ~7 ns gap. Turned out the fixed one stayed hot in CPU cache across every call, while the pooled ones were pulled cold each time — a memory-access artifact with nothing to do with the algorithm. Fixed by drawing both classes from equally sized, equally cold pools.

With both fixed, bracketed runs across both code paths came back quiet:

mode=invalid samples=1000000 delay_iters=0 seed=1
crop @90%:   n0=450328 n1=449672  mean0=65882.4 ns  mean1=65919.9 ns  diff=-37.5 ns  t=-1.50
crop @75%:   n0=375559 n1=374444  mean0=61177.5 ns  mean1=61169.2 ns  diff=8.3 ns    t=0.84
max |t| = 1.50 -> no timing difference detected

against a bracketing control, run in the same session, that reliably alarmed at the same scale:

mode=delay samples=1000000 delay_iters=8 seed=1
crop @75%:   diff=-10.3 ns  t=-62.47
max |t| = 62.47 -> ALARM: timing difference detected

No timing difference was found above roughly 8 ns, on either the AVX2-optimized backend or a second build forced to the portable-C code path — the exact implementation a compiler is most likely to accidentally branch on.

A second method: Valgrind as a leak detector

A stopwatch can only see a difference bigger than the noise. As a second, noise-free check, Valgrind's Memcheck tool was repurposed: mark the secret key undefined via VALGRIND_MAKE_MEM_UNDEFINED, and Valgrind flags any branch or memory address whose outcome depends on it — with no timing involved at all, and no blind spot at the nanosecond scale.

The first run produced almost 10,000 warnings. Almost all of them traced through gen_matrix. Digging into ML-KEM-768's secret-key layout explained why: the 2400-byte secret key isn't just the secret math — it embeds a full copy of the public key, required later for the re-encryption check the algorithm does internally. Marking the whole buffer undefined had also poisoned that embedded public data, and matrix generation legitimately reads a public seed sitting inside it. Not a leak — a scoping bug in the check.

offset	length	contents	secrecy
0	1152 B	secret vector s	secret
1152	1184 B	embedded copy of pk	public
2336	32 B	hash of pk	public
2368	32 B	implicit-rejection z	secret

Narrowing the check to only the two genuinely secret regions (s and z) and rerunning:

== positive control: leaky branch on secret bytes ==
ERROR SUMMARY: 1152 errors from 1 contexts   <- exactly one per byte of s, as expected

== decapsulation, VALID ciphertext ==
== decapsulation, INVALID ciphertext ==
ERROR SUMMARY: 0 errors

Zero warnings inside decapsulation, on both builds, while the positive control still correctly fired exactly 1152 times — once per byte of the secret vector it was deliberately made to branch on. That's the control working, and the result being clean, not the check being blind.

Limitations

All timing was run in a VirtualBox VM, not bare metal — the ~8 ns bound is what the noisiest reliable session supported, not a hard floor.
One seed of an earlier test showed a ~0.3–0.8 ns hint that didn't reproduce in three follow-up seeds, whose own controls came back weaker than the original run. Inconclusive, not resolved either way.
Valgrind catches secret-dependent branches and memory addresses — not a genuinely branchless but variable-latency instruction (the actual mechanism behind real-world bugs like KyberSlash). The timing method is the relevant check for that class, within its own precision limits.
One key pair, one compiler (gcc 15.2.0), one CPU family tested.

Outcome