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

Chinith (sign-05)

sign-05-1: The final Fiat–Shamir challenge omits ã0, allowing public-key-only universal forgery

Original source: Feussner's pqc-forum post and attached analysis Follow-up source: Chinith team's PKC Forum response

The submission claims EUF-CMA security (§9.1.5–9.1.6), which is trivially violated: anyone can sign any message under any public key.

The specification binds the QuickSilver constant term into the final challenge, chall3 ← H32(chall2 ∥ ã0 ∥ ã1 ∥ … ∥ ãd−1 ∥ ctr) (SM4th.Sign line 24, physical PDF page 60; uBlockith line 23, page 71; Vistrutith line 19, page 92). The verifier reconstructs ã0 from the public key and the committed witness and recomputes that hash (SM4th.Verify lines 19–21, page 63). ã0 is the only value that depends on whether the committed witness satisfies the public one-way-function relation.

The implementations never hash ã0. hash_challenge_3_init absorbs chall_2 and then deg − 1 field elements starting at the signature's ã1 (sm4th_d3_128f_loose/sig_impl.c:104-113). The signer computes a0_tilde and frees it unused (:440-458,516). The verifier also computes it (:652-658), hashes only ã1…ãd−1 (:670-671), compares chall_3 (:675), and frees a0_tilde (:679). uBlockith (utils_ublock/sig_impl_ublock.c:203) and Vistrutith (utils_vistrutah/sig_impl_vistrutith.c:205) do the same, as do all optimized copies. A forger therefore runs the ordinary signer with the victim's public key and a false witness, for example the extended witness of an all-zero key. All remaining commitment, consistency and grinding checks are honestly satisfied. Signer and verifier share the defect, so self-generated KATs pass.

Follow-up Analysis

The Chinith team confirms that every implementation must bind a_tilde_0 through a_tilde_(d-1) and describes the omission as an implementation oversight. The same response lists three additional specification corrections concerning the d=2/d=3, EM/non-EM, and degree-lifting formulas; those errata are not separately classified here.

Proposed fixes

The team's response proposes including every coefficient a_tilde_0, ..., a_tilde_(d-1) in both signing and verification. 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).

make -C sign-05 exploit
for b in sign-05/bin/reproduce_forgery_*; do "$b"; done

For each parameter set, the witness generates a victim key pair with sig_keygen and wipes the secret key. It checks that the all-zero OWF key is not a preimage of the public key, then signs with that key's witness while claiming the victim's OWF output. The public sig_verify accepts the forged signature, and a one-bit message change is rejected. Each set prints ATTACK sign-05-1 <set> CONFIRMED; all 14 were confirmed.

sign-05-2: Signing indexes lookup tables with the secret key

Key generation evaluates the one-way function on the secret key (sm4th_d3_128f_loose/sm4th_d3_128f_loose.c:43). Every signature re-derives its output and the extended witness from the secret key again (:64,72). The submitted Makefiles select table S-boxes (sm4th_d3_128f_loose/Makefile:4, vistrutith_d3_512f/Makefile:4, and USE_SBOX_TABLE ?= 1 in the optimized trees). SM4th therefore reads the 256-byte SM4_S table at key-dependent round words (utils_sm4/sm4_sbox.c:42-45, utils_sm4/sm4_core.c:208-216). uBlockith reads eight 2-KiB T-tables in its middle rounds (utils_ublock/ublock_core.c:61-62,137); its comments acknowledge the Flush+Reload risk and harden only the first and last rounds. Vistrutith reads AES T-tables (utils_vistrutah/vistrutah.c:37,105-134). A co-resident cache observer can therefore see secret-key-dependent addresses on each signature. No key recovery is demonstrated.

Constant-time fix (easy, hence Low): the submission already contains table-free code. Building without SM4_SBOX_TABLE computes the SM4 S-box as an affine map, inversion by fixed exponentiation with masked multiplication, and another affine map (utils_sm4/sm4_sbox.c:47-126, fields.c:253-286). Vistrutith has a computed S-box path when SBOX_TABLE is undefined (vistrutah.c:187). Faster constant-time options are AES instructions between two pshufb affine transforms for SM4, AES instructions for Vistrutah, and a 16-entry in-register pshufb lookup for uBlock's 4-bit S-box.

