Design
cheetahkem-2
Decapsulation failure rate at Cheetah128 and Cheetah256
Security proof gap · Argued · Cause: parameter size
Property: IND-CCA security
Cost against claim: Failure rate 2-77.8 and 2-51.5 against the claimed 2-129 and 2-176; Cheetah256 sees about 228 failures inside the call's 280 queries
The correctness analysis (section 2.2, pp. 16-17) sums the module inner product's noise over N terms rather than the k times N terms a rank-k instance actually has, understating the variance at every level above the first, and treats the public key and ciphertext rounding errors with the wrong second moments. Exact convolution of the real noise distribution gives 2-77.8 (Cheetah128) and 2-51.5 (Cheetah256), against the claimed 2-129 and 2-176, so at Cheetah256 a first failure is expected well inside the call's 280 chosen ciphertext budget and the designers' IND-CCA bound (q_H times delta, Theorem 2) is void beyond 251.5 queries.
| Parameter set | Claim | Attack cost | Verdict |
|---|
| Cheetah128 | failure rate 2-129 (Table 2); IND-CCA at 128 bits | failure rate 2-77.8; about 22 failures inside the 280 query budget | Security proof gap |
| Cheetah256 | failure rate 2-176 (Table 2); IND-CCA at 256 bits | failure rate 2-51.5; about 228 failures inside the 280 query budget; the IND-CCA bound is void beyond 251.5 queries | Security proof gap |
What causes it
Section 2.2 derives delta from b times r minus s times a times r, modelling the du and dv compression errors as centred binomial rather than uniform, and treating the rank-k inner product's coefficient as a sum of N products instead of k times N; for k=1 the two counts coincide, which is why Cheetah128's gap is small. Algorithms 15-17 give the exact noise term W = (e+e_b)^T r + e_2 minus (e_1+e_u)^T s + e_v, whose coefficient really is a sum of k times N independent products.
Evidence
Delta recomputed by direct float64 convolution of the exact per coordinate distribution (no FFT floor, e_v convolved rather than bounded worst case). Validated by a spec level simulation of KeyGen, Encrypt and Decrypt: measured Var(W) matches the k times N model within 1.3 percent at every level and refutes the N-only model for k at least 2 (predicted variance 41047 against a measured 59553 at Cheetah256). Tail shape checked against the exact distribution at 2.5, 3, 3.5 and 4 standard deviations, agreeing at every level. A second PQC-X member reran the original report's failure scripts, found them using N rather than k times N terms at every level, and independently reproduced the exact rates.
Cause in the specification: the attack also works on a model built from the specification alone.
Limits
No decryption failure was actually observed, and no failure boosting key recovery (D'Anvers et al.) was costed. Cheetah384 and Cheetah512 are also below their claims (2-115.1 and 2-198.9 against 2-189 and 2-243) but stay far outside the 280 query budget, so the argument still stands at those two levels.
Credit
Found by PQC-X.
cheetahkem-1
Key recovery via the reducible ring X640+1
Holds · Argued · Cause: construction
Property: key recovery
Cost against claim: the ring cuts key recovery by 24 to 62 bits; 137.2 against the designers' 157 at Cheetah128, every level still met
CheetahKEM's ring X640+1 factors as Phi_256 times Phi_1280 (degree 128 and degree 512, since 1280 divides q minus 1). A spec conformant public key reduces modulo the degree 512 factor Phi_1280 to a smaller MLWE instance carrying the same secret and error distribution as the full ring, so the real key recovery cost is that of the factor, not of the full dimensional lattice the design's own hardness estimate assumes.
| Parameter set | Claim | Attack cost | Verdict |
|---|
| Cheetah128 | 128 classical (designers' estimate 157) | degree-512 factor: core-SVP 137.2 | Holds |
| Cheetah256 | 256 classical (designers' estimate 302) | degree-512 factor: core-SVP 300.2 | Holds |
| Cheetah384, Cheetah512 | 384 and 512 classical | degree-512 factor: core-SVP 437.1 and 580.5 | Holds |
What causes it
Spec section 2.1/2.4 (p. 7, p. 18) fixes R_q = Z_q[X]/(X640+1), N = 640 = 5 times 27, with 1280 dividing q minus 1, so X640+1 splits as Phi_256 times Phi_1280. Section 5.3 (p. 23, p. 24) states its own hardness estimate explicitly ignores the algebraic structure of the ring.
Evidence
Mechanism re derived independently in exact Sage: the factorisation, the CRT obstruction over Z[x] (resultant 5128, so integer recombination fails while it succeeds over Q[x]), and the secret and error distribution modulo each factor, checked against a freshly generated spec conformant key at k=1 and k=2 (measured variances within sampling noise of the model). Cost recomputed with the campaign's estimator (rough core-SVP and MATZOV, beta and eta caps lifted): factor 137.2/300.2/437.1/580.5 against the corrected full ring cost with the public key compression error included, 160.9/334.3/487.3/642.1. A second PQC-X member reran the original report's ring and CRT check scripts against its own KAT dump and reproduced the same logs.
Cause in the specification: the attack also works on a model built from the specification alone.
Limits
No key was recovered by an actual lattice reduction run, only the reduced instance's cost estimated. Every set stays above its classical and quantum requirement (137.2 against 128 classically, with 9 bits of margin at the first level). Not explored: attacking the full instance restricted to the coset fixed by the other, costlier factor, which would keep the noise undoubled.
Credit
First public report: XuHaomeng (ngcc.dev kem-09-2, 2026-09-22). Found independently by PQC-X.
Implementation
Bugs in the submitted code; the specification is sound on these points.
cheetahkem-i1
Broken implicit rejection mask leaks the shared secret
Minor break · Demonstrated · Cause: code
Property: IND-CCA security
Cost against claim: A decapsulation query returns 7 of 8 bits of the real shared secret for any submitted ciphertext, in all 12 implementations
Every KEM_Cheetah.c tree ORs the ciphertext byte differences into fail, then negates it with (unsigned char)(-fail); for a mismatching ciphertext this produces 0x01, not 0xFF, so the masked XOR update ss[i] ^= fail & (kbar[i]^ss[i]) only ever replaces bit 0 of each output byte. Bits 1 through 7 of every byte stay equal to the real derived key, turning decapsulation into a plaintext checking oracle instead of returning an independent pseudorandom value.
| Parameter set | Claim | Attack cost | Verdict |
|---|
| Cheetah128, Cheetah256, Cheetah384, Cheetah512 (all 12 implementations) | IND-CCA2, 128 to 512 classical | one decapsulation query per chosen ciphertext | Minor break |
What causes it
Algorithm 20 line 4 (cheetah_kem_en.pdf) requires K-bar = H(salt || c) computed on the received ciphertext, with a full replacement of K on mismatch. The code instead hashes K-bar over salt and the re-encryption c-prime rather than the received c, and its (unsigned char)(-fail) mask flips only bit 0. Both deviations are in KEM_Cheetah.c (all three parameter files, all 12 implementation trees), Cheetah128 reference lines 285-295; the specification's own algorithm is correct on this point.
Evidence
Behavioural test on an unmodified copy of the Cheetah128 reference implementation (KAT reproduced byte for byte): flipping bit j (1 through 5) of a ciphertext byte returns a key whose low j bits equal the honest key in all 16 bytes; across 200 out of 200 random ciphertexts, bits 1 through 7 of every output byte equal K-prime = G(Dec(sk, c-star) || h) truncated to 16 bytes. The main session independently reread KEM_Cheetah.c across all 12 trees and confirmed both deviations from Algorithm 20 by code inspection.
Cause in the submitted code; the specification is not affected.
Limits
No end-to-end exploit chaining the leak into full key recovery was written; honestly generated KATs are unaffected since they never trigger the mismatch branch.
Credit
First public report: M.-J. Saarinen (ngcc.dev kem-09-1, 2026-09-21). Found independently by PQC-X.