💻 computer science

Static Detection of Post-Quantum Cryptographic Algorithms in Stripped Binaries for Digital Forensic Examination and Migration Assurance

This paper introduces Kestrel, a static analysis tool that reliably detects standardized post-quantum cryptographic algorithms (ML-KEM and ML-DSA) in stripped and optimized binaries by identifying unique number-theoretic transform constant tables, thereby enabling effective forensic examination, supply chain inspection, and migration assurance even when traditional detection signals are obscured.

Original authors: Muhammad Shaheer Bin Junaid

Published 2026-08-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Muhammad Shaheer Bin Junaid

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of digital security, a quiet revolution is underway. For decades, the locks protecting our most sensitive data—banking records, state secrets, private messages—have relied on mathematical puzzles that are easy to create but nearly impossible to solve without a specific key. These puzzles, known as public-key cryptography, are the foundation of trust on the internet. However, scientists have long predicted that a new type of computer, one that harnesses the strange laws of quantum physics, will eventually be powerful enough to break these locks instantly. When that happens, the old locks will become useless. To prepare, experts are designing new locks based on different mathematics that even a quantum computer cannot easily crack. These new systems are called post-quantum cryptography. The challenge now is not just building these new locks, but finding them. As organizations rush to replace their old systems, they need to know exactly where the new ones are hiding inside the complex software that runs their world. But there is a problem: once software is compiled into a final program for use, the labels and names that usually tell us what is inside are often stripped away to make the program smaller and faster. Without those names, finding a specific new lock inside a pile of code has been like trying to find a specific grain of sand on a beach without knowing what the sand looks like.

A researcher named Muhammad Shaheer Bin Junaid has developed a new way to solve this problem. He created a tool called Kestrel that can identify these new, quantum-safe locks inside stripped software, even when all the usual clues have been removed. The method relies on a simple but powerful observation: while the names of the code can be erased, the raw numbers the code needs to work cannot. The new cryptographic systems, specifically those based on a structure called a lattice, must use a fixed set of pre-calculated numbers to perform their calculations. These numbers act like a permanent fingerprint. No matter how much the software is optimized, compressed, or renamed, these specific numbers must remain in the file for the program to function. If the numbers are missing, the program simply will not work. Kestrel scans the raw data of a program, looking for these specific patterns of numbers. It does not care about the names of the functions or the libraries the program uses; it only cares about the presence of these essential mathematical constants.

The researcher tested this approach on a wide variety of software, including programs built with different tools and subjected to every kind of standard processing that makes them harder to analyze. They found that the tool worked perfectly. In tests involving 128 different versions of the software, Kestrel identified the new cryptographic algorithms in every single case, even when the programs had been stripped of all their names and linked together in complex ways. Crucially, the tool did not make any mistakes. When the researcher scanned over 6,000 real-world programs from a standard computer system, the tool found no false alarms. It did not mistake ordinary software for the new cryptographic systems. This level of accuracy is vital for digital forensics, where an expert must be absolutely certain about what they find before presenting it in a legal setting.

Perhaps the most surprising discovery came when the tool was applied to a live computer system. The scan revealed twelve different programs that contained these new quantum-safe locks, yet no one knew they were there. These included the software that manages internet connections for secure logins and the systems that run containerized applications. In many cases, the new cryptography had entered these programs automatically through the programming languages used to build them, without the developers of those programs even realizing it. This finding highlights a significant gap in current security practices: organizations might believe they are using old, vulnerable systems, or they might think they have upgraded, but without a way to inspect the actual code, they cannot be sure. Kestrel provides that certainty. It can distinguish between a program that genuinely uses the new locks and one that merely claims to do so. In one test, a program claimed to have quantum-safe protection, but the tool found no evidence of it, correctly identifying the claim as false.

The tool also proved its value in a forensic setting, simulating the recovery of data from a damaged or deleted file. When a file is deleted, the operating system often marks the space as available for new data, but the old data remains on the disk until it is overwritten. Standard recovery tools try to rebuild the file structure, which often fails if the file header is damaged. However, because Kestrel looks for the specific numbers inside the data rather than the file structure, it was able to find the cryptographic fingerprint even in the raw, unorganized space of the disk image. It successfully identified the presence of the new algorithm in a file that other tools could not recover. This capability means that investigators can confirm the use of specific cryptographic methods even when the original files are gone or corrupted.

The research also clarified what the tool cannot do. It is designed to find the specific types of new locks that rely on these fixed number tables. It cannot find other types of new locks that do not use this method, nor can it find a program that calculates these numbers on the fly every time it runs, rather than storing them. However, the researcher noted that no known software currently uses this "on-the-fly" method because it is inefficient and unnecessary. The tool is built for the reality of how software is actually made and distributed today. By focusing on the immutable numbers that the code requires to function, Kestrel offers a reliable way to verify the presence of these new security systems. It turns the invisible into the visible, allowing auditors and investigators to see exactly what is inside a program, ensuring that the transition to a quantum-safe future is based on facts rather than assumptions.

Technical Summary: Static Detection of Post-Quantum Cryptographic Algorithms in Stripped Binaries

