[GH-ISSUE #3724] [Feature] Post-quantum cryptography reverse engineering: ML-KEM, ML-DSA and SLH-DSA fingerprints, parameters and migration inventory #1435

New issue

Open

opened 2026-10-16 21:05:25 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-16 21:05:25 +00:00

Owner

Originally created by @matbrgz on GitHub (Oct 14, 2026).
Original GitHub issue: https://github.com/morluto/rea/issues/3724

Problem Statement & Context

With NIST officially standardizing post-quantum cryptographic (PQC) standards in FIPS 203 (ML-KEM / Kyber), FIPS 204 (ML-DSA / Dilithium), and FIPS 205 (SLH-DSA / SPHINCS+), modern software architectures are actively migrating away from classical RSA and Elliptic Curve Cryptography (ECC).

In reverse engineering, identifying cryptographic primitives is essential for understanding protocols, software protections, and secure communications. However, post-quantum algorithms exhibit fundamentally different mathematical and structural characteristics compared to classical public-key cryptography:

Lattice-Based Structures (ML-KEM / ML-DSA): High-degree polynomial arithmetic over polynomial rings (R_q = \mathbb{Z}_q[X]/(X^{256} + 1)), Number Theoretic Transform (NTT) butterfly loops, and rejection sampling.
Signature & Key Dimensions: Distinctive key and ciphertext sizes:
- ML-KEM-512 / 768 / 1024: Public keys (800 to 1568 bytes), ciphertexts (768 to 1568 bytes).
- ML-DSA-44 / 65 / 87: Public keys (1312 to 2592 bytes), signatures (2420 to 4627 bytes).
- SLH-DSA: Extremely large signatures (up to 49 KB) utilizing stateless hash trees.
Hybrid Cryptographic Suites: Coexistence of classical algorithms and PQC algorithms (e.g. X25519 + ML-KEM-768 hybrid key exchanges in TLS 1.3 / SSH).
Hash Function Pipelines: Extensive usage of Keccak / SHAKE128 / SHAKE256 / SHA3-512 for polynomial expansion and random sampling.

REA requires a dedicated post-quantum cryptography analyzer capable of fingerprinting PQC implementations in static binaries, firmware, and network protocols.

Proposed Architecture

flowchart TD
    A["Binary / Firmware / Network Capture"] --> B["Post-Quantum Cryptography Analyzer"]
    B --> C["Algorithmic Constant & S-Box Scanner"]
    B --> D["NTT Loop & Polynomial Kernel Recognizer"]
    B --> E["Key & Signature Dimensional Fingerprinter"]
    B --> F["Hybrid Protocol & Migration Inventory"]
    
    C --> C1["Keccak / SHAKE Permutation Constants"]
    C --> C2["Modulus Values (q=3329 for ML-KEM, q=8380417 for ML-DSA)"]
    
    D --> D1["NTT Twiddle Factor Tables"]
    D --> D2["Barrett & Montgomery Reduction Assembly Patterns"]
    
    E --> E1["Buffer Allocations Matching Exact PQC Key/Ciphertext Sizes"]
    E --> E2["Stateful / Stateless Hash Tree Structures"]
    
    F --> F1["TLS 1.3 / SSH Hybrid Key Exchange Suites"]
    F --> F2["Cryptographic Migration Inventory & Posture Report"]
    
    C & D & E & F --> G["Synthesized PQC Bill of Materials (PQC-BOM) & Call Graph"]

Technical Capabilities & Modules

Mathematical Constant & Modulus Detection:
- Scan for canonical lattice modulus constants in data and immediate instructions:
  - q = 3329 (0x0D01): ML-KEM (Kyber).
  - q = 8380417 (0x007FE001): ML-DSA (Dilithium).
  - Number Theoretic Transform (NTT) twiddle factor tables (\zeta exponents).
- Scan for Keccak round constants and SHAKE-128/256 sponge permutation loops.
NTT Arithmetic Loop & Kernel Recognition:
- Disassemble and detect Cooley-Tukey or Gentleman-Sande NTT butterfly loops.
- Detect optimized Barrett and Montgomery modular reduction assembly idioms across x86-64 (AVX2/AVX-512) and ARM64 (NEON).
Key, Ciphertext & Buffer Size Fingerprinting:
- Detect static buffer allocations and structure fields matching exact standardized PQC dimensions.
- Classify candidate implementations into specific security levels (e.g. Level 2, Level 3, Level 5).
Hybrid Protocol Handshake Analysis:
- Inspect recorded TLS 1.3 and SSH handshakes to identify post-quantum and hybrid key exchange cipher suites (e.g., X25519MLKEM768, secp256r1_mlkem768).
- Extract public key shares and verify protocol negotiation framing.
Cryptographic Bill of Materials (PQC-BOM) Generation:
- Synthesize a comprehensive cryptographic inventory detailing:
  - Identified algorithms (classical vs hybrid vs post-quantum).
  - Exact algorithm parameters and FIPS conformance status.
  - Call sites and functions interacting with PQC primitives.

Acceptance Criteria

Automated identification of ML-KEM, ML-DSA, and SLH-DSA implementations in native binaries (x86, ARM).
Detection of NTT loop kernels and modular reduction constants.
Detection and decoding of PQC / hybrid key exchange handshakes in network captures.
Generation of a Cryptographic Bill of Materials (PQC-BOM) flagging post-quantum readiness.
Zero false positive confusion between PQC lattice loops and standard matrix multiplication code.

Complements #3621 (Unknown binary file-format inference)
Complements #3624 (Native C++ semantic reconstruction)

Originally created by @matbrgz on GitHub (Oct 14, 2026). Original GitHub issue: https://github.com/morluto/rea/issues/3724 [![Type: Feature](https://img.shields.io/badge/type-feature-blue.svg?style=flat-square)](https://github.com/morluto/rea) [![Domain: Reverse Engineering](https://img.shields.io/badge/domain-reverse_engineering-blueviolet.svg?style=flat-square)](https://github.com/morluto/rea) [![Status: Proposed](https://img.shields.io/badge/status-proposed-blue.svg?style=flat-square)](https://github.com/morluto/rea) [![Ecosystem: REA](https://img.shields.io/badge/ecosystem-morluto%2Frea-8A2BE2.svg?style=flat-square)](https://github.com/morluto/rea) ### Problem Statement & Context With NIST officially standardizing post-quantum cryptographic (PQC) standards in FIPS 203 (ML-KEM / Kyber), FIPS 204 (ML-DSA / Dilithium), and FIPS 205 (SLH-DSA / SPHINCS+), modern software architectures are actively migrating away from classical RSA and Elliptic Curve Cryptography (ECC). In reverse engineering, identifying cryptographic primitives is essential for understanding protocols, software protections, and secure communications. However, post-quantum algorithms exhibit fundamentally different mathematical and structural characteristics compared to classical public-key cryptography: 1. **Lattice-Based Structures (ML-KEM / ML-DSA)**: High-degree polynomial arithmetic over polynomial rings ($R_q = \mathbb{Z}_q[X]/(X^{256} + 1)$), Number Theoretic Transform (NTT) butterfly loops, and rejection sampling. 2. **Signature & Key Dimensions**: Distinctive key and ciphertext sizes: - ML-KEM-512 / 768 / 1024: Public keys (800 to 1568 bytes), ciphertexts (768 to 1568 bytes). - ML-DSA-44 / 65 / 87: Public keys (1312 to 2592 bytes), signatures (2420 to 4627 bytes). - SLH-DSA: Extremely large signatures (up to 49 KB) utilizing stateless hash trees. 3. **Hybrid Cryptographic Suites**: Coexistence of classical algorithms and PQC algorithms (e.g. X25519 + ML-KEM-768 hybrid key exchanges in TLS 1.3 / SSH). 4. **Hash Function Pipelines**: Extensive usage of Keccak / SHAKE128 / SHAKE256 / SHA3-512 for polynomial expansion and random sampling. REA requires a dedicated post-quantum cryptography analyzer capable of fingerprinting PQC implementations in static binaries, firmware, and network protocols. ### Proposed Architecture ```mermaid flowchart TD A["Binary / Firmware / Network Capture"] --> B["Post-Quantum Cryptography Analyzer"] B --> C["Algorithmic Constant & S-Box Scanner"] B --> D["NTT Loop & Polynomial Kernel Recognizer"] B --> E["Key & Signature Dimensional Fingerprinter"] B --> F["Hybrid Protocol & Migration Inventory"] C --> C1["Keccak / SHAKE Permutation Constants"] C --> C2["Modulus Values (q=3329 for ML-KEM, q=8380417 for ML-DSA)"] D --> D1["NTT Twiddle Factor Tables"] D --> D2["Barrett & Montgomery Reduction Assembly Patterns"] E --> E1["Buffer Allocations Matching Exact PQC Key/Ciphertext Sizes"] E --> E2["Stateful / Stateless Hash Tree Structures"] F --> F1["TLS 1.3 / SSH Hybrid Key Exchange Suites"] F --> F2["Cryptographic Migration Inventory & Posture Report"] C & D & E & F --> G["Synthesized PQC Bill of Materials (PQC-BOM) & Call Graph"] ``` ### Technical Capabilities & Modules 1. **Mathematical Constant & Modulus Detection:** - Scan for canonical lattice modulus constants in data and immediate instructions: - $q = 3329$ (`0x0D01`): ML-KEM (Kyber). - $q = 8380417$ (`0x007FE001`): ML-DSA (Dilithium). - Number Theoretic Transform (NTT) twiddle factor tables ($\zeta$ exponents). - Scan for Keccak round constants and SHAKE-128/256 sponge permutation loops. 2. **NTT Arithmetic Loop & Kernel Recognition:** - Disassemble and detect Cooley-Tukey or Gentleman-Sande NTT butterfly loops. - Detect optimized Barrett and Montgomery modular reduction assembly idioms across x86-64 (AVX2/AVX-512) and ARM64 (NEON). 3. **Key, Ciphertext & Buffer Size Fingerprinting:** - Detect static buffer allocations and structure fields matching exact standardized PQC dimensions. - Classify candidate implementations into specific security levels (e.g. Level 2, Level 3, Level 5). 4. **Hybrid Protocol Handshake Analysis:** - Inspect recorded TLS 1.3 and SSH handshakes to identify post-quantum and hybrid key exchange cipher suites (e.g., `X25519MLKEM768`, `secp256r1_mlkem768`). - Extract public key shares and verify protocol negotiation framing. 5. **Cryptographic Bill of Materials (PQC-BOM) Generation:** - Synthesize a comprehensive cryptographic inventory detailing: - Identified algorithms (classical vs hybrid vs post-quantum). - Exact algorithm parameters and FIPS conformance status. - Call sites and functions interacting with PQC primitives. ### Acceptance Criteria - [ ] Automated identification of ML-KEM, ML-DSA, and SLH-DSA implementations in native binaries (x86, ARM). - [ ] Detection of NTT loop kernels and modular reduction constants. - [ ] Detection and decoding of PQC / hybrid key exchange handshakes in network captures. - [ ] Generation of a Cryptographic Bill of Materials (PQC-BOM) flagging post-quantum readiness. - [ ] Zero false positive confusion between PQC lattice loops and standard matrix multiplication code. ### Related Issues & Dependencies - Complements #3621 (Unknown binary file-format inference) - Complements #3624 (Native C++ semantic reconstruction)

bsakaguchi referenced this issue

2026-10-31 00:29:35 +00:00

[GH-ISSUE #2357] [Roadmap] Track scoped static artifact and recorded-crash improvements #781

bsakaguchi referenced this issue

2026-10-31 00:29:41 +00:00

[GH-ISSUE #2383] [Tracker] Audit analysis and debugging coverage for the TIOBE top 100 languages (October 2026) #794

bsakaguchi referenced this issue

2026-10-31 00:30:38 +00:00

[GH-ISSUE #3582] [Tracker] Ready to close or merge: issues and pull requests (October 2026) #1330

bsakaguchi referenced this issue

2026-10-31 00:30:54 +00:00

[GH-ISSUE #3795] [Tracker] Open documentation issues and pull requests (October 2026) #1468