Catching a KyberSlash-class bug in liboqs ML-KEM-768 with a patched Valgrind

In plain words

Some CPU instructions take a different amount of time depending on the numbers they're given. Division is the classic one. If a program divides by, or divides something derived from, a secret, then how long the division takes can leak the secret. KyberSlash (2023–24) was exactly this: a plain division in Kyber/ML-KEM code let researchers recover secret keys from timing.

This note shows that a patched Valgrind can catch this bug class in a real library, and that it stays quiet on fixed code. I reproduced KyberSlash1 on purpose in a private copy of liboqs, compared it against the unmodified code under identical compiler flags, and the tool flagged the bug in the same function where it was originally found.

Background

KyberSlash1 was first noticed by Tamvada, Bhargavan and Kiefer, and independently by Bernstein. KyberSlash2 was found separately by Ravi and Kannwischer. The published paper is Bernstein et al., "KyberSlash: Exploiting secret-dependent division timings in Kyber implementations," IACR TCHES 2025, issue 2, pp. 209–234.

The authors also published a patch adding a new check to Valgrind's Memcheck tool. Stock Memcheck already flags secret data used in branches and memory addresses. The patch adds a third check: a secret value used as an operand of a variable-latency instruction, mainly integer and floating-point division, plus square root and floating-point remainder. It's switched on with --variable-latency-errors=yes.

Setup

• OS and hardware: Kali Linux in VirtualBox, Intel i3-8130U
• Compiler: gcc 15.2.0
• Library: liboqs 0.16.0 release, ML-KEM-768 from the vendored mlkem-native code
• Valgrind: patched with the KyberSlash option and division patches, built into its own prefix
• Builds tested: plain C at -O3 (Release), AVX2 with runtime dispatch, and plain C at -Os (MinSizeRel)

Method

The harness is a small C program linked against liboqs. It generates a key pair, then marks only the genuinely secret parts of the secret key as undefined, which Valgrind treats as "secret": the secret vector s and the value z. It runs decapsulation on a valid and a random invalid ciphertext.

Two deliberate positive controls run in the same program: a loop that branches on secret bytes, and a loop that divides by a value derived from secret bytes. A quiet result only counts if these controls fire.

The compiler finding

The KyberSlash1 rounding step is ((u*2 + Q/2) / Q) % 2 with Q = 3329. The divisor is a constant, so compilers often replace the division with a multiply. Compiling that one line at five optimization levels and counting real div instructions:

The same source line is safe or vulnerable depending on one compiler flag. Correct maths, constant-time behaviour, and compiler output are three separate properties, so the binary that ships is the thing to test. This also explains why the original researchers saw the bug specifically in -Os builds.

Results

In every run the deliberate division control was flagged, so the tool was demonstrably active. For the reintroduced bug, the warnings point straight at:

Variable-latency instruction operand of size 8 is secret/uninitialised
   at PQCP_MLKEM_NATIVE_MLKEM768_C_poly_tomsg
   by PQCP_MLKEM_NATIVE_MLKEM768_C_indcpa_dec
   by PQCP_MLKEM_NATIVE_MLKEM768_C_dec
   by main

poly_tomsg inside decryption is where KyberSlash1 was originally found. The tool located it without being told where to look. The change was one edit in mlk_scalar_compress_d1: the multiply-and-shift code was replaced with the plain division formula, with everything else — compiler, flags — held identical between the fixed and bug builds.

Limits

• The tool flags a variable-latency instruction operating on secret data. It does not prove the timing difference is exploitable on a given CPU.
• One compiler version, one parameter set (ML-KEM-768), one machine.
• The bug reintroduction was done only on the plain-C -Os build.
• No timing measurement of the reintroduced bug was taken; this note shows detection, not measured leakage.

Reproducing it

1. Get the KyberSlash Valgrind patches, apply them to a matching Valgrind commit, and build into a private prefix.
2. Sanity test: a program that divides by a value from heap memory should be silent normally and flagged with --variable-latency-errors=yes.
3. Build liboqs at the 0.16.0 commit with -DCMAKE_BUILD_TYPE=MinSizeRel, once unmodified and once with the division put back.
4. Link the harness against each build and run it under the patched Valgrind.

Next steps

Run the same A/B test on ML-KEM-512 and 1024 and on ML-DSA signing, try a second library, and add a timing measurement of the reintroduced bug on hardware where the division is known to be variable-latency.