Impossible

Challenge summary

We are given a Rust project (Cargo, using the old bellman = "0.1.0" / pairing = "0.14.2" crates, BLS12-381 curve) that implements a tiny Groth16 zk-SNARK circuit, MintCircuit:

balance * 1 = amount        (public input: amount)
balance * 1 = 100           (balance is hard-wired to 100)

So the circuit only accepts proofs where the public “mint amount” equals 100. The verifier’s job is to reject any proof claiming a larger mint. We are handed the ceremony’s vk.bin (verifying key) and a secret file:

PRERZBAL_VQ=3p311q9qso7735r42643s394qp2p10ns
GNH=3894627051107121998319229043008213446770981528672674568925122813412699817

The key names are ROT13’d (“PRERZBAL_VQ” -> “CEREMONY_ID”, “GNH” -> “TAU”), but the values are given in the clear:

CEREMONY_ID = 3c311d9dfb7735e42643f394dc2c10af
TAU         = 3894627051107121998319229043008213446770981528672674568925122813412699817

This is the leaked trusted-setup secret (“toxic waste”) of the Groth16 ceremony — literally “a secret that was not hidden nearly well enough”.

Vulnerability

lib.rs::derive(tau) deterministically re-derives the entire toxic waste (alpha, beta, gamma, delta, plus two extra “g1-scale”/“g2-scale” generator scale factors) as raw BLS12-381 scalar field elements, by hashing tau with blake2b under different domain labels. Groth16’s soundness relies entirely on alpha/beta/gamma/delta/tau being destroyed after the ceremony. Since we can recompute them from the leaked tau, we can act as the “trusted setup” ourselves and forge a proof for a public input the circuit would never actually accept (amount = CLAIM = 1_000_000_000, dwarfing the real balance of 100).

Attack

1. Re-derive [alpha, beta, gamma, delta, g1_scale, g2_scale] = derive(TAU).
2. Reconstruct the verifying key and diff it against the given vk.bin to confirm the derivation is right. First attempt (naive alphaG1 etc.) did NOT match vk.bin — it turned out the ceremony uses scaled generators G1’ = g1_scaleG1, G2’ = g2_scaleG2, so vk.alpha_g1 = alphag1_scaleG1, vk.gamma_g2 = gammag2_scaleG2, vk.ic[i] = ic_ig1_scale*G1, etc. (ic0, ic1 computed via mint_ic_scalars(tau, alpha, beta, gamma), a Lagrange-interpolation over the 4-element FFT domain matching the 2-constraint R1CS -> QAP). Once the scale factors were applied, all 8 VK fields matched exactly.
3. Forge a proof using only vk.bin’s real group elements plus the derived scalars (this makes the construction invariant to the generator scaling, so we don’t even need to fuss with g1_scale/g2_scale again): Groth16 verification checks e(A,B) * e(acc,-gamma) * e(C,-delta) == e(alpha_g1,beta_g2) where acc = vk.ic[0] + CLAIM*vk.ic[1] (a real G1 point, computable directly from vk.bin’s IC values and the public claim). Choose: A = vk.alpha_g1 B = vk.beta_g2 => e(A,B) = e(alpha_g1,beta_g2) exactly C = -(gamma/delta) * acc (gamma/delta ratio is scale-invariant) This makes the whole equation hold by construction, for ANY public input we like — we never touch the actual R1CS witness at all.
4. Verify locally with the real verify_proof() + vk.bin before sending anything over the wire — confirmed true.
5. Started the challenge instance (TCP+SSL, impossible-<id>.chall.nnsc.tf:1337), sent <ceremony_id>:<hex-encoded proof>\n over TLS (stdlib ssl, CERT_NONE since it’s a self-signed cert as with ncat --ssl). Server replied: authorized balance 100 / requested mint 1000000000 / accepted, followed by the flag.

Lesson

Groth16 (and any KZG/pairing-based SNARK with a trusted setup) is only as sound as the ceremony’s toxic waste. If tau (or anything it’s derived from) ever leaks, an attacker who knows alpha/beta/gamma/delta as scalars can forge an accepting proof for literally any public statement, without touching the circuit’s constraints at all — the “proof” no longer proves anything.