FLIT

The decryption-failure rates claimed for Flit128 and Flit256 are 8 to 16 bits optimistic once the coefficients of one bit share the key

Holds · Argued · Cause: construction

Property: the decryption-failure rate entering the IND-CCA bound; no claimed property falls

Cost against claim: δ about 2^-174 (Flit128) and 2^-167 (Flit256) averaged over keys, against 2^-187.5 and 2^-176.1; no failure within 2⁸⁰ queries

The specification computes δ under an independence assumption on the coefficients of the error term (section 1.4), but the k = 2 or 4 coefficients that decode one message bit all multiply the same secret key, and the weight of f, a per-key quantity, drives their joint tail: a 2^-14 to 2^-28 fraction of keys, whose f is 4 to 6 standard deviations heavier than the mean, carries the average. Averaged over keys, δ is about 2^-174 for Flit128 and 2^-167 for Flit256, 8 to 16 bits above the claimed 2^-187.5 and 2^-176.1 depending on the model, while Flit512, whose ternary keys are dense, is as claimed. Failures stay far out of reach: the best chosen-ciphertext selection PQC-X could argue still needs at least about 2¹²⁵ decapsulation queries per expected failure, against the call's 2⁸⁰, so no attack follows and the claimed levels stand.

What causes it

Theorem 1 (section 1.4) gives the error term u = g·r + f·(e + e′) + ⌊f·M/2⌋ and the condition under which a bit fails, a sum over the k = N/n coefficients at positions i + jn; the paragraph that follows computes δ by treating the coefficients of u as independent and applying a union bound over the n positions, and Table 2 (section 1.5) and the design rationale (section 2) state the resulting 2^-187.5, 2^-176.1 and 2^-195.5. The k coefficients of one bit are k products with the same f and g, so their joint law depends on the key: on the weights of f and g first, and on their autocorrelations at multiples of n.

Evidence

PQC-X observed by Monte Carlo (2.56·10⁷ decoding groups per set) that at measurable thresholds the group tail exceeds the independence prediction, increasingly with the threshold; it then computed per-key rates at the real threshold with a saddle-point method validated against a Monte Carlo on the same keys (ratios 0.94 to 1.21) and integrated them against the exact law of the weight of f: about 2^-178 (Flit128), 2^-165 (Flit256) and 2^-196 (Flit512). A second member of PQC-X re-ran the combination and ciphertext-selection scripts (identical logs) and built an independent model from exact discrete laws: under the designers' independence assumption it gives 2^-185.4, 2^-175.6 and 2^-195.5, near the claims; letting the k coefficients of a group share the key's weights, it gives 2^-174.2 (Flit128, 11.1 bits above its independence figure), 2^-167.5 (Flit256, 8.1 bits) and 2^-195.0 (Flit512, 0.5 bit), with per-key rates within about 6 bits of the first model's at every weight stratum; it did not re-run the per-key saddle-point computations.

Cause in the specification, traced to the specification text.

Limits

Both models keep the dependence through the key's weights; neither captures the full autocorrelation of f and g at multiples of n, and the two differ by up to about 4 bits, hence the ranges. The claimed rates are unobservable, so the corrected ones are computed, not measured. The lower bound of about 2¹²⁵ queries per failure for Flit256 is argued from Gaussian scaling at the largest precomputation the level allows; for Flit128 one failure costs at least about 2¹⁷¹ decapsulations, above the level itself, before any selection. The designers' all-ones worst-case figures (2^-177.8 and 2^-164.5) were not re-derived by the second member: in the first model an all-ones message changes δ by only 1 to 4 bits.

Credit

Found by PQC-X.

Flit128 is 10 to 12 bits below 128 in core-SVP and above 128 only in the designers' gate-count model

Holds · Argued · Cause: parameter size

Property: IND-CCA security; the claim, stated in the MATZOV model, holds

Cost against claim: core-SVP 2^115.6 (key) and 2^117.3 (ciphertext) against 128; MATZOV 2^139.4 and 2^139.6

In the core-SVP count the best attacks on Flit128 cost 2^115.6 on the key (an NTRU instance, hybrid BDD at block size 390) and 2^117.3 on a ciphertext (an RLWE instance carrying the compression noise, dual hybrid at block size 398), both below the 128-bit level; in the MATZOV gate count the designers use for their claim they cost 2^139.4 and 2^139.6, and 2^134.0 on the designers' ciphertext instance without the compression noise, so the claim as stated holds. This is the situation of Kyber-512 under the same tool (core-SVP 2^118.6, MATZOV 2^139.7), and the designers' own Table 4 already reports core-SVP figures below 128 (118.6 and 118.8): the hybrid variants lower them by about 3 bits.

What causes it

Table 2 (section 1.5) fixes N = 512, q = 769, f and r ternary with Pr[±1] = 1/8 each, g and e with 5/16; Table 3 (section 3.2.3) states the claim as the minimum over attacks in the MATZOV model of the lattice estimator (commit 6019056), 134.0 for RLWE and 139.4 for NTRU; Table 4 gives the core-SVP primal figures 118.8 and 118.6. The call fixes no cost model.

Evidence

