CS

CS-512 sits at its level: primal 7 bits above, contested dual-hybrid 10 to 25 bits below

Holds · Argued · Cause: parameter size

Property: key recovery

Cost against claim: MLWE key recovery: primal 2^518.9 core-SVP and 2^530.4 MATZOV against 2⁵¹²; dual-hybrid estimate 2^486.8 core-SVP and 2^501.7 MATZOV

Key recovery on CS-512 is a Module-LWE instance of secret dimension 2560 with 3072 samples, ternary secret and error (Table 3, Definition 4.1). The primal attack reproduces the designers' figure exactly (block size 1777, 2^518.9 in their core-SVP metric; 2^530.4 in the MATZOV model, 2^526.2 for its BDD variant) and holds in every cost model. The estimator's dual-hybrid attack lands below the level, at 2^486.8 core-SVP (block size 1667) and 2^501.7 MATZOV (block size 1671); the designers evaluated only the plain dual attack (block size 1766, 2^515.7), which explains the gap. That attack rests on dual-sieve heuristics whose validity is contested, so PQC-X does not count it as a break; but the margin of CS-512 is a few bits at best, where the call asks for security redundancy.

Evidence

Costs from the lattice estimator in rough core-SVP (0.292β classical, 0.265β quantum) and in the MATZOV model, with the estimator's block-size cap lifted (the cap at 1754 first hid the primal figure and distorted the BDD one). A second member of PQC-X re-ran the same batch, obtained the same figures, and re-derived the primal and the plain dual costs without estimator code, from the 2016 primal condition under the geometric series assumption and the classical dual: block sizes 1777 (2^518.9) and 1768 (2^516.3), against the designers' 1777 (518.88) and 1766 (515.67). The dual-hybrid figure is checked by the estimator re-run only.

Cause in the specification, traced to the specification text.

Limits

Every block size here (1667 to 1849) lies far beyond any lattice reduction ever run, so all figures are extrapolations of the cost models. CS-128 and CS-256 hold in both models, within the precision of any cost model. The forgery side (MSIS in the infinity norm) is comfortable at every level (CS-512: 2^549.8 core-SVP, 2^561.7 MATZOV).

Credit

Found by PQC-X.

The dual-hybrid costs follow the lattice estimator's implementation of the MATZOV report (2022); Ducas and Pulles (CRYPTO 2023) question the dual-sieve heuristics it relies on.

The one-bit approximation-loss bound is proven for 2⁶⁴ signatures, not the call's 2⁸⁰

Holds · Argued · Cause: parameter size

Property: existential unforgeability (tightness of the security argument)

Cost against claim: provable loss at 2⁸⁰ signatures: at most 0.2 bits at CS-128, about 1.4 bits at CS-256, about 4.5 bits at CS-512, against the stated 1 bit

