Rhyme · PQC-X

Design

Minor break The whole secret key is derived from a 256-bit root
Minor break A 512-bit message digest caps forgery at every level

rhyme-1

The whole secret key is derived from a 256-bit root

Minor break · Argued · Cause: parameter size

Property: key recovery

Cost against claim: key recovery 2²⁵⁶ classical, 2^127.7 quantum, against 384/512 classical, 192/256 quantum

Key generation draws a single 256-bit root and derives the public seed and the whole secret key from it; the public seedA is exactly Hgen(root)[0:32]. Guessing the root and comparing its hash with the public key is a full key-recovery attack costing 2²⁵⁶ classical hash calls, or 2^127.7 Grover iterations.

Parameter set	Claim	Attack cost	Verdict
Rhyme-384	384 classical, 192 quantum	2²⁵⁶ classical; 2^127.7 quantum	Minor break
Rhyme-512	512 classical, 256 quantum	2²⁵⁶ classical; 2^127.7 quantum	Minor break
Rhyme-256	256 classical, 128 quantum	2²⁵⁶ classical; 2^127.7 quantum, no margin	Holds

What causes it

Alg. 5 (PDF p.31) draws seed <- {0,1}^rho0 and never gives rho0 a value in the text. Table 3 (PDF p.53) fixes it indirectly: the public- and secret-key sizes only match the code's layout if seedA and K are 32 bytes, and params.h sets SEEDBYTES = 32 in all 16 builds (SHAKE and SM3, reference and optimized).

Evidence

PQC-X traced the key-derivation chain in the reference code (root -> Hgen -> seedA, K) and matched the 32-byte length against Table 3's key-size formulas across all 16 builds. A second member of PQC-X independently re-derived the same chain and the Grover count and confirmed the numbers.

Cause in the specification, traced to the specification text.

Credit

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

rhyme-2

A 512-bit message digest caps forgery at every level

Minor break · Argued · Cause: parameter size

Property: existential unforgeability

Cost against claim: forgery via digest collision at 2²⁵⁶, against 384/512 classical

Verification depends on the message only through mu, a 64-byte digest of the public key and the message, with no salt. A generic birthday collision on mu, found in 2²⁵⁶ hash calls, followed by one signing query on either colliding message, forges a signature on the other.

Parameter set	Claim	Attack cost	Verdict
Rhyme-384	384 classical	2²⁵⁶ classical	Minor break
Rhyme-512	512 classical	2²⁵⁶ classical	Minor break
Rhyme-256	256 classical	2²⁵⁶ classical, no margin	Holds

What causes it

params.h fixes CRHBYTES = 64 in every backend; sign.c squeezes mu = Hgen(pk, m) to 64 bytes and verification compares a hash of (w, mu) against the value carried in the signature, so a collision on mu alone breaks unforgeability. The specification gives mu no explicit length of its own.

Evidence

PQC-X computed the generic birthday cost from the fixed 64-byte digest and checked that the verification equation depends on the message only through mu (Alg. 6 line 3, Alg. 7 lines 5-6). A second member of PQC-X re-verified the digest length across all 16 builds and the collision-to-forgery argument.

Cause in the specification, traced to the specification text.

Credit

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

Implementation

Bugs in the submitted code; the specification is sound on these points.

Minor break The shipped SM3 build samples an undersized challenge, forgeable by guessing it

rhyme-i1

The shipped SM3 build samples an undersized challenge, forgeable by guessing it

Minor break · Argued · Cause: code

Property: existential unforgeability

Cost against claim: key-only forgery below the classical and quantum requirement at every SM3 set

The SM3 build ships a challenge-weight table and a Gaussian width that both differ from the specification's own Table 3, shrinking the challenge space. A forger with no key and no signing query fixes a short z and a challenge value, then searches messages until the derived hash resamples to that same challenge: each trial succeeds with probability 1 over the challenge-space size, so the forgery costs about that size in trials, below the requirement at every level.

Parameter set	Claim	Attack cost	Verdict
Rhyme-SM3-128	128 classical, 80 quantum	2^108.1 classical; 2^53.7 quantum	Minor break
Rhyme-SM3-256	256 classical, 128 quantum	2^212.5 classical; 2^105.9 quantum	Minor break
Rhyme-SM3-384	384 classical, 192 quantum	2^308.4 classical; 2^153.9 quantum	Minor break
Rhyme-SM3-512	512 classical, 256 quantum	2^425.0 classical; 2^212.2 quantum	Minor break

What causes it

The SM3 parameter tables equal the SHAKE tables of the initial commit and were never updated when a later commit retuned the SHAKE and optimized-SM3 hash layer, so the SM3 challenge weight and Gaussian width stay off the specification's Table 3. The SM3-128 known-answer vectors reproduce byte for byte from this unmodified, off-spec build, so it is the build the call's official vectors come from.

Evidence

PQC-X reproduced the SM3-128 known-answer vectors byte-identical to the official ones from an unmodified copy of the reference code, diffed the SM3 tables against the SHAKE and specification tables, and recomputed the challenge-space size for both. A second member of PQC-X re-derived the forgery from the verification code directly, confirming it compares a hash output rather than the raw challenge polynomial, which is the condition that makes the challenge-space size the actual cost.

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

Limits

SHAKE builds use the specified tables and are not affected; only the eight SM3 builds (reference and optimized, all four levels) are.

Credit

Found by PQC-X.