PQC-X ran the lattice estimator (commit 6019056) on instances written from Table 2, with the exact law of the compression error added to the ciphertext instance (variance 0.671 at q = 769, d = 8): on Flit128 it reproduces the designers' figures of Tables 3 to 5 to the decimal and gives 115.6 (key) and 117.3 (ciphertext) in core-SVP against 139.4 and 139.6 in MATZOV. A second member of PQC-X wrote its own instance definitions from the specification, including the compression law, and reproduced all four Flit128 figures exactly; a Gaussian stand-in for the fixed-weight secret model gives the same 115.6, so the figure is not an artefact of the secret model; quantum core-SVP stays at or above 2^103.4 against the call's 80.

Cause in the specification, traced to the specification text.

Credit

Found by PQC-X.

The FIPS202 additional implementations never seed their random generator: every key pair and every shared secret is a fixed public value

Minor break · Demonstrated · Cause: code

Property: key recovery

Cost against claim: the secret key and the shared secret are recomputed by running the public code, against 2¹²⁸ and 2²⁵⁶

Scope: Users of the four FIPS202 additional implementations (FLIT_FIPS202_REF128, REF256, OPT128 and OPT256), which the specification offers as a speed reference in section 4.2.3.

In the four FIPS202 additional implementations, the function that supplies randomness returns SHAKE256 of a fixed all-zero seed and a call counter, and the routine that would seed it is never called: the harness generator that the ICCS interface prescribes is seeded but never read. The key-generation seed, the implicit-rejection secret z and the KEM message m are the first, second and third outputs of every process, so the i-th key pair and the i-th encapsulation of any process are fixed values that anyone recomputes by running the code.

What causes it

The specification is sound on this point: Algorithm 11 draws ρ and Algorithm 12 draws m at random, and the main implementations draw them from the seeded harness generator. In the four FIPS202 directories, rng.c holds a static all-zero 32-byte seed and returns SHAKE256(seed ‖ counter) at each call; its seeding routine is defined but has no call site anywhere in the submission; the key seed (indcpa.c), z and m (kem.c) come from this generator, while the harness generator that KAT_KEM.c seeds is never read.

Evidence

PQC-X ran the FIPS202 REF128 build with two different 64-byte harness seeds in two processes: the same public key, secret key, ciphertext and shared secret; the unmodified KAT program produces the same file at every run. A second member of PQC-X rebuilt the FIPS202 REF128 and OPT256 directories unmodified from a fresh copy of the submission, changed only the harness nonce so that all ten KAT seeds differ, and found the public keys, secret keys, ciphertexts and shared secrets identical in 10 of 10 records for both builds, while the main SM3 REF128 and REF512 builds, run the same way as controls, change every value; in all 10 records of both FIPS202 builds the stored implicit-rejection secret equals SHAKE256 of thirty-two zero bytes and the counter 3i+1, and rng.c and KAT_KEM.c are byte-identical across the four FIPS202 directories.

Cause in the submitted code; the specification is not affected.

Limits

Only the four FIPS202 additional implementations are affected; the reference and AVX2 implementations built on the call's SM3 primitives, which produce the official test vectors, read the seeded harness generator. No FIPS202 test vectors were submitted, so nothing in the package exposes the defect.

Credit

Found by PQC-X.

The AVX2 Flit512 code does not reduce compressed coefficients modulo 2⁹: about half of its ciphertexts are not the specified ones

Holds · Demonstrated · Cause: code

Property: conformance; no security consequence

Cost against claim: the reference decapsulation returns the implicit-rejection key on 8 of the 10 official Flit512 AVX2 test vectors

Compress_q(x, 9) is the rounding of 2⁹·x/q reduced modulo 2⁹ (section 1.1). The AVX2 Flit512 packing routine computes the rounding but omits the reduction, so the three values x ∈ {3326, 3327, 3328} give 512, whose tenth bit is OR-ed into the lowest bit of the next 9-bit field (and dropped for the eighth field of each group of eight). With about 0.81 affected coefficients per ciphertext, about 55% of the ciphertexts of the AVX2 code differ from the specified ones; the deviation depends on the public ciphertext only and the AVX2 code is self-consistent, so nothing leaks, but the reference and AVX2 implementations do not interoperate.

What causes it

Reference_Implementation/FLIT512/poly.c masks each compressed value with 0x1FF; Optimized_Implementation/FLIT512/poly.c, in the d = 9 branch of its compress-and-pack routine, does not. The d = 8 path used by Flit128 and Flit256 keeps only the low byte, so it reduces modulo 2⁸ by construction. The submission's README states that the reference and optimized implementations produce identical output from the same seed; for Flit512 they do not.

Evidence

PQC-X compared the official Flit512 REF and OPT test-vector files: ciphertext and shared secret differ in 8 of 10 records, in 13 coefficients that all fit the pattern (the preceding reference coefficient is 0, the position is not the eighth of its group, and the OPT value is the REF value with its lowest bit set), and the unmodified reference decapsulation returns the implicit-rejection key KDF(z ‖ H(c)) on those 8 records. A second member of PQC-X re-derived the pattern from a fresh copy of the code, re-ran both tests with its own unpacker and its own decapsulation driver (10 of 10 REF records accepted; 8 of 10 OPT records rejected, the other 2 accepted), and computed the expected rate: 0.81 corrupted coefficients per ciphertext, a non-conformant ciphertext with probability about 0.55.

Cause in the submitted code; the specification is not affected.

Limits

The Flit128 REF and OPT files are identical; the Flit256 files differ only in one secret key, where a zero NTT coefficient of f is stored as q, which the reference decapsulation handles.

Credit

Found by PQC-X.