Security › sign-07 · Constant-time review · Performance: x86_1 · arm_1

CS (sign-07)

sign-07-1: Trivial signature malleability violates SUF-CMA

The signature contains a fixed-size rANS encoding area and an encoded byte count. sigDecode consumes only the indicated meaningful bytes and does not require the unused tail to be zero or otherwise canonical.

Changing the last unused signature byte produces a distinct signature that continues to verify for the same public key and message. This transformation needs neither the secret key nor a signing query beyond the original valid signature.

The result is not a new-message forgery and therefore does not alone violate EUF-CMA. It directly violates the submitted strong-unforgeability claim, which forbids producing a second accepted signature for an already signed message.

Verification must enforce a unique encoding, including the complete fixed-size tail.

Reproducing

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

Build the candidate and the reproducer, then run:

make -C api harness && make -C tools && make -C sign-07
tools/ngcc_attack sig-malleable sign-07/lib/libCS-128.so

tools/reproduce.sh runs this together with the other supported runtime witnesses and their controls. See tools/README.md.

sign-07-2: Verifier challenge-sign blindness enables universal forgery

Original source: ngcc-harness PR #1

CS samples a weight-tau challenge over {0,+1,-1} and credits all tau sign bits in its challenge-entropy calculation. In both specification Algorithm 12 and CS_Verify, however, the challenge reaches verification only through parity: the -q*c term is identical for +1 and -1 modulo 2q, and the other hash input retains only LSB(z0-c). Verification therefore sees the challenge support but not its signs.

The verifier also imposes no independent weight or norm bound on the hint. For any chosen support, an attacker can set z0=z1=0 and choose an encodable hint so that every norm and reconstruction check passes. Grinding the free hint until the hash selects that support costs binomial(n,tau), rather than the binomial(n,tau)*2^tau challenge space used in Table 3. Independently recomputed costs are 108.08, 212.46, and 394.18 bits, below every claimed classical level; generic quantum search halves those exponents.

The complete submitted-size grinds were not executed. The reproducer proves the free-transcript construction at every submitted parameter set and runs the same attack to completion on a scaled CS-128 instance with tau reduced from 23 to 3. Compensating B0, B1, B2, and M0 adjustments preserve the z0 and z1 bounds and tighten the z2' bound from 2812 to 2521. The submitted verifier compiled with those scaled parameters accepted the forged signature without a signing query or secret key. Binding the challenge signs into a verifier-visible equation and bounding the hint are both necessary repairs.

Reproducing

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

make -C sign-07 libs exploit
sign-07/forgery_CS-128-scaled-tau3 \
  sign-07/lib/libCS-128-scaled-tau3.so --threads 4 --verbose
sign-07/forgery_CS-128 sign-07/lib/libCS-128.so \
  --control --threads 4 --trials 200000 --verbose
sign-07/forgery_CS-256 sign-07/lib/libCS-256.so \
  --control --threads 4 --trials 200000 --verbose
sign-07/forgery_CS-512 sign-07/lib/libCS-512.so \
  --control --threads 4 --trials 200000 --verbose

sign-07-3: Compressed signatures enable practical equivalent-key recovery and forgery

Original source: NGCC PKC Forum post Follow-up source: Feussner's PKC Forum post and reproducer

In the full compressed scheme, §3.4 (Correctness) derives the verifier-visible relation z2' = z2 - c_r·b_0 + (-LowBits_h(w,α)+LSB(w))/2 (mod ±q), where b_0 is the secret low part of the public-key relation and c_r aggregates hidden bimodal signing signs. Liu reports estimating E[c_r | z0,c] from public signature fields, then using its correlation with z2' to recover all coefficients of b_0; a second cross moment reportedly recovers s1, from which the remaining short key follows. The cited experiment used 2^27 CS-128 signatures and reported exact 768-coefficient recovery after normalization.

Feussner's follow-up turns this into an end-to-end attack on one deterministic, ordinary CS-128 key. One million calibration signatures produce a rough public low-term estimate. For 1.3 million further signatures, posterior scoring tests all 64 hidden block-sign choices and regression produces a nearly correct ternary s1; a fixed public ladder completes an equivalent signing key. The submitted verifier accepts its signature on a fresh message. The immediately preceding 1.2-million refinement checkpoint fails.

