Security › kem-32 · Constant-time review · Performance: x86_1 · arm_1

QCTM (kem-32)

kem-32-1: Debug path retains the secret error vector

Follow-up source: QCTM team's 2026-10-08 response

When the LOCALLY_QUASI_CYCLIC_TWISTED_MCELIECE_TRACE_DEC environment variable is present, encapsulation copies the fixed-weight secret error positions into file-static process-global storage. The same opt-in trace path prints decoder stages, syndrome-difference counts, decoded weight, and failure-location diagnostics to standard error.

The logic is present in the compiled QCTM128, QCTM256, and QCTM512 reference sources. The retained error positions are secret per-encapsulation material and should be erased after ciphertext construction, not persisted for a later decoder trace.

The static buffer has no exported accessor, so merely setting the environment variable does not reveal its contents to a remote KEM caller. Exploitation additionally requires stderr visibility, local/in-process memory access, or another disclosure primitive. This is a confirmed implementation-security and secret-lifetime defect, not a demonstrated remote key-recovery attack.

Proposed fixes

In its 2026-10-08 response, the QCTM team says it removed the global error-position storage and trace diagnostics and added clearing of temporary error buffers in both implementation trees. This records the team's revision without evaluating it.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

This is a source-level secret-lifetime check, not a remote exploit. Fetch the official archive, then inspect the QCTM128 reference kem.c at lines 15–20 (file-static buffer), 523–531 (trace use), and 641–645 (copy from the fresh encapsulation error). The QCTM256 and QCTM512 reference files have the same pattern.

IDS=kem-32 ./download.sh
./extract.sh kem-32
rg -n 'debug_last_error|TRACE_DEC' kem-32/Implementations/Reference_Implementation/QCTM*/kem.c

kem-32-2: Same-key multi-instance decoding misses QCTM-128 and -256 targets

Follow-up source: QCTM team's 2026-10-08 response

Additional reference: May and Sá Diogo, Multi-Instance Security Degradation of Code-Based KEMs, ePrint 2026/517, pinned 2026-06-12 version

QCTM encapsulation publishes C=H e^T for a fresh weight-w error under a reusable public key. The order-19 circulant part gives 19 public rotated targets for every observed ciphertext. Omitting the two non-circulant tail checks while searching gives effective dimensions 4,958, 9,784 and 19,892; the fixed-weight parity restores the remaining check. A candidate rotation is unshifted and verified against the complete public syndrome, after which K=H(1,e,C) is public.

May and Sá Diogo's pinned DS-DOOM estimator gives:

The attacks are passive, use fewer than 2^80 observed encapsulations, and need no decapsulation queries. The specification describes cached public-key state for encapsulation and reuse of decoded secret-key state across calls (§7.4), and states no per-key session cap. A hypothetical 2^64-ciphertext limit would avoid the crossings, but neither the NGCC call nor QCTM imposes one. The 128- and 256-bit claims are therefore missed and the finding is Critical.

The margins are narrow: 0.339 and 0.664 bits under this single heuristic DS-DOOM cost model, with memory estimates of 2^95.592 and 2^96.271 bits. Reducing the allowed observation exponent by one removes both reported crossings. The classification applies the policy's strict below-target rule to the cited model; it should be revisited if a better-supported cost model moves either estimate above its target.

Proposed fixes

In its 2026-10-08 response, the team reports increasing QCTM128's code length from 10,070 to 10,545 and QCTM256's from 19,000 to 19,551. It gives revised DS-DOOM estimates of 2^136.294 and 2^264.170 bit operations under the stated multi-instance model; QCTM512's length remains 38,000. The revised sets require new keys and test vectors. These proposals are recorded without evaluating them.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

Install numpy and scipy, then run:

python3 kem-32/reproduce_multi_instance.py

The witness downloads the official estimator at commit 39b78dcc077793cfa3ccdce8d032ece76825ca55, verifies both its archive and doom.py hashes, reproduces each crossing and its preceding above-target point, and checks the 512-bit control.

kem-32-3: The bundled RNG limits QCTM-512 key-generation and encapsulation randomness to 384 bits

The submitted QCTM512 builds link a bundled AES256-CTR-DRBG (Reference_Implementation/QCTM512/Makefile:33–42,54–63). Its entire state is a 32-byte Key and 16-byte V (rng.h:19–23, rng.c:113–129). The KAT program seeds it with 48 bytes. The only supplied path that seeds it from the external RBG is an adapter labelled api-pkc-kat, which likewise draws 48 bytes before every kem_keygen (KEM_AlgorithmInstance.c:18–27,70–86, also in the optimized tree). The local generator supplies the 64-byte seed to deterministic key generation (kem.c:557–592, seeded_keygen.c:797–848).

An attacker can enumerate the 2^384 possible bundled-RNG states, reproduce each candidate public key, and retain its decapsulation key on a match. The published x86_1 benchmark measures QCTM512 key generation at about 793.78 billion cycles (2^39.5); using that as an indicative per-trial cost gives about 2^424 cycles total, below the 512-bit target (§3.1 and §3.2.3, physical pp. 5–6). This does not rely on predicting or resetting the external RBG: replacing it by an ideal source still leaves the 48-byte local state. The bound is theoretical; no exhaustive search was run, and it does not describe a build that replaces the bundled RNG.

