Project
Kestrel
Static detection of ML-KEM and ML-DSA inside stripped, statically linked and obfuscated binaries, by fingerprinting the number-theoretic transform constant tables the algorithms cannot run without.
Problem
Migration mandates assume that someone can look at a compiled program and confirm that a post-quantum algorithm is really inside it. Existing discovery tools find the classical algorithms that are being retired, but rely on symbol names, strings and library dependencies, which stripping, static linking and optimisation remove. None of them could confirm the replacement from a shipped binary alone.
Approach
ML-KEM and ML-DSA both depend on a number-theoretic transform, which needs a fixed table of constants (powers of a root of unity) baked into the binary. Change those numbers and the scheme stops working, and because the table is data rather than code, optimisers, stripping and static linking leave it intact. Kestrel derives fingerprints of these tables from the public scheme parameters and searches for them.
Design decisions
- Normalise every candidate value both ways at once: the reference implementation stores constants in signed Montgomery form, so a naive search for the textbook residues finds nothing.
- Read every data section a toolchain might use, including Go’s
.noptrdata, which an early version missed and so produced a false negative on a real Go ML-KEM binary. - Match tables as multisets, so reordering entries does not hide them; count tables per binary to attribute a detection to its originating codebase (C reference, Go, Rust, BoringSSL).
- Pure Python standard library, so it runs on a stripped binary or a raw disk image with nothing installed.
Evaluation
The author evaluated recall across four independent implementation lineages under every build transformation (-O2, -O3, -Os, stripping, static linking and an LLVM instruction-substitution obfuscation pass), swept 6,224 binaries in /usr/bin and /bin of a production Linux system, and ran a forensic disk-image trial. Measurements were taken on a Kali virtual machine with four cores of an Intel i9 and 8 GB of RAM; the repository includes the generator, detector, obfuscation pass, benchmark scripts, raw measurement files and the machine fingerprint.
Results
Recall of 128 of 128 across four implementation lineages and every build transformation tested, with zero false positives. The analytical false-positive bound is 6.4e-9 per window at the detection threshold of 32.
On 6,224 binaries from a production Linux system, twelve uncatalogued programs containing ML-KEM were found, among them the OpenSSH key-exchange program and the container-management stack, where post-quantum code had arrived through the Go runtime without the projects' awareness. The sweep took 9 minutes 44 seconds (mean 94 ms per binary).
In a forensic disk-image trial, an ML-KEM table was still detected in unallocated space after the deleted binary could no longer be carved back.
These are the author's reported measurements; the raw logs are in the repository.
Limitations
A binary that generates its constant table at run time instead of storing it leaves nothing on disk to find; this evasion was built and confirmed (it scores 7 against a threshold of 32). It requires forking the implementation, which none of the twelve real-world programs had done.
On a raw disk image holding several binaries, a detection shows that post-quantum code is present on the disk, not which deleted file it belonged to; per-file attribution still needs per-file scanning.