COMPASS-KEM

A 256-bit seed, message and shared key at every level cap COMPASS-KEM-384 and -512 at 256 bits

Minor break · Tested at small scale · Cause: parameter size

Property: key recovery

Cost against claim: seed or message search 2²⁵⁶ classical, 2¹²⁸ quantum, against 2³⁸⁴ / 2¹⁹² and 2⁵¹² / 2²⁵⁶

Scope: The submitted reference and optimised code and the official test vectors, which follow the 32-byte reading of the specification (Table 2, §5.1.1). An implementation written from the algorithm text alone, with 64-byte strings, is not capped, but does not interoperate with them.

The whole key pair is derived from one 256-bit seed, every ciphertext from a 256-bit message, and the shared key is 256 bits, at all four levels. Enumerating the seed and re-running key generation until the public key matches recovers the decapsulation key; enumerating the message and re-encrypting until the ciphertext matches recovers the message, hence the shared key of that ciphertext. Either search costs 2²⁵⁶ classically and 2¹²⁸ Grover iterations, below the 384 and 512 classical bits and the 192 and 256 quantum bits claimed; a 256-bit shared key is also shorter than the call requires at those two levels.

What causes it

The algorithm text sizes these strings in n bits (§2.3.1; Algorithms 1, 2, 4, 5 and 6), and Table 1 sets n = 512 at levels 3 and 4, which would conform. The rest of the submission fixes them at 32 bytes: Table 2's key and ciphertext sizes are only reproduced with 32-byte seeds, hashes and rejection values at every level, and with a secret key that holds no key-generation seed; §5.1.1 speaks of a 32-byte core seed; the reference and optimised code set the seed, message and shared-key lengths to 32 bytes at every level, zero the coefficients 256 to 511 of the message polynomial when n = 512, and keep no seed in the secret key (which §3.4 needs for its kleptography check); the official test vectors carry a 32-byte shared key. The specification therefore contradicts itself, and the submitted code and test vectors embody the 256-bit reading. The fix is to make the n-bit reading normative and to regenerate the code and the test vectors.

Evidence

On the unmodified reference build, at all four levels, PQC-X ran both searches with all but 14 bits of the target given: the message search recovered the message and the shared key in 7876 trials, and the seed search rebuilt the public key and the secret vector in 1138 trials (counts re-run at levels 384 and 512). A second member of PQC-X rebuilt the code from sources identical to the submission, reproduced the official test vectors of levels 384 and 512 byte for byte with a 32-byte shared key, and re-ran both searches through the public API alone with 12 bits unknown: message and shared key in 1502 trials and seed in 1680 trials at every level, the rebuilt secret key decapsulating an honest ciphertext; one trial takes 1 to 4 ms. The full 2²⁵⁶ count follows from the string lengths, not from a run.

Cause in the specification, traced to the specification text.

Limits

The full search is extrapolated: no key was recovered from a 256-bit unknown. COMPASS-KEM-128 is unaffected, and COMPASS-KEM-256 meets its level with no margin. Counted in gates, the Grover search costs about 2¹⁵⁰, and about 2²²⁶ under the 2⁶⁴ depth limit the designers assume, which stays below the 2²⁵⁶ required at level 512 but not below the 2¹⁹² of level 384; the classical shortfall holds in every model.

Credit

First public report: M.-J. Saarinen (ngcc.dev kem-11-1, 2026-09-21). Found independently by PQC-X.

The failure-rate analysis drops the mean of the rounding error: failures are 2³³ to 2⁷⁶ times likelier than Table 3 states, and reachable below the claim at levels 256 and 512

Security proof gap · Argued · Cause: specification text

Property: IND-CCA security, the failure-rate argument

Cost against claim: failure rate 2^-148 against the stated 2^-181 at level 256; first failure at about 2²²⁷ against 2²⁵⁶; no key recovery costed