Extended on 2026-10-17: encapsulation uses the same bundled DRBG. kem_enc calls ensure_local_rng_from_api_pkc_drng (KEM_AlgorithmInstance.c:111). That function seeds the local generator with 48 bytes only if it has not been seeded already (:31–37). Otherwise it continues the state left by key generation or by an earlier encapsulation. crypto_kem_enc takes its error vector from fixed_weight_random (kem.c:640), which reads the bundled randombytes (m2e.c:61). The shared secret is hash_session_key(ss, 1, e, ct) (kem.c:650). Every encapsulated key is therefore a deterministic function of a 48-byte Key‖V state. Given (pk, ct), an attacker can enumerate the 2^384 states, regenerate e, and match its syndrome against ct. This recovers the shared secret without decapsulation queries, below the 512-bit target, and it applies to an encapsulating party that never generated a key. In a process that seeded the generator at key generation, the state recovered from the public key also determines the later encapsulations made by that process. The optimized tree has the same path (KEM_AlgorithmInstance.c:109, kem.c:875,885, m2e.c:60). This extension was checked by source only. No search was run.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 kem-32/reproduce_bridge_seed_ceiling.py

The certificate checks the submitted build flags, bundled RNG state, and bridge-to-keygen-seed source path. It is a source-and-counting argument, not a full-size key recovery.

kem-32-4: Folding exposes an ordinary Goppa quotient of the public code

Original source: Liping Wang's QCTM structural-analysis post Follow-up source: Yongge Wang's 2026-11-02 PKC Forum post

Additional reference: Weis, Improving GIJS Key Recovery for Classic McEliece, ePrint 2026/1984

The specification argues that the twisted construction prevents a direct folding attack (§6.3, physical pp. 19–20). In the submitted public-key construction, however, the twist is confined to the omitted final field row: the published matrix uses the first t−1 ordinary syndrome rows plus an all-ones parity row (reference QCTM128 goppa.c:1889–1893,2050–2127; decode.c:103–139; the other trees use the same construction). The support consists of 19-element orbits (seeded_keygen.c:610–691). Folding the public matrix across each orbit therefore exposes an ordinary degree-t/19 Goppa check space with one parity row. Puncturing one coordinate gives an ordinary binary Goppa code.

The exact public and secret-oracle row spaces agree on the archived KAT keys for all three sets:

This defeats the stated rationale for excluding ordinary-Goppa structural analysis, hence Medium. The forum post estimates quotient key recovery using Weis's heuristic GIJS model. Yongge Wang's 2026-11-01 analysis, §4, derives an explicit character-projection lift from a recovered quotient description and demonstrates decapsulation on two scaled instances. Its lift assumes the returned description has the stated affine/Frobenius equivalence and that the alignment system has a unique solution; neither a real QCTM quotient key nor a full-size decapsulation key has been recovered. The construction strengthens the route to kem-32-5 without establishing its heuristic key-recovery cost.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

sh kem-32/reproduce_folded_quotient.sh

The wrapper downloads the SHA-256-pinned submitted archive and checks the public quotient against the secret Goppa description for KAT record 0 of each set. The private key is used only as an independent oracle for the row-space comparison; the quotient is derived from the public key alone. The witness does not recover a decapsulation key.

kem-32-5: Reported structural key recovery for QCTM256 and QCTM512

Original source: Liping Wang's QCTM structural-analysis post Follow-up source: Yongge Wang's 2026-11-02 PKC Forum post

Additional reference: Weis, Improving GIJS Key Recovery for Classic McEliece, ePrint 2026/1984

The public QCTM code exposes an ordinary Goppa quotient of degree 27 or 53 for these sets. The reporter applies Weis's heuristic GIJS key-recovery model to that quotient, estimating the costs above (or 2^176.7 and 2^177.7 bit operations with square-root memory charging). If this yields full QCTM decapsulation keys at comparable cost, both estimates fall below the claimed 256- and 512-bit levels.

Two decisive steps remain open: the GIJS/Weis assumptions have not been established at these quotient degrees, and quotient-key recovery has not been demonstrated on a QCTM key. Wang's follow-up analysis supplies a polynomial-time conditional lifting algorithm and a scaled-key implementation. We ran its toy witness with two seeds, including an extra Frobenius twist: in both runs the lifted key matched the public code and decoded a fresh error. The proof's one-dimensional alignment condition is heuristic and was checked on those instances, not on full QCTM keys. No full-size key recovery or full-scheme attack has been executed. This remains a candidate-specific Critical lead. The archived-key audit in kem-32/reproduce_folded_quotient.sh confirms only the prerequisite quotient.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 kem-32/reproduce_lift_toy.py

The wrapper fetches Wang's hash-pinned toy script and checks two scaled-key lifts and fresh-error decodings. The quotient key is supplied to the toy; this does not recover a quotient key or decapsulate a full-size QCTM ciphertext.