Bugs in the submitted code; the specification is sound on these points.
ntre-i1
NTRE-512 key-generation seed halved to 256 bits in code
Minor break · Tested at small scale · Cause: code
Property: key recovery
Cost against claim: 2256 trials, about 2274 cycles classical, or about 2128 Grover iterations recover f and g, against 2512 classical / 2256 quantum required
NTRE-512 key generation (Algorithm 5, Algorithm 8) is specified to draw two 512-bit seeds and expand each with an XOF into a secret polynomial. Every reference and optimized implementation instead requests only 256 bits per seed (NTRE_SYMBYTES = 32), so exhaustively searching the seed space and checking a candidate against the public key recovers the secret key f, g in about 2256 classical trials, or roughly 2128 Grover iterations, both far below the 2512 classical / 2256 quantum the level 512 claim requires.
| Parameter set | Claim | Attack cost | Verdict |
|---|
| NTRE-512 | 512 classical, 256 quantum | 2256 trials, about 2274 cycles classical; about 2128 Grover iterations quantum | Minor break |
What causes it
Spec Algorithm 5 (Sample), line 1, draws s from B64, 512 bits, and Algorithm 8 (KeyGen) calls Sample once for f prime and once for g prime. NTRE_SYMBYTES is fixed at 32 in every params.h (reference, optimized and the Others copies); KEM_AlgorithmInstance.c requests NTRE_SYMBYTES*8 = 256 bits per polynomial (lines 98 to 104). The specification is sound; only the code's request length is wrong.
Evidence
The reported seed-search binary, re-run on two NTRE-512 keys and one NTRE-128 key, accepted exactly one candidate out of a reduced 216 search, the true seed, at about 218.1 to 218.3 cycles per trial. Independently, without reusing that code: a linker wrapper on the unmodified reference sources recorded every random-number request kem_keygen makes, exactly two 256-bit requests per key, and a separate re-implementation of CBD1 and the NTRU-ring multiplication, taking only the XOF output and the pk/sk bytes from the C side, confirmed the secret-key relation exactly on two keys and, over a reduced 212-candidate search, accepted only the true seed (a wrong candidate leaves 2 to 3 of 2304 coefficients out of range). The fresh reference build reproduces the official NTRE-512 KAT byte for byte.
Cause in the submitted code; the specification is not affected.
Limits
NTRE-128 and NTRE-256 are unaffected; only NTRE-512 falls below its target.
Credit
First public report: M.-J. Saarinen (ngcc.dev kem-27-1, 2026-09-23). Found independently by PQC-X.
ntre-i2
Reference decapsulation branches on every bit of the re-encrypted message
Holds · Argued · Cause: code
Property: message recovery
Cost against claim: one secret-dependent branch per message bit in the reference build's re-encryption, run in kem_enc and in every accepted kem_dec, exposing the encapsulated message and, through it, the session key
NTRE decapsulation re-encrypts the decrypted message before checking it, and the reference code's CBD prime 1 encoder branches on each message bit instead of computing the specification's pure formula. The compiled reference binary keeps one conditional jump per message bit, 2304 for NTRE-512 and 648 for NTRE-128, and the same encoder runs on the real session message in kem_enc and in every ciphertext kem_dec accepts, so an observer of the branch pattern recovers the message and, through the public derivation of the session key from it, the session key too.
| Parameter set | Claim | Attack cost | Verdict |
|---|
| NTRE reference build, all sets; optimised NTRE-128 | constant-time encapsulation and decapsulation | a secret-dependent branch per message bit; no timing attack run | Holds |
What causes it
Spec CBD prime 1 (Algorithm 4, printed p. 3) is the pure formula f_i = beta_i (1 minus 2 beta_{n+i}); nothing in it requires a branch. Reference poly.c:72 implements it as a conditional (beta0 selects 1 minus 2 beta1 or 0), one test-and-jump per bit; optimized poly.c:57 to 64 unrolls the same test. Decaps (Algorithm 13) re-encrypts the decrypted message before any check.
Evidence
A valgrind-style harness marking only the secret key's f-hat as undefined flagged 4608 (2 times 2304) and 1296 (2 times 648) uses at poly.c:72 on the reference NTRE-512 and NTRE-128 builds, all reached from decapsulation's internal re-encryption, with no other secret-dependent jump found. A behavioural wrapper around the encoder confirmed the branched value matches the spec formula at every position and equals the encapsulated message on accepted ciphertexts, on two keys each. Built with the official optimized flags (O3, AVX2, LTO, gcc 13.3), NTRE-128 still shows 8 branches per call, the last message byte, but NTRE-512 shows none: its message bytes are handled by a vectorized loop, and the scalar fallback that remains in the object code never runs. No timing measurement over a real channel was attempted.
Cause in the submitted code; the specification is not affected.
Limits
Exploitation is argued, not demonstrated; remote timing is untested. Covers the reference implementation at every set, and the optimized implementation only for NTRE-128 (8 branches per call); the optimized NTRE-512 build under the official flags shows none.
Credit
Found by PQC-X.