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

CTL (kem-12)

kem-12-1: The specified CTL-512 public-key space has at most 256 bits of support

Follow-up source: CTL submitters' 2026-09-23 response

CTL-512 claims 512-bit security, but its normative short private-key format stores one 32-byte key-generation seed. The specification requires f and g to be regenerated deterministically from this seed and recomputes the public key as h = f^-1 g mod q.

Consequently, at most 2^256 public keys can be generated. An attacker can enumerate the seeds, recompute h, and compare it with the target public key; a match recovers the target trapdoor data. This ceiling is independent of the nominal lattice dimensions and is present in both the specification and submitted code.

Proposed fixes

The CTL submitters' response proposes a 64-byte CTL-512 key-generation seed, an expansion mechanism intended to preserve the target level, corresponding private-key and deterministic-regeneration changes, and a review of the complete entropy path. This section records the proposal without evaluating it.

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-12-1

The kem-12-1 check verifies the short-key algorithms on physical PDF pages 24 and 28–36 and the corresponding reference constants.

kem-12-2: CTL-512 returns only 384 shared-secret bits

Follow-up source: CTL submitters' 2026-09-23 response

The CTL-512 adapter returns a 48-byte shared secret and instantiates the ciphertext hash component c2 at 48 bytes. The specification assigns 64 bytes to CTL-512 c2.

The returned key therefore has at most 384 bits of delivered-key capacity and the ciphertext format contradicts the PDF. The NGCC Submission Requirements §2(2) require the encapsulated key to be at least as long as the corresponding classical security level. CTL-512 misses that explicit 512-bit target and is therefore Critical, even though this dimensional shortfall is not a separate IND-CCA attack. The CTL submitters acknowledge both findings; these reports remain scoped to the archived submission.

Extended on 2026-10-17: the encapsulation randomness is also only 384 bits, so lengthening the output alone would not reach the target. kem_enc draws a 48-byte seed (KEM_AlgorithmInstance.c:68,84), and CTL_MK(3329, 2048, 48, ...) sets LVLBYTES = 48 (ctl.h:249). In encapsulate_explicit_seed, the seed is the message m. The code derives s from m (api.c:677), forms c1 from s and pk, and sets c2 = Hash_m(s) ⊕ m. It then derives the key from m alone (api.c:708). The rare retry path replaces m with H(m) (api.c:691), which is still a function of the seed. Given only (pk, ct), an attacker can enumerate the 2^384 values of m, re-encrypt each one, and match it against ct. This recovers the key without decapsulation queries, below the 512-bit target. The reference and optimized trees have the same lines. This extension was checked by source only. The enumeration was not run.

Proposed fixes

For CTL-512's shared secret and c2, the submitters' response proposes revising the length handling, key derivation, implementation, specification, documentation, test vectors, and validation. This section records the proposal without evaluating it.

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-12-2

The kem-12-2 check verifies the CTL-512 output table and the corresponding reference constants.