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

TRINE (sign-30)

sign-30-1: The normal build deterministically exposes every signing key

Original source: Feussner's PKC Forum post

The submitted normal build compiles every parameter set with -DUSE_SHA3 and links randombytes.c (Makefile:33–46,53–67). Its global AES-CTR DRBG state is zero-initialized, randombytes.h exposes no initialization function, and no normal-build caller invokes randombytes_init. Key generation immediately obtains the complete secret seed from this state (trine.c:178–213). The separate ICCS/KAT path uses randombytes_iccs.c and is not affected.

Every fresh normal-build process therefore generates the same public and secret key. An attacker can locally repeat key generation and sign an arbitrary fresh message under the victim's public key. The source pattern is identical across the six normal reference builds, so this is a complete EUF-CMA break rather than only reduced key entropy.

Reproducing

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

python3 sign-30/reproduce_unseeded_forgery.py

The witness compiles the archived TRINE-128-ShortSig normal sources. Independent victim and attacker processes produce identical complete key pairs; the attacker secret signs a fresh message accepted under the victim public key. Explicitly distinct DRBG seeds give distinct keys as a control.

sign-30-2: The specified 128-bit round seeds permit collision-accumulation forgeries

Original source: Feussner's PKC Forum post

The pinned analysis and reproducer validates the following result.

The direct specification uses unsalted 128-bit per-round seeds (Algorithms 6–8, physical pp. 13–14; parameter tables, p. 15). Birthday collisions at a fixed round therefore make two ordinary signatures share the same decoded round object. Their different opened labels expose equivalences that can be accumulated: one edge suffices for Balanced, while ShortSig uses a connected label graph. The recovered equivalences yield a valid witness and a fresh-message forgery.

At 2^64−1 signing queries, exact ideal-model tables give roughly 50% success with total attacker costs of 2^94.25 cycles for Balanced and 2^96.99 for ShortSig, below the 128-bit claim. The artifact validates the resource model, executes reduced-seed forgeries through the specification-aligned verifier, and confirms at full entropy that the specified signature layout works. The submitted source adds a 256-bit signature salt and is not affected, but its signatures are 32 bytes longer than the specified format.

Reproducing

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

sh sign-30/reproduce_seed_collision.sh

sign-30-3: SHAKE256 capacity limits TRINE-512 transcript collision security

The normal build selects USE_SHA3 (Makefile:34). Its transcript hash is incremental SHAKE256 (hashkdf.c:255–313). Signing absorbs the message into a fresh transcript before any round commitments (trine.c:358–379); verification reconstructs and absorbs those same commitments after the supplied message (trine.c:576–615). No message length or salt is absorbed before the message in this path.

SHAKE256 has a 512-bit capacity. For two controlled, equal-length messages, a birthday search over one rate block finds post-permutation states with the same capacity in about 2^256 work. A second controlled block cancels the rate-state difference, leaving identical complete states before the common commitment suffix and padding. The attacker obtains one signature on either message; verification recomputes the same transcript digest for the other and accepts the unchanged signature. The two-block messages fit the submitted message interface. This construction is an analytic, below-512-bit EUF-CMA attack that does not require guessing or resetting the signer's randomness.

Reproducing

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

python3 sign-30/certify_shake_capacity.py

The certificate checks the normal build flag, message-first transcript order, and SHAKE256 backend in both 512-bit variants. It verifies the structural preconditions, not an infeasible 2^256 collision search.

sign-30-4: TRINE-512's invariant-attack estimate falls about 5.5 bits below target

The specification estimates the corank-one invariant attack as O(q^((n−2)/2) n^4 (log q)^2) (§5.3, physical pp. 19–20; §6.2, p. 22), using the faster point-sampling heuristic from Narayanan, Qiao and Tang. It explicitly selects q using this estimate. With TRINE-512's n=81 and q=4093, the stated factor is q^39.5, not q^40. Counting the printed polynomial factors gives about 2^506.5 bit operations, roughly 5.5 bits below the 512-bit target. The 128- and 256-bit table entries agree with the same calculation to rounding precision; replacing 39.5 by 40 nearly reproduces the 512-bit entry.

This is a conditional below-target lead, not a demonstrated attack. The faster corank-one sampling is heuristic, its distribution has not been established, and the O notation hides a constant of about 45 or more that could erase the margin. No full-size equivalence recovery or calibrated cost has been demonstrated.

Reproducing

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

python3 sign-30/reproduce_invariant_estimate.py

The certificate checks both submitted 512-bit parameter headers and recomputes all three rows. It does not execute the exponential search.

sign-30-5: Scalar multiples of the response vectors verify

A TRINE response d_i represents a corank-one projective point. The canonical form CF(ϕ, d_i) that verification recomputes is constructed to be invariant under replacing d_i by a nonzero scalar multiple (§2.4, pp. 6–8; Algorithm 7, p. 13). The signature, however, transmits the vectors d_i ∈ F_q^n themselves (the first TRINE_K · TRINE_n 12-bit elements), and neither the specification nor crypto_sign_verify fixes a canonical representative (trine.c:493–650, canonical.c:340–362). Replacing any response vector d_i by λ·d_i for λ ∈ F_q^* therefore leaves every recomputed canonical form, the transcript hash and the verdict unchanged.

On TRINE-128-ShortSig, multiplying all 36 response vectors by the distinct scalars 2 to 37 changed 1,181 of 1,652 signature bytes, and the signature still verified. Negating a single vector also verified. Adding 1 to one coordinate, scaling only the first half of one vector, and changing the message were all rejected. The same results held on TRINE-128-Balanced (K = 52) and TRINE-256-ShortSig (K = 76). Every verification was the first library call in its own fresh process.

Each signature thus has (q − 1)^K encodings, for example 4092^36 ≈ 2^432 at TRINE-128-ShortSig. TRINE claims EUF-CMA (§5.2, p. 16), and these aliases give no signature on a new message, so the finding is Medium. Because the scale freedom is in the specified response encoding rather than in a parser, it is a design issue. Normalizing each response (for example, scaling so its first nonzero coordinate is 1) before encoding, and rejecting non-normalized responses, would remove it.

Reproducing

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

python3 sign-30/reproduce_response_scaling.py
NGCC_LONG=1 python3 sign-30/reproduce_response_scaling.py

The default run checks TRINE-128-ShortSig in about 20 seconds. NGCC_LONG=1 adds TRINE-128-Balanced and TRINE-256-ShortSig, which takes about 5 minutes. The script does not run the 512-bit profiles.