Reports › sign-04 · Constant-time review

CEDRUS-alpha (sign-04)

sign-04-1: The 160-bit WOTS implementation authenticates only 128 bits

Original source: NGCC PKC Forum report

Shiyuan reported the defect in the NGCC PKC Forum. The specification converts the complete n-byte WOTS message to an integer. In both 160-bit implementations, however, WOTS_UINT_WORDS is SPX_N/8 = 2, and chain_lengths() loads only two eight-byte words. Bytes 16 through 19 of every FORC or child-XMSS root are ignored by WOTS signing and verification.

The implementation therefore authenticates only a 128-bit prefix at these layers, contradicting the stated 160-bit classical strength. This is not an immediate signature-bit malleability: exploiting it in the full hypertree still requires finding a lower-layer result with the same authenticated prefix. The submitted 2^128 second-preimage estimate is the justified cap; the forum post's separate 2^64 collision figure does not by itself give a 2^64 signature forgery.

Reproducing

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

make -C sign-04 exploit

The first control calls the submitted chain_lengths() and wots_pk_from_sig() on two 20-byte inputs that differ in all trailing 32 bits and obtains identical outputs.

sign-04-2: FORC chain addresses are truncated to eight bits

Original source: NGCC PKC Forum report

Shiyuan reported the defect in the NGCC PKC Forum. The specification assigns a full 32-bit chainAddr with domain 0..k*2^a-1. The implementation writes the value only to address byte 27, so indices congruent modulo 256 generate identical PRF and FORC-chain inputs. The intended k*2^a leaf secrets consequently draw from at most 256 distinct values inside a fixed FORC address context.

This invalidates the specification's independence model and aliases leaves both within and across FORC trees. It does not establish the forum post's coupon-collector claim: ordinary signatures select fresh FORC contexts through their hypertree address, so observations from different contexts cannot be pooled as the same 256 keys without a separate address-reuse attack. A complete adaptive forgery exploiting the aliases remains to be constructed.

Reproducing

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

make -C sign-04 exploit

The second control links the submitted address code and SM3 PRF and confirms that indices 0 and 256 produce identical 32-byte addresses and identical secret values.

sign-04-3: Specified and implemented hash instantiations are incompatible

Original source: NGCC PKC Forum report

Shiyuan documented the mismatch in the NGCC PKC Forum. Specification Section 1.11 pads PK.seed to one 64-byte SM3 block, uses the 22-byte compressed address ADRS^c, and includes PK.seed in PRF(PK.seed,SK.seed,ADRS). The code instead hashes SPX_N bytes of PK.seed followed by the full 32-byte address, while prf_addr() hashes only SK.seed || ADRS and receives no public seed.

Thus a conforming implementation of the PDF cannot reproduce the submitted keys, signatures, or verification results. The discrepancy also removes the specified public-seed domain separation from secret-value generation, but no cross-key attack follows from that omission alone.

Reproducing

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

pdftotext -layout sign-04/sign-04-spec.pdf - | grep -A8 'pad the PK.seed'
sed -n '12,30p' sign-04/Implementations/Reference_Implementation/CEDRUSALPHA-160s/hash_sm3.c
sed -n '12,24p' sign-04/Implementations/Reference_Implementation/CEDRUSALPHA-160s/thash_sm3_simple.c