Janaka’s Court: The False Witness

Category: Cryptography / Fiat–Shamir soundness Target: https://pinaka-m02-cyber-xo-x.vercel.app Result: admitted — flag captured

PINAKA{janaka_false_witness_the_question_asked_before_the_answer}

"The court records a witness where none could stand."

1. Challenge overview

The court runs a single HTTP/JSON service exposing:

Each docket names an ordered identity pair (Y0, Y1) in the order-q subgroup of Z_p^*. A deposition is a 1-of-2 Schnorr OR-proof:

Proof = (t0, t1, c0, c1, s0, s1)

proving ∃x : Y0 = g^x OR Y1 = g^x without revealing which branch.

The goal is to produce a valid deposition for the false-witness docket, whose identities were derived by hash-to-group (Z = SHA256(...)² mod p), so nobody knows either discrete log. An honest proof is impossible; the proof must be forged.

Verification (per /court/params):

accept iff (c0 + c1) == c (mod q)
       and g^s0 == t0 * Y0^c0 (mod p)
       and g^s1 == t1 * Y1^c1 (mod p)

where c is the Fiat–Shamir challenge.

2. The bug: unbound commitments

The shipped primitive (pinaka_testimony.py) selects the challenge by binding_mode. The live validator uses mode 0:

def _h_bind(ctx, Y0, Y1, q):
    m = hashlib.sha256(b"PINAKA-M02-FS")
    for lbl, v in (("ctx", ctx), ("Y0", Y0), ("Y1", Y1)):
        m.update(b"|"); m.update(lbl.encode()); m.update(b"|"); m.update(str(v).encode())
    return int(m.hexdigest(), 16) % q

The challenge is therefore

c = SHA256('PINAKA-M02-FS' | ctx | Y0 | Y1) mod q

and it omits the prover commitments t0, t1. That is the fatal flaw.

A sound Fiat–Shamir OR-proof requires the challenge to commit to the announcements:

c = H(ctx, Y0, Y1, t0, t1)      # _h_bind_full / verify_strict

Because c here is a deterministic function of only public, fixed data, the prover knows c before choosing t0, t1. In the honest protocol the challenge is what forces at least one branch to be answered with a real witness; if the prover can choose the challenge first, it can simulate both branches — the standard zero-knowledge simulator for a Schnorr proof. Soundness collapses.

3. The forgery

For a Schnorr proof g^s = t · Y^c, the simulator picks c and s at random and solves for t:

t = g^s · Y^{-c} mod p

Since the OR-proof only requires c0 + c1 ≡ c (mod q), we can split the known challenge arbitrarily and simulate each branch independently:

1. Compute c = _h_bind(ctx, Y0, Y1, q) — public, no commitments.
2. Choose random c0 ∈ [0, q) and set c1 = (c - c0) mod q.
3. Choose random s0, s1 ∈ [0, q).
4. Set t_i = g^{s_i} · Y_i^{-c_i} mod p.

Then both equations hold by construction:

g^{s_i} = t_i · Y_i^{c_i}

No discrete log of Y0 or Y1 is ever needed. Both branches are simulated, which is exactly why the challenge must bind the commitments.

4. Exploit

M02_player/forge.py:

#!/usr/bin/env python3
import json
import secrets
import urllib.request

import pinaka_testimony as pt

BASE = "https://pinaka-m02-cyber-xo-x.vercel.app"

params = pt.load_params()
p, g, q, ctx = params["p"], params["g"], params["q"], params["ctx"]

with urllib.request.urlopen(BASE + "/court/registry", timeout=30) as r:
    reg = json.load(r)
Y0 = int(reg["dockets"]["false-witness"]["identities"]["Y0"])
Y1 = int(reg["dockets"]["false-witness"]["identities"]["Y1"])

# Challenge depends only on public data -> known before choosing t0, t1.
c = pt._h_bind(ctx, Y0, Y1, q)

# Split the challenge and simulate BOTH branches.
c0 = secrets.randbelow(q)
c1 = (c - c0) % q
s0 = secrets.randbelow(q)
s1 = secrets.randbelow(q)
t0 = (pow(g, s0, p) * pow(Y0, (-c0) % q, p)) % p
t1 = (pow(g, s1, p) * pow(Y1, (-c1) % q, p)) % p

dep = {"t0": t0, "t1": t1, "c0": c0, "c1": c1, "s0": s0, "s1": s1}

assert pt.verify(params, Y0, Y1, dep), "local verification failed"
print("local verify: OK")

body = json.dumps({"docket": "false-witness", "deposition": dep}).encode()
req = urllib.request.Request(
    BASE + "/court/depose", data=body,
    headers={"Content-Type": "application/json"}, method="POST",
)
with urllib.request.urlopen(req, timeout=30) as r:
    print(r.status, r.read().decode())

Run:

$ cd M02_player && python3 forge.py
local verify: OK
200 {"docket":"false-witness",
     "flag":"PINAKA{janaka_false_witness_the_question_asked_before_the_answer}",
     "proclamation":"The court records a witness where none could stand.",
     "result":"admitted"}

The shipped verify() accepts the deposition locally, and the live clerk admits it — no witness, no seal exponent, only public data.

5. Root cause and remediation

Root cause: Fiat–Shamir was applied without binding the prover's announcements. c = H(ctx, Y0, Y1) is computable by anyone at any time, so the challenge provides no soundness: a prover can fix c, split it across the two branches, and simulate both.

Remediation:

1. Bind all public transcript values into the challenge, including both commitments (and ideally the docket/statement):
   pythonCopy code

   c = H(ctx, Y0, Y1, t0, t1)   # _h_bind_full / verify_strict

2. Never expose a verification path that selects an unbound challenge mode. Remove binding_mode == 0 from production, or reject it outright.
3. Include domain separation and the full statement (docket name, identity pair, commitments) so proofs cannot be replayed across contexts.
4. Add known-answer tests: for a statement with unknown witnesses, no proof should verify unless produced by a simulator with the challenge fixed by the commitments — i.e. a soundness/forgery test should fail.

With the challenge bound to (t0, t1), the prover must choose the commitments first; then at least one branch's challenge is unpredictable, and answering it requires the corresponding witness — restoring soundness.

6. Flag

PINAKA{janaka_false_witness_the_question_asked_before_the_answer}