Problem Statement
The transition to post-quantum cryptography (PQC) faces a critical verification gap: while tools exist to identify quantum-vulnerable algorithms (RSA, ECC) in source code or binaries, there is no established method to verify the presence of standardized post-quantum algorithms (specifically ML-KEM and ML-DSA) within compiled, stripped, and statically linked binaries. Existing cryptographic discovery tools rely on symbols, library dependencies, runtime behavior, or network traffic. These signals are destroyed by standard build transformations such as symbol stripping, static linking, and compiler optimization. Consequently, auditors and forensic examiners cannot confirm whether a binary genuinely implements PQC or merely advertises it, a distinction that has become urgent due to the emergence of PQC-enabled malware (e.g., the "Kyber" ransomware family) and regulatory mandates (e.g., Executive Order 14412) requiring verification of deployed cryptographic primitives.

Methodology: The Kestrel Approach
The paper introduces Kestrel, a static analysis tool that identifies ML-KEM and ML-DSA by detecting the Number-Theoretic Transform (NTT) constant tables embedded in the read-only data section of binaries.

The Signal: ML-KEM and ML-DSA rely on polynomial multiplication via the NTT, which requires precomputed tables of powers of a fixed root of unity ( $\zeta$ ) modulo a prime ( $q$ ). Unlike code, these constant tables are data; they cannot be removed or altered by optimization without breaking the algorithm's correctness. They persist through stripping and static linking.
Fingerprint Derivation: Instead of manually compiling a list of signatures, Kestrel uses a deterministic procedure to generate the complete set of fingerprints from public scheme parameters ( $q$ , $\zeta$ , transform length, bit-reversal width). The generator produces three families of constants: forward twiddles, inverse twiddles, and base-case/mod-root constants. It accounts for various storage representations, including Montgomery form, signed/unsigned integers, and vectorized layouts.
Detection Pipeline:
- Normalization: The detector scans the read-only data section, normalizing candidate values to canonical residues modulo $q$ . This handles signed vs. unsigned representations and converts Montgomery form back to plain residues.
- Multiset Scoring: Rather than exact byte-matching, the detector scores a window based on the number of expected canonical residues it contains, treating them as a multiset. This order-independence accommodates vectorized reordering and layout variations.
- Corroboration: The presence of Keccak round constants (used by the underlying SHAKE function) is checked as a secondary condition to strengthen confidence, though it is not a hard gate to avoid false negatives.
- Attribution: The total byte count of the twiddle tables serves as a provenance marker. Different implementation lineages (e.g., reference C, Go standard library, Chrome/BoringSSL) store distinct numbers of tables (1, 2, or 3), allowing the tool to attribute the binary to a specific source lineage.

Key Contributions

Derivation Procedure: A general method to generate fingerprint sets for any transform-based lattice scheme from public parameters alone, ensuring coverage of future or unexamined implementations.
Robust Detector: A scoring mechanism that normalizes data and uses multiset matching to achieve high recall across different compilers, optimization levels, and obfuscation techniques, with an analytically derived false-positive bound.
Lineage Attribution: A demonstrated capability to distinguish between principal implementation lineages (C-reference vs. from-specification) based solely on the configuration and count of constant tables, without access to source code.
Operational Validation: The method is validated in two specific contexts: forensic examination (analyzing seized disk images where execution is impossible) and migration assurance (verifying vendor claims against shipped binaries).

Experimental Results

Recall and Precision: In experiments across four independent implementation lineages (C, Go, Rust, BoringSSL) and all build transformations (including stripping, static linking, and LLVM instruction substitution), Kestrel achieved 128/128 recall for ML-KEM and 255/256 for ML-DSA (the single miss is a known reference implementation quirk, not a detection failure). Precision was 100% with zero false positives.
System Sweep: A scan of 6,224 binaries from a production Linux system revealed zero false positives. It identified 12 distinct uncatalogued programs containing ML-KEM, including the OpenSSH key-exchange binary and the container-management stack (containerd, docker, runc). Notably, the container tools contained PQC code inherited from the Go language runtime without the project maintainers' explicit awareness.
Forensic Recovery: In a trial involving a deleted binary on a disk image, conventional file carving failed to recover the file. However, Kestrel successfully detected the ML-KEM table by scanning the raw unallocated space, demonstrating that the signal survives file-level destruction.
Adversarial Evasion: The tool resisted trivial evasions (reordering, padding, splitting tables). Only a "byte-rewrite" evasion (XORing the table with a runtime key) defeated detection, which requires substantive modification of the cryptographic code.

Significance and Claims
The paper asserts that Kestrel provides the first practical method for verifying the presence of post-quantum lattice schemes in stripped binaries, addressing a blind spot in current migration and forensic tooling.

Compliance: It enables the verification of statutory migration deadlines by confirming that a binary actually contains the claimed PQC primitives, rather than relying on vendor declarations or source-level scans.
Forensics: It allows examiners to distinguish genuine PQC implementations from fraudulent claims (e.g., malware that claims PQC but uses RSA) and to detect PQC in deleted or damaged files.
Scope Limitation: The author explicitly states the method's boundaries: it applies only to lattice schemes with stored transform tables (ML-KEM, ML-DSA) and assumes ordinary build practices. It does not cover hash-based schemes (SLH-DSA), schemes that compute constants at runtime, or managed runtimes where constants may be emitted as instructions rather than data tables.

The paper concludes that while the technique of constant matching is established, its application to post-quantum primitives in stripped binaries is novel and necessary, as these primitives leave a fingerprint that ordinary compilation cannot remove.

Technical Summary: Static Detection of Post-Quantum Cryptographic Algorithms in Stripped Binaries

More like this