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

HEP-QC (kem-17)

kem-17-1: Publicly reproducible secret keys

Key generation draws from a file-scope SHAKE-256 PRNG context that is never initialized by the KEM wrapper. The API-provided seeded DRNG is declared but never consumed. Each fresh process therefore begins from the same zero-initialized state and generates the same key pair.

Fresh-process tests with different API seeds produced identical public and secret keys for hep-qc-1, hep-qc-3, hep-qc-5, and hep-qc-7.

An attacker recovers a victim's secret key by starting a fresh process and invoking the submitted key-generation API once. No code-based cryptanalysis is required. The resulting secret key decapsulates the victim's ciphertexts, completely breaking the claimed KEM confidentiality.

The wrapper must initialize its PRNG from the supplied DRNG for every independent key-generation operation and must not rely on zero-initialized global state.

Reproducing

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

Build the candidate and the reproducer, then run:

make -C api harness && make -C tools && make -C kem-17
tools/ngcc_attack keygen-fresh kem-17/lib/libhep-qc-1.so 0x01   # repeat with a different seed

tools/reproduce.sh runs this together with the other supported runtime witnesses and their controls. See tools/README.md.

kem-17-2: HEP-QC-7 has at most 256 bits of key-generation support

This is independent of the implementation defect above. The HEP-QC-7 specification claims 512-bit classical security, but fixes seedKEM, every derived seed, and the shared key K at 32 bytes. KEM.KeyGen samples one 256-bit seedKEM and deterministically derives seedPKE and the complete PKE key pair from it.

There are consequently at most 2^256 HEP-QC-7 public keys. A generic attacker can enumerate seedKEM, regenerate the encapsulation key, and compare it with the target public key. A match supplies the corresponding decapsulation key. The 32-byte KEM output also has at most 256 bits of delivered-key capacity.

This is a specification-level parameter-selection break of the advertised 512-bit classical level. It is not made less valid by the submitted wrapper's much cheaper predictable-key failure; repairing the wrapper still leaves this 2^256 design ceiling.

Reproducing

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

Specification evidence is on physical PDF pages 12–14. Run:

python3 security/design_parameter_audit.py --report-id kem-17-2

kem-17-3: First encapsulation in each process is publicly reproducible

kem_enc draws both its message m and salt consecutively from a file-scope SHAKE-256 PRNG context. The wrapper never initializes that context from the API-provided DRNG, so it begins in the same zero-initialized state in every fresh process.

For a fixed public key, the first encapsulation in each fresh process consequently repeats both the ciphertext and shared secret. An attacker can run the public encapsulation algorithm in a fresh process with the recipient's public key and recover the exact first session key produced by another fresh process. Fixing key generation alone does not repair this independent KEM confidentiality failure.

Every encapsulation operation must obtain fresh entropy from the API DRNG or initialize a per-operation generator from it. Message and salt generation must not use predictable global state.

Reproducing

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

In all four parameter sets, kem_enc calls prng_get_bytes(m, ...) and then prng_get_bytes(salt, ...); the wrapper declares the initialized API DRNG but never uses it. The permanent witness compares fresh processes with different API seeds:

tools/reproduce.sh kem-17

It reports identical first public-key, ciphertext, and shared-secret digests for HEP-QC. The Aigis-Enc+ control differs across the two seeds.

kem-17-4: Public column multiplicities break the EPC-P assumption

Original source: NGCC PKC Forum report

HEP-QC repeats every column of its inner Reed–Muller generator MULT = n2/128 times before applying row mixing and a column permutation. Those operations preserve equality. The public matrix G' therefore has exactly n1*128 column classes of multiplicity MULT and 64 singleton columns, whereas a uniform matrix has no repeated columns except with negligible probability. This gives a public, linear-time distinguisher with advantage essentially one and directly falsifies the EPC-P assumption used by the specification's first security bound.

Tianyuan Xie's mailing-list analysis additionally reports recovery of the affine blocks and exact secret transformation T on 35/35 official keys. The remaining frame-label searches are estimated at 2^84.1, 2^131.0, and 2^198.7 for HEP-QC-1, -3, and -5, below their 128-, 192-, and 256-bit claims. The public attachment reproduces the distinguisher, but not the full transformation recovery, so those residual key-recovery costs are less independently reproducible than the confirmed EPC-P break.

Xie also identifies an independent gap in Theorem 6.3.1's EPC-P-only IND-CPA bound: replacing G' by a uniform matrix in Game 2 does not make the challenge ciphertext independent of the selected message. For fixed public s, the noise s*r2 + e has at most binomial(n,omega_r)*binomial(n,omega_e) possible values before truncation. Its translates by two messages' codewords are therefore almost surely disjoint for a uniform G' (their expected overlap is bounded by the square of that support size divided by 2^(n1*n2)). Thus the claimed statistical independence is false. This finite-support argument does not give an efficient ciphertext distinguisher; a computational assumption about the noise distribution is still needed. It is a proof gap, not a separate demonstrated KEM break.

Reproducing

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

make -C kem-17 lib/libhep-qc-1.so
python3 kem-17/reproduce_epcp_fingerprint.py

On a freshly generated official HEP-QC-1 key, this prints 3^5888 + 1^64; its uniform-matrix control prints 1^17728.

kem-17-5: Secret permutation and mixing matrix drive memory and control flow

HEP-QC decapsulation regenerates private y, mixing matrix t, and column permutation p from the secret seed (ref/PKE_HEP_QC.c:185-220). The permutation indexes output memory by P[old_col] (common/vector.c:498-503,477-485). The code then inverts private t using a value-dependent pivot search and conditional row operations (common/vector.c:369-408). These addresses and branches disclose information about secret key material to a sufficiently close observer. No remote channel, complete key recovery, or shared-secret extraction is demonstrated.

The same decapsulation key expansion also runs secret-seed rejection sampling, retry-until-invertible matrix generation, and a Fisher–Yates x % bound with hardware division in the reviewed GCC -O2 build (common/parsing.c:23-31, common/vector.c:64-76,343-357,416-423). These are additional paths within this finding, not separate demonstrated key-recovery attacks.

Constant-time fix (moderate, hence Medium): apply the secret permutation obliviously with a Beneš network, as Classic McEliece does, invert the mixing matrix with masked-pivot constant-time elimination, and replace the rejection sampling, the retry-until-invertible loop and the division-based Fisher–Yates shuffle with fixed-work constant-time equivalents. These are well-known techniques with moderate cost, although several components change.

Reproducing

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

The source-level witness is ref/KEM_HEP_QC.c:165-212 → ref/PKE_HEP_QC.c:185-220 → common/vector.c:369-408,477-503 under Implementations/Implementations/; the x86_64 PKE source calls the same shared routines. See constant_time.md for the secret/public mapping. This is not a measured timing benchmark.