Reproducing

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

Inspect the cited build flags and table reads in any reference variant; the lookup indices are round words derived from the secret one-way-function key.

sign-05-3: The specified opening-rejection retry cannot make progress

Original source: changke's PKC Forum post Follow-up source: Chinith team's PKC Forum response

The three signing algorithms increment ctr only when chall3 fails the trailing-zero grinding condition. If that condition passes but BAVC.Open returns bottom because the opening exceeds Topen, the loop repeats with the same counter and otherwise unchanged hash input. It therefore derives the same challenge and rejects the same opening forever (SM4th.Sign lines 23–31, physical PDF page 60; uBlockith.Sign lines 22–30, page 71; Vistrutith.Sign lines 18–26, page 92).

The rejection branch is reachable. For SM4th-d3-128s-lo, the valid indices (0,100,...,1000) map to eleven leaf positions whose root-path union contains 135 nodes. The specified opening uses 135-2·11+1=114 sibling seeds, exceeding Topen=102. The tuple fits the 121 index bits and can be followed by the required seven zero grinding bits. This proves a specification-level non-progress case, not a practical chosen-message denial of service: no transcript producing that tuple was searched, and the inspected implementation advances the counter after a rejected batch.

Follow-up Analysis

The Chinith team confirms that the counter must advance after either grinding rejection or opening rejection. Its response also corrects the stated one-trial probability from 2^-wgrind to 2^-wgrind·alpha, where alpha is the probability that BAVC.Open accepts.

Proposed fixes

The team's response proposes breaking only after both the grinding test and BAVC.Open succeed, returning failure if the 32-bit counter is exhausted, and otherwise incrementing the counter before retrying. This 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 sign-05/reproduce_open_retry.py

The witness recomputes every leaf position, the path-union size, and the opening-size rejection. Inspect the cited signing algorithms for the unchanged-counter retry.

sign-05-4: uBlockith-EM witness misalignment reduces the specified relation to a two-round fixed point

Original source: IIE-AIC Team's PKC Forum post and pinned artifact

The specification's 3,072-bit EM encryption witness begins with the secret input S0, yet uBlockith.OWFConstraints selects the encryption witness from offset l_ke=0, and uBlockith.EncCstrnts prepends the same input again (Table 2 and physical PDF pages 67–69). The checked chain is therefore

S0 || S0 || S2 || ... || S22 || out.

Its first constraint is only DoubleRound_0(S0)=S0; the remaining constraints follow freely chosen intermediate blocks, and the loop stops at S22 without reading out=S0 xor pk2. Thus the specified relation does not bind the public output. A fixed point of the first two public-keyed uBlock rounds gives a witness for any pk2 and any message.

The posted guess-and-determine method fixes 108 nibble-spread input bits and SAT-solves the residual system. At this same g=108 point, eight wrong guesses for a real public first component took 17.1 seconds on average, while the planted-instance mean was 22.3 seconds. This gives the reported extrapolation 2^108 · 2^27.5 = 2^135.5 double-round evaluations. The full enumeration was not run, so the empirical cost remains Probable, but the real-key measurement directly supports the extrapolation and its large margin below the claimed 256-bit level supports Critical severity.

Further extension to IIE-AIC Team's analysis

The artifact estimates that about 1-1/e ≈ 63% of public first components have a fixed point under the random-permutation heuristic. Accounting also for the independent w[0]·w[1]=0 constraint thins the expected fixed-point count from 1 to 3/4, so about 1-exp(-3/4) ≈ 53% of first components are expected to have an admissible fixed point. This changes the affected-key fraction, not the attack cost when such a point exists.

The source duplicates the first witness block too (ublockith_ublock_256.c:181,190,264; ublock_constraints.c:778–784), but its final-round branch reads out directly. It therefore does not have the spec-literal forgery relation. Instead, once the final Fiat–Shamir challenge is corrected to bind the reconstructed constant term, honest uBlockith-EM signatures fail. The post reports this for both parameter sets and implementation families; our reference-256f replay obtained 0/5 valid signatures, while the non-EM control and a one-block-offset repair each gave 5/5.

