Description

This proof-of-concept demonstration exploits the observation that compiling the Kyber reference implementation with Clang may result in the emission of a secret-dependent branch.

Despite the source-level constant-time implementation of poly_frommsg, Clang has been observed to produce insecure assembly for at least the following configurations:

• ISA: x86
• Clang versions: v15-18
• Clang options:
  • -Os
  • -O1
  • -O2 -fno-vectorize
  • -O3 -fno-vectorize

On an Intel Core i7-13700H (Clang 16.0.6), it takes between 5-10 minutes to leak the entire ML-KEM 512 secret key using end-to-end decapsulation timing measurements.

The attack strategy is a plaintext-checking oracle attack a la Ravi et al. and Ueno et al.

Running the PoC

# Pull pqcrystals/kyber standard branch (though attack also affects main branch)
git submodule init && git submodule update

# Modify compiler options and produce shared library
sed -i 's/-O3/-Os/g' kyber/ref/Makefile
CC=clang make -C kyber/ref shared

# Build the key recovery PoC
make

# Run the key recovery PoC
./clangover

Remarks

If the PoC doesn't produce the correct key guesses on your machine, here is some guidance:

1. Check that you are running on x86
2. Check that you are using clang version 15 or later (latest is 18.1 at time of writing)
3. This PoC contains some parameters in attack.c. Consider tweaking them for your machine. Of special interest are:
   • CONFIDENCE_HIGH: the higher, the more robust
   • EVALUATE_EVERY_N_ITERATIONS: the higher, the more robust
   • OUTLIER_THRESHOLD: can go either way