Signing accepts or rejects a candidate with integer arithmetic only, at a relative error of at most 2^{−L+4+log d} per rejection step with L = 64 (Lemma B.2), and Appendix B bounds the resulting loss of concrete security by one bit through a Rényi-divergence argument, but for 2⁶⁴ signing queries only (Lemma B.3, using Prest's criterion). The call lets an attacker obtain 2⁸⁰ signatures. With each set's own number of rejection blocks N and dimension d, the criterion still holds at CS-128 at 2⁸⁰ (loss at most 0.2 bits) but not at CS-256 (about 1.4 bits) nor at CS-512 (about 4.5 bits at the best Rényi order, 10.6 bits at the order a = 2λ of Prest's statement). It is a gap of a few bits in the stated bound, not an attack: observing a relative bias of 2⁻⁴³ would take about 2⁸⁶ signatures.

Evidence

Exact computation from the specification's bounds (Lemmas B.2 and B.3: |ΔA| ≤ N·2^{−L+4+log d}) with N = 6, 15, 20 and d = 1792, 3584, 6144 for CS-128, CS-256, CS-512, then Prest's relative-error lemma and probability preservation, optimised over the Rényi order. At 2⁶⁴ queries all three sets lose at most 0.5 bits, so Lemma B.3 is right as stated. A second member of PQC-X computed the loss at 2⁸⁰ set by set, which is what excludes CS-128.

Cause in the specification, traced to the specification text.

Limits

CS-128 is unaffected. Normalising the accepted output over restarts can at most double the per-attempt relative error, which would bring CS-256 to about 2.8 bits and CS-512 to about 9 bits. No attack exploits the loss; the designers' bound needs restating at the call's query budget, or a few more bits of precision L.

Credit

Found by PQC-X.

Verification never reads the zero padding of the rANS-coded fields: one signature has about 2²²⁴ to 2⁶⁸⁰ accepted encodings

Minor break · Demonstrated · Cause: code

Property: strong unforgeability

Cost against claim: a second accepted signature for one byte change, against claimed sUF-CMA at 128, 256 and 512 bits

Scope: The reference and the optimized implementations, all three parameter sets. The specification fixes no byte format, so a verifier written from it is affected only if it repeats the same container.

The submitted code packs each rANS-coded field of a signature (z0 or its high part, the high part of z1, and the hint) into a block of fixed size as a two-byte length, the used bytes, then zero padding. Verification decodes exactly the used bytes and never looks at the padding, and nothing else in verification covers the raw bytes, so any change to a padding byte gives a different signature that is still accepted on the same message. From one valid signature, an attacker without the key obtains 2^8·pad accepted encodings, with pad between 28 and 85 bytes depending on the set and the signature, which contradicts the strong unforgeability the designers prove (Theorem 4.1).

What causes it

The specification defines the signature as the tuple σ = (σ0, σ1, h, c̃), where σ0 and σ1 are the rANS encodings of z0 and z1 (Algorithm 11, lines 19 to 21), and verification decodes them (Algorithm 12, lines 5 and 6) with the rANS decoder of Algorithm 3. It fixes no byte container, no block size and no padding (Table 1 gives sizes only), and the strong unforgeability proof (Theorem 4.1, through the unique-response argument of Lemma 4.3) reasons about the tuple, not about its bytes. The container is the implementation's: sigEncode in encodings.c zeroes each block and writes the length, the used bytes and zero padding for the three rANS-coded fields (the code also rANS-codes the hint, which the specification does not ask); sigDecode and decode_rans stop at the written length and check nothing beyond it; CS_Verify in cs.c recomputes nothing over the raw signature bytes. The same encodings.c ships in the reference and the optimized implementations.

Evidence

Reference implementation, all three parameter sets, CS-128, CS-256 and CS-512. First seen at CS-128 by flipping every byte of a signature in turn: only the padding bytes (47 in that signature) leave it accepted; changing the last byte of an official KAT signature also leaves it accepted. A second member of PQC-X rebuilt the unmodified reference sources (the three official KAT files regenerate byte for byte), re-ran that test with the same result, and wrote an independent one: on each of the 30 official KAT signatures (10 per set), derive the padding from the three length prefixes, flip every byte of the signature one at a time, randomise all padding bytes at once, then try the padded signature on a changed message. Result on all 30: the honest padding is all zero; every padding flip is accepted (35 to 47 bytes at CS-128, 44 to 70 at CS-256, 45 to 69 at CS-512); no flip outside the padding is accepted (1501 to 5930 other offsets per signature, the challenge hash c̃ and the length fields included); the fully randomised padding is accepted; the same padded signature on a changed message is rejected. On 200 fresh signatures per set under a new key, the padding totals 28 to 54 bytes (CS-128), 36 to 79 (CS-256) and 32 to 85 (CS-512), and all 600 are still accepted with their padding randomised.

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

Limits

Only the strong unforgeability the designers claim falls. The call accepts EUF-CMA as well, and EUF-CMA is intact: a padded signature is rejected on any other message, and the padding carries no information about the key. The fix is local: reject any non-zero padding, or re-encode the decoded values and compare them with the received bytes.

Credit

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