OAEP-NTRU

Non-canonical ciphertext byte encodings decapsulate to the challenge key

Minor break · Demonstrated · Cause: specification text

Property: IND-CCA security

Cost against claim: one decapsulation query wins IND-CCA2 with the challenge key, no secret key or plaintext recovery

Because the byte width used to encode each ring coefficient exceeds log2(q), every coefficient below a small threshold has two distinct byte encodings of the same ring element, and the decapsulation algorithm accepts either one and returns the same key. An attacker who takes a challenge ciphertext, re-encodes one such coefficient, and submits the result to the decapsulation oracle recovers the challenge key in a single query, winning the designers' own IND-CCA2 game.

What causes it

DecodePoly (Algorithm 12 for 13-bit fields, Algorithm 14 for 15-bit fields, pp. 11 and 13) reads raw bytes into coefficients with no reduction or range check, so a byte string encoding v and one encoding v+q decode to the same element of Z_q; EncodePoly (Algorithm 11/13) only ever emits fields below q, so any adversarial re-encoding above q is new to the oracle. Decap (Algorithm 3, p. 7) reads the ciphertext bytes once through DecodePoly, performs no re-encryption and no ciphertext comparison, and rejects only when the tag sigma differs from the challenge's; the designers' own game (Figure 7, p. 26) likewise refuses only ct = ct*. Table 1 (p. 15) gives q = 7129/17497/28513 against byte widths of 13/15/15 bits, so a fraction 0.149/0.873/0.149 of coefficients admit a second encoding.

Evidence

The re-encoded ciphertext was submitted to the unmodified reference, optimized (AVX2) and additional implementations of all three parameter sets against the 10 official KAT ciphertexts of each, using a byte-level codec written independently from Algorithms 11 to 14 (not the original attacker's codec). Re-encoding the smallest, largest or a random aliasable coefficient succeeded on 10 of 10 official vectors in all 9 builds. Re-encoding every aliasable coefficient at once succeeded in the reference and additional builds (10/10 for 648 and 2592, 2/10 for 1296) but not in the AVX2-optimized 1296 build (0/10), whose 16-bit arithmetic rejects fields near 2¹⁵; single-coefficient re-encoding still succeeds there in 9,649 of 11,220 cases (86 percent, every alias with v+q under 23,223 accepted). A second PQC-X member re-ran the original attacker's malleation and decapsulation scripts, got byte-identical logs, then independently confirmed the codec and the byte counts from a fresh, unmodified build.

Cause in the specification, traced to the specification text.

Limits

Benign malleability only: it gives no secret-key or plaintext recovery by itself. The spec-level count of about 2⁹⁷/2¹¹³¹/2³⁸⁷ simultaneous re-encodings per ciphertext holds for the specification and for 8 of the 9 builds; the AVX2-optimized 1296 build only reliably accepts single-coefficient re-encoding, already enough for the break.

Credit

Found by PQC-X.

Honest ciphertexts are distinguishable from uniform byte strings

Holds · Demonstrated · Cause: construction

Property: ciphertext pseudorandomness (PR-CCA); IND-CCA2 unaffected

Cost against claim: testing that all fields are below q distinguishes with advantage close to 1, no query; not a call requirement

Every honest ciphertext's polynomial part comes from EncodePoly, which only ever produces coefficient values below q, while a uniform byte string has all of its coefficients below q with a small, exactly computable probability. Testing whether every field is below q therefore separates honest ciphertexts from uniform byte strings with advantage close to 1 and no query, even though the designers' PR-CCA proof treats the ciphertext space as the ring itself, where this byte-level test has no meaning.

What causes it

EncodePoly (Algorithm 11/13) maps into [0, q) by construction. The PR-CCA claim (Definition 14, p. 25; Figure 7 and Theorem 16, p. 26; Table 7, p. 32, ticked for OAEP-NTRU) is proved in Figure 10 (pp. 47 to 48) by sampling the ciphertext's ring part uniformly over R_q, the trapdoor function's range, and never defines the byte-string ciphertext space that the concrete scheme actually transmits.

Evidence

The probability that a uniform byte string's polynomial part has every coefficient below q, (q / 2^bits)^n computed exactly as a rational, is 2^-129.93 / 2^-1173.11 / 2^-520.13 for the three sets; the official ciphertexts' maximum observed fields (7128/17494/28512) confirm every honest field is below q. The original report's figures of 2^-130 and 2^-1173 match; its 2^-521 figure for the largest set should be 2^-520.1. A second PQC-X member recomputed the same exact rationals independently and confirmed the report's cited log does not contain them (it holds a different quantity, the probability of no alias at all).

Cause in the specification, traced to the specification text.

Credit

Found by PQC-X.