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

TriQ-KEM (kem-37)

kem-37-1: Decapsulation re-expands its private support with variable work

crypto_kem_dec decrypts with a persistent PKE seed. The decryption path calls triq_dk_pke_from_string on every decapsulation, which regenerates the private support using vect_sample_fixed_weight1. Its sampler rejects out-of-range or duplicate positions and fetches more XOF bytes when extra draws exhaust a block (src/ref/vector.c:61-91). Thus the same public ciphertext can take seed-dependent work. The FO validity selection remains masked, but does not hide this earlier trace. No key-recovery attack is claimed; see constant_time.md.

Constant-time fix (moderate, hence Medium): store the expanded support in the private key instead of re-deriving it on every decapsulation, which changes the key format and storage, or sample it with a fixed number of draws and constant-time duplicate handling. Both are well-known techniques with moderate cost.

Reproducing

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

ct_dir=$(mktemp -d)
ref=kem-37/Implementations/Reference_Implementation/TriQ-KEM-128
cc -std=c99 -O3 -ffunction-sections -fdata-sections -Wl,--gc-sections \
  -I "$ref/src/common" -I "$ref/src/common/triq-128" \
  -I "$ref/src/ref" -I "$ref/src/ref/triq-128" -I "$ref" \
  -o "$ct_dir/repro" kem-37/reproduce_ct_sampler.c \
  "$ref/src/common/symmetric.c" "$ref/auxfunc.c"
"$ct_dir/repro"

The witness observes one XOF fetch for seed byte 0 and multiple fetches for seed byte 11 on this build. The full source path is src/common/kem.c:192 → src/ref/triq_pke.c:176 → src/ref/parsing.c:19-22 → src/ref/vector.c:61-91.

kem-37-2: FO re-encryption leaks the decrypted message through sampler timing

Original source: PKC Forum post and verification package

Decapsulation decrypts m_prime, derives theta_prime from it, and re-encrypts before comparing the ciphertext (src/common/kem.c:192–207). Re-encryption calls the bounded-density sampler twice (src/ref/triq_pke.c:113–115). That sampler exits as soon as a candidate passes its density test, so its iteration count depends on theta_prime and hence on the secret-dependent decrypted message (src/ref/vector.c:244–255); the optimized trees contain the same early exit. The masked final validity selection does not hide this earlier work. This operational dataflow contradicts the specification's statement that the bounded-density condition is public and independent of secret data (§III-B, p. 9).

The reporters measured a 7.9% probability that a full re-encryption needs at least one extra draw across its two sampler calls, corresponding to about 4.1% per call under the same model. The two timing classes differed by 37,227 cycles: one averaged 10,220,477 cycles and the one-extra-rejection class 10,257,704 cycles (z about 4.4); a quieter-host run reached z=5.6. A separate microbenchmark measured one extra sampler iteration at roughly 15,674 cycles, so the two figures measure different scopes. This is the re-encryption leakage mechanism used by the published Don't Reject This attack on related code-based KEMs. A TriQ-specific classifier is demonstrated, but a complete secret-key recovery is still in progress.

Constant-time fix (moderate, hence Medium): run a fixed, message-independent number of sampler candidates and use masks to select the first acceptable one. The original analysis estimates about 78% extra sampler work for a two-candidate schedule; that performance estimate and its residual failure probability have not been independently validated.

Proposed fixes

The original post proposes running exactly N_max sampler iterations with masked selection, or using another fixed message-independent schedule. This section records the proposal without evaluating it.

Reproducing

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

python3 kem-37/reproduce_reencrypt_sampler.py

The compact witness checks the decrypted-message-to-sampler dataflow and early exit in all four archived trees. It deliberately does not claim to reproduce a stable timing classifier or key recovery on every host.

kem-37-3: Same-key multi-instance decoding puts all TriQ-KEM sets below target

Original source: Wang's PKC Forum publication post

The first ciphertext component is u = r1+h*r2 (specification §III-C), with each vector's fixed weight 67, 132, 196 or 260. Ignoring the public bounded-density restriction gives a conservative [2n,n] syndrome-decoding instance of weight 2wr; each ciphertext has n cyclic rotations. The observations must be independently generated ciphertexts from other parties under the same public key, with ephemeral errors unknown to the attacker; attacker-generated encapsulations do not supply unknown decoding targets. A decoder returning the actual (r1,r2) exposes r2. Subtracting s*r2 from the second component leaves a publicly decodable codeword plus the designed weight-we error; the recovered message and public (ek,salt) then determine the shared key. The bounded-density condition makes the true error space smaller, but the estimator does not claim to exploit it.

These are the first below-target points under May and Sá Diogo's pinned heuristic DS-DOOM estimator; each preceding exponent is above target. The margins are below one bit, and a different operation-cost convention could change the verdict. The estimator counts cyclic rotations of each ciphertext as related targets. The published API imposes no per-key session cap. The pinned estimator, preceding above-target controls, and public ciphertext-to-key equations establish the stated model crossings, hence Critical / Confirmed. No full-size decoder run or end-to-end key recovery was performed.

Reproducing

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

NGCC_ESTIMATOR_PYTHON=/path/to/python-with-numpy-scipy python3 security/reproduce_code_multi_instance.py kem-37

The witness checks all four first crossings and preceding above-target controls against the hash-pinned official estimator.