The frozen sufficient statistics replay against source that is byte-identical to the archive after line-ending normalization. Replacing every secret-dependent diagnostic truth array with unrelated values leaves the first public success, completed key, and forgery unchanged, establishing that the recovery consumes only the public key and ordinary signature fields. We independently rebuilt and replayed that evidence. The experiment covers one preselected key and does not estimate success probability across keys or extend the result to CS-256/512. A practical fresh-message forgery nevertheless violates CS-128's EUF-CMA claim and is Critical.

Reproducing

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

Download the reproducer pinned at commit c66f8b06b9033d0be076db7a8bdaebb2158ad493 (archive SHA-256 0fe62b6b330b3ece432013ca14a1ee35f3e2315ff36d6ac776e1a9134ad67b39) and run its frozen evidence replay:

T=$(mktemp -d)
curl -fL -o "$T/cs.tar.gz" \
  'https://github.com/martinfeussner/NGCC-Signature-Audit/archive/c66f8b06b9033d0be076db7a8bdaebb2158ad493.tar.gz'
printf '%s  %s\n' \
  '0fe62b6b330b3ece432013ca14a1ee35f3e2315ff36d6ac776e1a9134ad67b39' \
  "$T/cs.tar.gz" | sha256sum -c -
tar -xzf "$T/cs.tar.gz" -C "$T"
cd "$T"/NGCC-Signature-Audit-*/CS/reproducer
CFLAGS='-O3 -flto -fcommon -std=gnu11 -Wno-error=implicit-int' \
  ./verify_evidence.sh

The extra warning flag lets current GCC accept two pre-existing implicit-int declarations in the archived source. The replay verifies all evidence and submitted-source hashes, recomputes the posterior/refinement ladder, requires rejection through 1.2 million refinement signatures and an accepted fresh-message forgery at 1.3 million, then repeats with poisoned diagnostic truth. run_full.sh performs the approximately 2.3-million-signature collection instead.

sign-07-4: A missing nonce collapses every secret and error polynomial to one value

Original source: Sun Shuzhou's PKC Forum post

The specification says that ExpandS derives a child seed for each component of s1 and s2 (physical p. 9). RejBoundedPoly writes the intended two-byte nonce at rho[HBYTES], but seeds the ICCS DRBG expander with only SEEDBYTES+2 bytes (sampling.c:240–253). Since HBYTES=2*SEEDBYTES, the nonce lies outside the consumed prefix. All l+k calls therefore return the same ternary polynomial p; fresh keys confirm that every packed s1 and s2 block is identical. The bug is byte-identical in all six submitted source trees.

The public relation consequently collapses from module-LWE to one secret polynomial. If A_ij are the public matrix entries and 2^beta*t1_i+t0_i=sum_j A_ij*s_j+e_i, then

2^beta*t1_i = (1 + sum_j A_ij)*p - t0_i  (mod q),

where every coefficient of the public-key rounding residual t0_i is bounded by 2^(beta-1). Here beta denotes the implementation's rounding exponent, not the unrelated parameter β in the specification. Scalarizing these public negacyclic equations gives ordinary bounded-error LWE with dimension n and k*n samples, instead of the submitted MLWE instance.

At pinned lattice-estimator commit 53da598, the ADPS16/Core-SVP model gives best costs of about 42.6, 114.7, and 95.5 bits for CS-128/256/512. The post's independent models give 43.7/113.3/94.0 bits under its Core-SVP settings and 68.8/135.9/118.0 with MATZOV costing. All are far below the respective 128-, 256-, and 512-bit targets claimed on physical pp. 33 and 35. The estimates are heuristic lattice costs rather than completed full-size runs; the post reports exact recovery on otherwise faithful n=32 and n=64 scaled instances. The exact public reduction plus the large modeled shortfalls violate the claimed levels and are Critical.

Reproducing

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

make -C sign-07 libs
python3 sign-07/reproduce_expand_s_collapse.py
LATTICE_ESTIMATOR_PATH=/path/to/lattice-estimator \
  /path/to/sage/python sign-07/reproduce_expand_s_estimate.py

The first witness generates fresh submitted keys, requires every packed secret/error polynomial to be identical, checks a changed-seed control, and verifies the faulty seed length in all source copies. The Sage witness checks the estimator commit and reproduces the three independent Core-SVP estimates; it does not perform full-size key recovery.