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

SQIsignTriangle (sign-27)

sign-27-1: An all-zero signature aborts the verifier process

The submitted verifier passes attacker-controlled encoded signature data to compressed_aux_basis_from_bytes, which asserts that the decoded exponent e_rsp is in range. An all-zero signature fails that assertion and calls abort() instead of returning invalid-signature status. The existing bounded security sweep recorded the same assertion in all four levels. Rebuilding level 1 from source reproduced exit code 134; its honest KAT passes. This is a process-availability flaw only, and the result with assertions disabled has not been established.

Reproducing

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

make -C sign-27 lib/libSQIsignTriangle_lvl1.so
make -C security ngcc_security
security/ngcc_security sign-27/lib/libSQIsignTriangle_lvl1.so sig-zero

The last command intentionally aborts with encode_verification.c:216 and exit status 134. make -C sign-27 test-SQIsignTriangle_lvl1 is the passing honest-signature control.

sign-27-2: Triangle prime sizing relies on the former square-root attack cost

Original source: GitHub issue #10 and its attached cost model

Section 5.3 selects p by requiring p^1/2 > 2^λ and states that the One Endomorphism Problem is equivalent to the underlying isogeny problem. The submitted Level-1 prime already fails that stated rule: for p = 5·2^248-1, p^1/2 ≈ 2^125.2 < 2^128. The following concrete-security paragraph lists only λ ∈ {160,256,512}, omitting the 128-bit set. Wesolowski, ePrint 2026/1486 improves the underlying problem to p^(1/3+o(1)) time and memory. Ouyang, Wei and Xu subsequently proved the smoothness property used by the algorithm, making that asymptotic result unconditional.

Mamah's concrete analysis evaluates the exact submitted Level-1 prime p = 5·2^248-1. With at most 2^80 stored entries it estimates 2^[138.78,143.51] gates for the full attack. The same table estimates the old square-root HyperSolver attack at 2^143 gates on that prime, equal to the usual AES-128 key-search reference when both sides are counted in elementary gates. Thus the submitted prime already had essentially no margin under the old estimate, while the new estimate gains between zero and about 4.2 bits. Its interval straddles the target, but its midpoint, about 2^141.1, is below it. This supplies a quantified candidate-specific route and therefore a Critical Lead, but not a confirmed break.

Publication update: ePrint 2026/1821 was revised on 2026-10-30. Its revised Table 4 retains the 2^[138.78,143.51] gate interval and 2^143 HyperSolver comparator for this exact prime. The paper says other running-time estimates were adjusted; those revised calculations have not been separately reproduced here. This finding remains Critical / Lead.

SQIsign v3 now uses approximately 326-, 505- and 669-bit primes for 128-, 192- and 256-bit targets. This is independent parameter-selection evidence, not an attack threshold for SQIsignTriangle. The 160-, 256- and 512-bit profiles use the same superseded sizing rule, but Mamah's practical-memory study does not give candidate-specific below-target costs for them. No full-size key recovery or forgery was run.

Reclassified from Medium to Critical on 2026-10-16. The status remains Lead because the estimate is model-dependent and straddles the target.

Reproducing

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

Compare §5.3 and Table 6 of sign-27-spec.pdf with the cited papers and issue model. The submitted Level-1 prime is exactly the Level-I prime used in Table 4 of the concrete analysis.

sign-27-3: A known signature transfers to a new message in about 2^(lambda/2) work

Original source: Fouotsa's PKC Forum post and attached analysis Follow-up source: SQIsignTriangle team's confirmation

A signature exposes its response degree q; its auxiliary curve and torsion data recover the same commitment independently of the message. Verification hashes the public-key curve, commitment curve and message to (c1,c2), then checks q mod c1 = c2. A forger therefore keeps any valid signature and searches for a different message whose challenge satisfies that single congruence.

Each challenge component is only lambda/2 bits: the implementation sets byte_len = SECURITY_BITS / 16 and imports that many bytes into each integer, agreeing with the specification's challenge interval of size 2^(lambda/2). The verifier checks (q - c2) mod c1 = 0 without requiring c2 < c1, so several c2 values can succeed for one c1; either codomain component can also supply c1. The search still costs on the order of 2^(lambda/2) classical trials, rather than the claimed 2^lambda. Grover search uses about 2^(lambda/4) generic quantum queries or iterations; no end-to-end gate cost is claimed. A chosen-message signing query supplies the starting signature, making this a direct EUF-CMA attack. It violates every claimed classical security level and is therefore Critical, even though the larger instances remain computationally infeasible.

Reproducing

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

python3 sign-27/reproduce_modular_challenge.py

The witness checks relevant expressions in the archived source, prints the four full-size costs, constructs two distinct accepting challenge pairs for one response degree, and models the hash-to-prime/congruence search in Python at a scaled 16-bit security parameter. It does not call the submitted verifier.

sign-27-4: Distinct challenges can share the identical response, invalidating special soundness

Original source: Fouotsa's PKC Forum post and attached analysis Follow-up source: SQIsignTriangle team's confirmation

