Sigma Protocols & Pairings (Zero-Knowledge Proofs)
Sigma Protocols & Pairings (Zero-Knowledge Proofs)
Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-24 | Status: Solved Techniques: fiat_shamir_transform, hvzk_simulator, pairing_bit_test, schnorr_proof, special_soundness_extractor, unreduced_response_bit_alignment
Summary
Task: CryptoHack ZKP series of Schnorr-style sigma protocols (intro/special-soundness/SHVZK/NIZK/too-honest) plus a BN254 pairing-based bit oracle. Solution: honest Schnorr proof, special-soundness witness extraction from commitment reuse, HVZK simulator forgery, Fiat-Shamir NIZK, integer-unreduced-response bit-alignment leak via e=2^768, and bilinearity bit test e(yG,b*xG)=e(yG,xG)^b.
Sigma Protocols & Pairings — CryptoHack (Zero-Knowledge Proofs)
Description
CryptoHack "Zero-Knowledge Proofs" category. A graded series of Schnorr-style sigma (Σ) protocols built on a 512-bit safe-prime Diffie-Hellman group, plus a pairing-based offline challenge on BN254. Each challenge teaches one property of sigma protocols: completeness, special soundness, honest-verifier zero knowledge, the Fiat-Shamir transform, and a "too honest" implementation bug.
This single writeup covers six challenges. Five are interactive Schnorr sigma
protocols; one is an offline pairing puzzle. The recurring object is the Schnorr
proof of knowledge of a discrete log w such that y = g^w, with the classic
3-move structure:
Prover Verifier
a = g^r -----> (commitment)
<----- e (challenge)
z = r+e*w -----> (response)
check g^z == a * y^e
Each challenge breaks (or uses) a different leg of this structure.
Shared group (sigma 1–4)
python read-only • copy allowedp = 0x1ed344181da88cae8dc37a08feae447ba3da7f788d271953299e5f093df7aaca987c9f653ed7e43bad576cc5d22290f61f32680736be4144642f8bea6f5bf55ef q = 0xf69a20c0ed4465746e1bd047f57223dd1ed3fbc46938ca994cf2f849efbd5654c3e4fb29f6bf21dd6abb662e911487b0f9934039b5f20a23217c5f537adfaaf7 g = 2 # p = 2q+1 safe prime, g generates the order-q subgroup
1. Sigma Intro — crypto{sigma_protocol_complete!}
Goal: Run an honest Schnorr proof. We are given the witness w (and y = g^w).
The verifier sends the challenge e; we must respond correctly.
This is just completeness: pick random r, commit a = g^r, receive e,
respond z = (r + e*w) mod q. The verifier checks g^z == a * y^e.
python read-only • copy allowedw = 0x5a0f15a6...be00e83 # given witness r = random.randint(0, q-1) a = pow(g, r, p) send({"a": a}) e = recv()["e"] z = (r + e*w) % q send({"z": z}) # -> flag
Why it works: g^z = g^(r+e*w) = g^r * (g^w)^e = a * y^e. ∎
Teaching: the 3-move (a, e, z) structure and completeness of Schnorr.
2. Sigma Special Soundness — crypto{specially_sound_sigmas}
Goal: Here the server is the prover (the witness w is the flag) and we
are the verifier choosing the challenges. The server is willing to prove twice
— and (the bug) reuses the same nonce r across both rounds:
python read-only • copy allowed# server side (from source): self.r = random.randint(0,q); self.a = pow(g,self.r,p) # round 1 commitment ... self.z = (self.r + self.e *flag) % q # round 1 response # self.r = random.randint(0,q) # "oh no they reused the same r" self.a2 = pow(g,self.r,p) # round 2: SAME r self.z2 = (self.r + self.e2*flag) % q # round 2 response
Two accepting transcripts with the same commitment a but different
challenges e1 ≠ e2 are exactly the input to the special-soundness
extractor. From
z1 = r + e1*w
z2 = r + e2*w -> z1 - z2 = (e1 - e2)*w
we recover the witness directly:
python read-only • copy allowede1, e2 = 1, 2 # we are the verifier; pick distinct e # ... collect z1 (round 1) and z2 (round 2) ... flag_int = ((z1 - z2) * pow(e1 - e2, -1, q)) % q # special-soundness extractor pad = long_to_bytes(flag_int) # crypto{...} + os.urandom padding -> strip
flag_int is the padded flag (FLAG + os.urandom(...)); long_to_bytes then
locate crypto{...}.
Teaching: reusing a nonce/commitment across two sigma runs lets the verifier extract the witness via special soundness — this is the soundness proof turned into an attack (and the same algebra as ECDSA/Schnorr nonce reuse).
3. Sigma SHVZK (Special Honest-Verifier Zero Knowledge) — crypto{so_honest_very_zero_knowledge}
Goal: Produce an accepting transcript (a, e, z) for a challenge e that the
server chooses and tells us in advance, without knowing the witness w.
When the challenge is known beforehand, the honest-verifier ZK simulator
produces a perfectly distributed accepting transcript with no witness. Pick a
random response z first, then solve the verification equation for a:
python read-only • copy allowede = recv()["e"]; y = recv()["y"] # server gives e and y up front z = random.randint(0, q-1) a = (pow(g, z, p) * pow(y, -e, p)) % p # a = g^z * y^{-e} (SIMULATOR) send({"a": a, "z": z}) # -> flag
Check: g^z = a * y^e ⇔ a = g^z * y^{-e}. The transcript verifies by
construction, yet proves nothing — which is the whole point of zero-knowledge.
Teaching: the HVZK simulator. A transcript whose challenge is fixed/known in
advance carries no knowledge of the witness; this is why a real verifier must
pick e after seeing a.
4. Sigma NIZK (Fiat-Shamir) — crypto{shvzk_and_ss_to_nizk}
Goal: Send a non-interactive proof. The verifier no longer sends e;
instead both sides derive it from the commitment via a hash (Fiat-Shamir):
python read-only • copy allowede = bytes_to_long(sha512(str(a).encode()).digest()) % 2**511
We are given w, so just produce an honest NIZK:
python read-only • copy allowedw = 0xdb968f92...677ddc0 # given witness r = random.randint(0, q-1) a = pow(g, r, p) e = bytes_to_long(sha512(str(a).encode()).digest()) % 2**511 # Fiat-Shamir z = (r + e*w) % q send({"a": a, "z": z}) # -> flag
(A witness-free simulator also works: grind a random a of the form
g^z*y^{-e} until e = H(a) matches — but with the witness in hand the honest
route is one shot.)
Teaching: Fiat-Shamir converts an interactive sigma protocol into a
signature / NIZK by replacing the verifier's challenge with H(a) (combining
SHVZK + special soundness ⇒ NIZK in the random-oracle model).
5. Sigma Too Honest — crypto{REDACTED}
Goal (the real break): An RSA-group Schnorr variant where the response is
computed over the integers — no mod q — and the server never validates the
challenge range.
python read-only • copy allowed# server source (2048-bit N, RSA group): g = 2; k1 = 512; k2 = 128 R = 2**(2*k2 + k1) # = 2**768 self.r = random.randint(0, R) # r in [0, 2**768) self.a = pow(g, self.r, N) y = pow(g, -flag, N) # y = g^{-w} # expected: 0 <= e < 2**k2 (=2**128), but NOT enforced: self.z = (self.r + self.e * flag) # <-- INTEGER, no mod!
Because z = r + e*flag is a plain integer with r < 2^768, choosing the
challenge e to be a multiple of 2^768 aligns e*flag so its low 768 bits
are zero. Then the low 768 bits of z are exactly r, and the rest is
e*flag. One query recovers the flag:
python read-only • copy allowede = 2**768 # multiple of R's bound 2**768 send({"e": e}) z = recv()["z"] r = z % (2**768) # low 768 bits = r exactly (since r < 2**768) flag = (z - r) // e # the witness, in one query assert r + e*flag == z assert pow(2, -flag, N) == y # verify against y = g^{-flag} mod N
long_to_bytes(flag) then contains crypto{...} plus os.urandom padding.
Teaching: three coupled mistakes — (a) the response must be reduced
mod the group order; an unreduced integer response leaks bits; (b) a
chosen oversized challenge exploits bit-alignment; (c) the server must
validate the challenge bound e < 2^k2. Any one of the three fixes kills the
attack.
6. Pairing Based — crypto{Pa1rings_R_Str0ng} (offline)
Goal: Recover the flag from an offline file of BN254 pairing tuples, one per flag bit. The generator:
python read-only • copy allowedfrom py_ecc.optimized_bn128 import G1, G2, multiply, pairing def gen_test(is_true): x = randint; y = randint bias = 1 if is_true else random_2byte # bias=1 for bit 1, random for bit 0 xG = multiply(G1, x) # in G1 yG = multiply(G2, y) # in G2 zG = pairing(yG, multiply(xG, bias)) # in GT = e(G2,G1)^(x*y*bias) return xG, yG, zG for bit in bin(int(FLAG.hex(),16))[2:]: challenges.append([xG, yG, zG])
Bilinearity gives e(yG, bias*xG) = e(yG, xG)^bias = e(G2,G1)^(x*y*bias). So
without knowing x, y we can test the multiplier bias: a bit is 1 iff
zG == e(yG, xG) (the bias = 1 case). Reconstruct the stored integer tuples
into py_ecc points and pair:
python read-only • copy allowedfrom py_ecc.optimized_bn128 import pairing, FQ, FQ2, FQ12 mk_g1 = lambda t: (FQ(t[0]), FQ(t[1]), FQ(t[2])) # (FQ,FQ,FQ) mk_g2 = lambda t: (FQ2(t[0]), FQ2(t[1]), FQ2(t[2])) # (FQ2,FQ2,FQ2) mk_gt = lambda t: FQ12(t) bits = [] for ln in open('files/pairingbased__output.txt'): xG_r, yG_r, zG_r = ast.literal_eval(ln.strip()) xG, yG, zG = mk_g1(xG_r), mk_g2(yG_r), mk_gt(zG_r) expected = pairing(yG, xG) # e(yG, xG) = e(G2,G1)^(x*y) bits.append('1' if zG == expected else '0') # bias=1 -> bit 1
The file yields 199 bits (the MSB of c=0x63 is 0, so bin()[2:] dropped a
leading zero). long_to_bytes(int(''.join(bits), 2)) reconstructs the flag.
Teaching: bilinearity e(yG, b*xG) = e(yG, xG)^b lets you test the secret
multiplier b against the no-multiplier baseline — a clean illustration of how
pairings turn a multiplicative relation into a checkable equality.
All Flags
1. Sigma Intro crypto{sigma_protocol_complete!}
2. Special Soundness crypto{specially_sound_sigmas}
3. Sigma SHVZK crypto{so_honest_very_zero_knowledge}
4. Sigma NIZK crypto{shvzk_and_ss_to_nizk}
5. Sigma Too Honest crypto{REDACTED}
6. Pairing Based crypto{Pa1rings_R_Str0ng}
Flag (frontmatter)
crypto{REDACTED}