Proposed fixes

The post proposes either selecting the EM encryption witness after S0 or not prepending in inside EncCstrnts. This 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).

sh sign-05/reproduce_em_constraints.sh

The wrapper downloads the public artifact at a pinned commit, applies its instrumentation only to temporary copies of the archived source, checks the uBlock core against its public vector, and replays the non-EM, EM, and shifted-witness controls. It also validates the clear constraint reduction for two unrelated public outputs. The final LIMITATION line records that the 2^135.5 estimate is an extrapolation rather than a completed enumeration.

sign-05-5: Vistrutith combines three constraint families as one polynomial

Original source: IIE-AIC Team's PKC Forum post and pinned artifact

Vistrutith creates three separate arrays of normal, input/output-0, and input/output-1 constraints. The prover passes one tag from each array to zk_hash_SSS_3_update as though they were the three coefficients of one degree-two polynomial (vistrutith_vistrutah_512.c:139–145). The verifier correspondingly hashes z_norm + delta·z_io0 + delta^2·z_io1 (:163–170). This is not the coefficient decomposition of any one submitted constraint and loses the intermediate coefficients of the three actual constraint polynomials. The file is byte-identical in both parameter sets and implementation families.

After instrumenting signing and verification to bind the reconstructed constant term, honest Vistrutith-512f signatures failed 5/5. A clear-value control simultaneously found zero nonzero values in each of the three 576-element constraint arrays, excluding an invalid witness as the cause. The current final-challenge omission masks this independent completeness error. No forgery or security-level reduction follows, so the finding is Low.

Reproducing

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

sh sign-05/reproduce_em_constraints.sh

The Vistrutith portion prints five signer/verifier constant-term mismatches, followed by two controls in which all 1,728 honest constraint values are zero.

sign-05-6: The specified SM4th-EM relation omits the public output

Original source: Sun Shuzhou's PKC Forum post

For every SM4th-EM set, Table 2 gives l_ke=0 and l_enc=1024. SM4th.OWFConstraints nevertheless selects w[0..1024) as the encryption witness after separately taking w[0..128) as the secret input (physical p. 58). SM4th-EM.EncCstrnts then prepends that input again (p. 57). Its effective word sequence is therefore X0,...,X3,X0,...,X31,out, and its 32 five-word windows stop at X31: the public output out=X0 xor pk2 is never read.

The first four duplicated-output constraints form an invertible four-word linear system in X0,...,X3 once the public round keys and patched-inversion constants are fixed. Every later witness word can then be computed forward. This gives a closed-form satisfying witness independent of pk2; only the separate two-bit keyspace constraint filters candidates. The post reports that the witness satisfies the literal relation for 2,048/2,048 random keys, with 74.22% passing that filter, and that a signer built with the specified offset produces an accepted public-key-only forgery in 0.34 seconds.

The surrounding specification contradicts that literal slice: the witness layouts on physical pp. 51, 53, 55, and 57 define the encryption witness as the 896-bit middle portion, and the constraint input on p. 57 has length 32(R-4) bits. The post also reports that none of 2,048 honest witnesses satisfies the literal relation, so a functioning implementation cannot use it unchanged. The delivered prover and verifier instead skip the already supplied input block (Implementations/Reference_Implementation/sm4th_em_d2_128s_loose/sm4th_sm4_128.c:216–244, 835–859); all eight reference and optimized copies agree. This is therefore a confirmed transcription/type inconsistency in the frozen design, but the submitted implementation follows the only interoperable reading and is unaffected. It is Low rather than a break of the working signature scheme.

Proposed fixes

The Chinith team's 2026-10-09 response proposes an explicit EM-case witness slice in the revised specification while retaining the delivered implementation's middle-block selection. This is recorded without evaluating the revision.

Reproducing

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

python3 sign-05/reproduce_sm4th_em_spec_relation.py

The certificate checks the PDF's slice and prepend operations, the four parameter rows, the window boundary that excludes out, the invertibility of the four-word system, and both corrected prover/verifier calls in all eight SM4th-EM source copies. It does not replay the reported 0.34-second patched-build forgery.