Reports › kem-37 · Constant-time review

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.

Follow-up analysis: FO re-encryption also samples from coins derived from recovered m_prime (src/common/kem.c:192-200, src/ref/triq_pke.c:113-115). The Guo et al. HQC/BIKE attack suggests a test, not a proven TriQ recovery.

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.