The compression of §2.3 (a decrement, then a floor) leaves a rounding error of mean −1/2, not zero, and §3.3 models the noise term it multiplies with the error's variance (1.25) where its second moment (1.5) is needed. Computed exactly, the failure rate is 2^-152.1, 2^-148.2, 2^-328.1 and 2^-205.0 at the four levels, against the 2^-189.3, 2^-181.1, 2^-404.5 and 2^-250.3 of Table 3. The designers dismiss failures because decapsulation calls are capped at 2⁸⁰; but an attacker who selects ciphertexts using the known mean shift obtains a first failure within that cap for about 2²²⁷ to 2²³⁵ encryptions at level 256 and 2⁴⁵² to 2⁴⁶¹ at level 512, below the 2²⁵⁶ and 2⁵¹² claimed, so the argument no longer covers those two levels. Key recovery from failures has not been costed: no attack is known.

What causes it

§3.3 models every product of a rounding error by a secret coefficient as a centred Gaussian with the rounding error's variance; the compression of §2.3 makes the public-key rounding error have mean −1/2, so each such product has second moment 1.5 times the variance of the encryption randomness, not 1.25, and the noise inherits a shift of half the signed sum of the randomness, which the sender knows. §3.3 then dismisses failures on the ground that decapsulation calls are capped at 2⁸⁰ (p. 16).

Evidence

PQC-X reproduced Table 3 to within 0.4 bits with the designers' Gaussian model and the variance, then recomputed the rate by exact convolution with the second moment; the same machinery reproduces the published failure rate of Kyber-512 (2^-139.1 against 2^-139). A second member of PQC-X re-derived the rounding error's mean and moments by direct convolution (mean −0.499, second moment 1.501 at q = 3329), checked the shift on the scheme's own arithmetic (regressing the noise on the signed sum of the randomness gives a slope of −0.508 for −0.499 predicted), re-ran the failure-boosting model and rebuilt one independently with Chernoff joint tails: first-failure work of 2^209.9, 2^226.7, 2^978.6 and 2^451.8 with a 2⁸⁰-query budget, within 3 bits of the first model.

Cause in the specification, traced to the specification text.

Limits

Only the first failure is costed, in candidate encryptions; counted in bit operations the level-256 gap shrinks to a few bits while the level-512 gap stays above 30 bits. Levels 128 and 384 are not concerned: the first failure costs about 2²¹⁰ and 2⁹⁷⁹ there, above the claim, and with a 2⁶⁴-query budget every level is above its target. On a quantum computer the search for weak ciphertexts stays above the quantum targets (about 2¹⁵³ against 2¹²⁸ at level 256, about 2²⁶⁶ against 2²⁵⁶ at level 512). Without the mean shift, no ciphertext selection reaches a failure probability of 2^-80 per query.

Credit

Found by PQC-X.

COMPASS-KEM-384 sits at or below 384 bits in the dual and MATZOV cost models

Holds · Argued · Cause: parameter size

Property: IND-CCA security

Cost against claim: level 384: 2^378.8 (MATZOV), 2^362.1 (core-SVP), 2^383.06 in the designers' own dual estimate, against 2³⁸⁴

In the MATZOV model the best attack on COMPASS-KEM-384 costs 2^378.8 (dual hybrid, block size 1237), 5 bits under the level, and the designers' own dual estimate (Table 6) gives 383.06 bits, which they lift above 384 by crediting the attack's 31 % success rate; only their two-step primal estimate (409.9 bits) leaves a margin. In core-SVP the set is at 2^362.1 classical, but that model also places the three other sets under their levels (2^113.3, 2^244.1, 2^507.2), which the MATZOV model places above (2^137.9, 2^265.1, 2^520.0). Whether COMPASS-KEM-384 meets its level is thus a matter of cost model; level 384 is optional in the call.

Evidence

Estimates from the lattice estimator with the module-LWR instance written as LWE (a centred-binomial secret, a rounding error), calibrated on Kyber-512. A second member of PQC-X re-ran the estimator with no cap on the block size (uSVP block size 1312, dual hybrid 1240; MATZOV 2^378.8 for the dual hybrid, 2^393.9 for BDD, 2^398.6 for uSVP) and recomputed the primal block size independently under the GSA (1314, hence 383.7 bits in core-SVP).

Cause in the specification, traced to the specification text.

Credit

Found by PQC-X.