The proof claims that two accepting transcripts with the same commitment and distinct challenges yield two different response isogenies, except with negligible probability. That implication is false. In the submitted hash-to-challenge implementation, given one response of degree q, choose any different accepted prime c1' and set c2' = q mod c1'; the unchanged response is valid for the distinct challenge (c1',c2'). In the proof's shifted interval description, one instead samples c1' until this remainder lies in the stated interval. Composing the two identical responses in the extractor produces a scalar endomorphism, not the required non-scalar witness.

This is a deterministic counterexample to the stated two-special-soundness claim, not merely a loose probability bound. It does not establish an additional forgery, so it is tracked as a proof failure rather than a Critical break.

Reproducing

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

python3 sign-27/reproduce_modular_challenge.py

The script models two distinct prime challenges that accept the same fixed degree and checks the corresponding congruences. It checks the submitted source expressions statically but does not execute verify.c.

sign-27-5: Response rescaling gives a practical fresh-message forgery

Original source: Feussner's PKC Forum post and pinned public analysis and reproducer

The specified response has a scaling symmetry. Verification constructs its kernel from ([q]P_pk,P_aux) and ([q]Q_pk,Q_aux). Given an odd replacement q' with the same bit length, set u = q' q^-1 mod 2^e and multiply all four serialized auxiliary-basis coefficients by u mod 2^e. Both reconstructed kernel generators are then multiplied by the same unit, so the subgroup, quotient, and unordered codomain j-invariants are unchanged.

SQIsignTriangle claims EUF-CMA security (§6.4, Theorem 4), which one signing query suffices to violate. For a fresh target message, the attacker publicly recovers the two codomain factors and their challenges (c1,c2), then chooses an odd e-bit q' satisfying q' = c2 mod c1. The public condition 2^(e-1) > 2c1 is sufficient to ensure such a representative. The verifier reconstructs the original kernel but accepts the replacement response against the target challenge. No message search is needed; this is a direct EUF-CMA forgery rather than signature malleability.

We reran three deterministic fresh-key trials at each of the 128-, 160-, 256-, and 512-bit sets. Every first response met the sufficient condition; every transformed signature was accepted on its unqueried target and rejected on its source, while the genuine signature showed the opposite behavior. The observed response exponents were 219–895 and all 12 public transformations completed in under one second on this host. The submission gives no lower-tail bound for honest response sizes, so this establishes practical success on the tested executions rather than a proof that every first response is eligible; an attacker can request another signature after an ineligible response.

Proposed fixes

The SQIsignTriangle team's 2026-09-29 response proposes checking the actual response degree for the challenged codomain factor using Weil pairings and the degree bound, and clarifying a canonical commitment encoding for the hash input. It credits Tako Boris Fouotsa with the earlier missing-check observation and canonical-encoding proposal. This records the submitters' 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-27 exploit-response-rescaling

The wrapper checks out the pinned public reproducer, which builds the unmodified submitted verifier and runs the four source/target controls for three fresh keys at every level. It requires Git, GNU Make, Python 3, GCC, and GMP development headers.

sign-27-6: High bits of the auxiliary-basis coefficients are never authenticated

A SQIsignTriangle signature encodes the auxiliary curve, four coefficients r1, r2, s1, s2 of SQISIGNTRIANGLE_BASIS_COEFF_BYTES bytes each, and q in a field of the same width (encode_verification.c:284–297). compressed_aux_basis_from_bytes reads each coefficient into a full-width integer. It then uses the coefficients only through ec_biscalar_mul(..., e_rsp, ...) and mp_mod_2exp(..., e_rsp, ...), where e_rsp = bitsize(q) (encode_verification.c:202–241). Coefficient bits at positions >= e_rsp are never read and never required to be zero. Equivalently, adding any multiple of 2^e_rsp to a coefficient leaves the decoded auxiliary basis unchanged.

The number of unused bits depends on q in each signature. In the native fresh-process run, e_rsp was 211, 273, 445 and 894 at Levels 1, 2, 5 and 6. This left 52, 28, 12 and 8 unused bits, and every one of them could be flipped on its own and still verify. Setting all of them at once, and adding random multiples of 2^e_rsp to all four coefficients, also verified. Flipping bit 0 or bit e_rsp/2 of any coefficient, and changing the message, was rejected. The earlier run used different signatures and found 8, 28, 28 and 4 unused bits.

The submission states its security as EUF-CMA (§6.4, p. 54), and its feature list (p. 60) states that the scheme "achieves strong EUF-CMA security". These aliases are new valid signatures on already-signed messages, so they violate that explicit strong-unforgeability claim and the finding is rated High. They yield no signature on a new message, so the required EUF-CMA property is not broken. Canonical decoding should reject coefficients >= 2^e_rsp.

Reproducing

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

python3 sign-27/reproduce_coefficient_high_bits.py

The script signs once per level and verifies every single unused-bit flip, the all-bits and random-multiple variants, and the used-bit and message controls. Each verification is the first library call in its own fresh process. It takes about 20 seconds.