Reports › sign-29
Tins (sign-29)
| Candidate | Tins |
|---|---|
| Family | Multivariate (MPC-in-the-head) |
| Archive | Tins.zip (SHA-256: 84affc1f7cbdeec48a7cb6df3349b5708644672f2ac12140c529e74f6d57ca21) |
sign-29-1: One signature reveals the complete signing witness
| Classification | Critical / design |
|---|---|
| Status | Confirmed |
| Affected | Tins128, Tins256, and Tins512 |
| Discovery | Non-trivial |
| Exploitation | One signature and binary Gaussian elimination on at most 1,044 unknowns |
| Credit | Tianyuan Xie |
| Date | 2026-09-22 |
Original source: NGCC PKC Forum report
Tianyuan Xie reported the attack in the NGCC PKC Forum. Tins masks its binary witness (alpha,beta) with vectors over the 12-bit subfield, while publishing p_mid in GF(2^k). After substituting the verifier-reconstructed evaluations into p_mid, the bilinear witness terms cancel in characteristic two. Only a 12-bit additive mask remains, confined to the final subfield coefficient.
Every execution therefore exposes k-12 public binary equations in the 2(n-2) witness bits. Two executions from one signature have full rank for each submitted set: the reported ranks after the first and second executions are 264 then 276, 516 then 532, and 1,032 then 1,044. Recovering the witness is deterministic and inexpensive; the witness satisfies the public NSBC relation and can run the specified signer on arbitrary messages, violating EUF-CMA.
The local reproducer independently performs the attack on a fresh Tins128 key and signature. It uses only the public key and signature after signing, obtains rank 276/276 from two executions, and validates the recovered witness against the public relation. Xie additionally reports end-to-end accepted forgeries on all three sets and exact recovery from all ten usable Tins128 and Tins256 KAT signatures.
Reproducing
Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).
make -C sign-29 exploit