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

DTRU (kem-14)

kem-14-1: Caller-declared ciphertext length overflows a decapsulation stack buffer

Follow-up source: DTRU team's confirmation and fix

The official kem_dec API accepts a caller-supplied ct_len_bytes, but the reference implementation does not verify it against the instance's fixed ciphertext length. It copies that many bytes into a stack buffer sized for the fixed ciphertext plus Z and a short prefix, then writes Z at offset ct_len_bytes. A correctly allocated, longer input therefore causes an out-of-bounds stack write inside decapsulation. The same unchecked loops appear in all seven reference source trees.

For DTRU-Light, a valid 512-byte ciphertext decapsulates to the honest shared secret; passing those same bytes followed by 48 allocated zero bytes with declared length 560 aborts with stack-smash detection. DTRU-1024 behaves likewise at lengths 1280 and 1360. The effect is memory corruption and availability loss, not a demonstrated confidentiality break. An application that enforces the exact ciphertext length before calling the library can avoid this path, but the submitted API does not enforce that requirement itself.

The DTRU team confirmed the missing validation. Its broader review also found that some optimized paths read the fixed ciphertext size even when the caller supplied a shorter allocation; that is the undersized-input manifestation of the same missing API-length validation.

Proposed fixes

The DTRU team's response proposes exact fixed-ciphertext-length checks before processing or buffer access in every reference, AVX2, resource-optimized, and ARM decapsulation entry point. 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).

make -C kem-14 exploit

The witness tests two independent instances, gives the library an input allocation matching the declared length, checks normal decapsulation first, and isolates each crash in a subprocess. It prints ATTACK kem-14-1 ... CONFIRMED for both.

kem-14-2: Decapsulation return value exposes the implicit-rejection branch

Original source: DTRU team's PKC Forum disclosure and fix

The specified FO transform uses implicit rejection: an invalid ciphertext yields a pseudorandom rejection key without revealing which branch was selected. Every reference kem_dec instead ends with return fail;, returning 0 after successful re-encryption and 1 after failure even though the shared-secret buffer is selected in constant time. Thus a correctly sized modified ciphertext exposes its validity directly through the API.

This signal alone is not a demonstrated IND-CCA break: explicit-rejection FO variants can be secure, and the contest API has an error return. The finding is the implementation's violation of DTRU's specified implicit-rejection contract. The DTRU team confirmed the discrepancy.

Proposed fixes

The DTRU team's response proposes retaining constant-time key selection, returning 0 on every correctly sized decapsulation, and reserving negative returns for public-API input errors. 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).

make -C kem-14 exploit-rejection-contract

The witness first checks an honest encapsulation, then changes one ciphertext byte and requires the submitted decapsulator to return 1 while producing a deterministic rejection key. It also source-checks the same return fail; path in all seven reference trees and prints ATTACK kem-14-2 ... CONFIRMED.

kem-14-3: Rejection key omits the specified public-key binding

Original source: DTRU team's PKC Forum disclosure

The specification derives the rejection key as H1(ID(pk), z, c). All seven reference implementations instead compute pseudohash(512, c || z): ID(pk) is absent, the operands are reversed, and the ordinary hash is reused without the specified domain separation. Consequently, distinct keys containing the same rejection seed return the same rejection key for a common invalid ciphertext, even when their public keys differ.

The submitted generator samples z independently, so this correlated-key witness is not an attack on honestly and independently generated keys and does not establish an IND-CCA break. It demonstrates precisely the missing multi-key binding that the specified ID(pk) input is intended to provide. The DTRU team independently identified the omission.

Proposed fixes

The DTRU team's response announces an updated implementation after noting that the code omits the specification's ID(pk) input. This section records the proposal without inferring implementation details or evaluating it.

Reproducing

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

make -C kem-14 exploit-rejection-contract

The witness generates two different keys, copies only the first key's 32-byte rejection seed into the second secret key, and decapsulates one invalid ciphertext under both. The rejection keys become identical; retaining the second key's original seed is a negative control and produces a different value. It prints ATTACK kem-14-3 ... CONFIRMED.

kem-14-4: Ring-paired DoubleE8 blocks invalidate DTRU's failure estimates

Follow-up source: DTRU team's 2026-10-11 response

Reference: Xiao, ePrint 2026/2250

The specified DoubleE8 decoder joins an E8 octet with coefficients shifted by n/2 (§1.1 and Algorithm 2, physical pp. 2–3). The submitted DTRU-768/-1024/-1536/-2048 code does the same (poly.c:159, :151, :180, :151); DTRU-648 instead shifts by 320 (poly.c:159), leaving four n/2-separated pairs within each 16-coefficient block. Multiplication in Z[x]/(x^n-x^(n/2)+1) couples those pairs, whereas the submitted DFR analysis treats decoder inputs as independent (Theorem 1 and §2.3, physical pp. 8–9). Xiao's covariance-aware model gives block eigenvalues around 0.3 and 1.6–2.1 times the marginal variance. Its uncapped first-failure estimates are about 2^85.4, 2^97.9, 2^104.6, 2^96.3, 2^100.7 and 2^110.8 in the Affected order above, 50–110 bits below the submitted DFR exponents. At the call's 2^80 decapsulation ceiling, Table 5 gives total costs of 2^83.7, 2^86.0, 2^98.9, 2^79.8, 2^94.5 and 2^116.1. DTRU-Light's power-of-two ring does not have this pairing. For odd-dimensional DTRU-Prime, the specification does not state the DoubleE8 layout; its listed result is conditional on Xiao's assumed offset floor(n/2)=543.

A failing honest encapsulation is recognizable from its known shared key. The paper develops directional follow-ups and a toy secret-correlation experiment, but no full-size recovery. Its normal-tail fits use 200 ciphertexts and extrapolate the extreme tails. Its DTRU-648 and Prime exponents assume offsets different from those in the delivered code, so those numbers are conditional rather than code-specific estimates. The result therefore establishes a substantive failure-proof gap rather than a completed attack.

Further extension to Xiao's analysis: direct public multiplication-matrix calculations on all five tricyclotomic dimensions give paired correlations around -0.65 and normalized 16-row covariance eigenvalues from about 0.27 to 2.12. This independently certifies structural non-independence, not the extreme-tail DFR estimates. Even the submission's own DFR values leave Theorem 3's (qH+qD) delta term far above every target when qD=2^80 (physical p. 12).

In its 2026-10-11 response, the team says its DFR tests arrange tricyclotomic coefficients consecutively to avoid correlated pairs and reports four reduced-strength stress tests. That arrangement differs from the frozen decoder's eight-plus-eight layout above; the stress tests do not establish the submitted full-strength tail bounds. The team says a formal justification will follow. No revised scheme is evaluated here.

Reproducing

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

python3 kem-14/reproduce_dtru_covariance.py

The dependency-free certificate constructs the multiplication rows, checks their paired correlations and spectrum, and evaluates the submitted DFR exponents at 2^80 queries. It does not reproduce the paper's tail fitting or a key-recovery attack.