Reports › kex-09 · Constant-time review

TriQ-KEX (kex-09)

kex-09-1: Decapsulation re-expands its secret key with a variable-length sampler

crypto_kem_dec() passes the persistent secret PKE seed to triq_pke_decrypt(), which calls triq_dk_pke_from_string() on every decapsulation. That function expands the seed through vect_sample_fixed_weight1(). Its support sampler repeats on rejected or duplicate secret-derived positions (vector.c:69-90), and refills an XOF buffer when the extra draws cross its boundary. Thus otherwise identical decapsulation calls perform a secret-key-dependent number of loop iterations and XOF calls. The four reference variants share the same sampler. This is a secret-dependent timing/control-flow leak, not an established full-key attack; see constant_time.md for the data-flow trace.

Reproducing

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

From the repository root, compile the witness against the submitted TriQ-128 source:

ct_dir=$(mktemp -d)
ref=kex-09/TriQ-KEX/Implementations/Reference_Implementation/TriQ-KEX-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" kex-09/reproduce_ct_sampler.c \
  "$ref/src/common/symmetric.c" "$ref/auxfunc.c"
"$ct_dir/repro"

The witness counts XOF fetch calls in the unmodified reference sampler. It prints CONFIRMED after finding two secret seeds (first byte 0 and 11 in this build) that require different call counts. An extra fetch performs another XOF invocation and allocation, making the paths observably different without a statistical timing test.

Follow-up analysis: decapsulation re-encryption also runs a bounded-density sampler on coins derived from recovered m_prime (src/common/kem.c:156-164, src/ref/triq_pke.c:96-98). This is a Guo et al.-style lead; no TriQ-specific key-recovery oracle is yet demonstrated.