Security › kem-11 · Constant-time review · Performance: x86_1 · arm_1

COMPASS-KEM (kem-11)

kem-11-1: COMPASS-KEM-384 and -512 use a 256-bit key-generation root

The COMPASS-KEM algorithms define both the initial key-generation seed and the shared key as n-bit values. The submitted COMPASS-KEM-384 and COMPASS-KEM-512 implementations instead fix SYMBYTES and SSBYTES at 32 bytes.

The entire IND-CPA key pair is a deterministic function of one 256-bit coins value. There are therefore at most 2^256 generated public keys: enumerate the root, regenerate the public key, and compare it with the target to recover the corresponding secret key. The KEM output independently has at most 256 bits of delivered-key capacity.

This caps both implementations at 256 bits despite their respective 384- and 512-bit classical claims. The specification is internally inconsistent: Algorithm 1 requests an n-bit seed, while its implementation notes on physical PDF page 25 say that one could store only a “32-byte core seed” and rerun key generation. The submitted code follows the shorter interpretation.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 security/design_parameter_audit.py --report-id kem-11-1

The check verifies the source constants and deterministic expansion against physical PDF pages 9, 12, 16, and 25.

kem-11-2: The Biased-MLWR reduction does not instantiate the concrete small-secret sets

Original source: Make's PKC Forum post

COMPASS-KEM's IND-CPA proof states Theorem 2 on physical p. 20 and uses Biased MLWR for its Game 2-to-Game 3 transition on p. 21. Definition 2 instead defines that problem with a uniform secret, and Theorem 1 relies on a uniformly random bounded component satisfying its leftover-hash-lemma inequality (physical pp. 16–17). Concrete encryption samples r from CBD_eta with eta in {2,3,4} (Algorithm 2, physical p. 14; Table 1, p. 18; indcpa.c:336–337). The submission gives no reduction from these concrete distributions to the stated assumption.

Further extension to Make's analysis: even granting each concrete coefficient the greater entropy of a uniform draw over its full 2 eta + 1 support leaves the displayed inequality short by 6,307, 7,121, 14,629 and 14,357 bits at the 128-, 256-, 384- and 512-bit sets. This quantifies a missing proof bridge, not an attack; the heuristic lattice estimates are separate.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 kem-11/reproduce_biased_mlwr_gap.py

The certificate extracts the theorem's condition, checks each implementation's parameters and CBD call, and evaluates the optimistic entropy bound.