Bounty Hunter

Full solution below. Spoilers ahead.

Task description

If you were any good at this, you’d get paid for it…

This task had no handout, only a live instance, so this writeup is reconstructed from my working notes taken during the competition. The cryptographic reasoning and the field arithmetic I have re-derived from scratch, and they check out; the values that came back from the live service (the committed vector, the commitment hash, the vault’s reply and the flag) are the ones I recorded during the solve.

What the portal exposes

BugLedger is a mock bug-bounty portal for the researcher el1t3_hun73r. It has four pages:

• /reports lists six reports owned by the account, all with payout = no.
• /transparency publishes a snapshot of a committed state vector as 8 shards, with a manifest.
• /playground shows a sample proof that accepted(604) = 1.
• /vault releases a sealed attachment, and the flag, to anyone who submits a valid receipt proving payout_authorized(report_id) = 1 for an owned report.

The published data says payout_authorized = 0 for every report, so the vault has to be fooled with a proof of a false statement. It runs the published verifier (/api/replay/verifier.py) and layers a policy check on top: the report must be owned, the field must be payout_authorized, and the claimed value must be "1".

The scheme, TwinFold-PCS-v2

The snapshot is a vector of 8192 (that is 2^13) elements of a prime field. The prime is

P = 35182531786822156541290684230036086178800502148536840364113258180206318266211

which is prime and sits just under 2^255 (255 bits, so it fits in 32 bytes). The vector is treated as the coefficients of a degree-8191 polynomial and committed with a SHA-256 hash of the coefficient list (the manifest’s commitment began d438f6d5...). A claim field(report_id) = v becomes a multilinear evaluation at a 13-bit Boolean point: bits_le(report_id, 11) followed by bits_le(column, 2), little-endian in each part.

The proof is a folding argument in the FRI/BaseFold family. For each of the 13 rounds i the verifier does four things:

1. It checks that commit(coeffs) equals the pinned commitment: the manifest’s for round 0, and the previous round’s fold_commitments[i-1] after that.
2. It evaluates a = f(xs[i]) and b = f(-xs[i]), where xs[i] = rho^(2^i) and rho is a Fiat-Shamir challenge (a challenge derived by hashing, standing in for a value an interactive verifier would have chosen at random). It checks these against the prover-supplied rounds[i].a and .b.
3. It reads the prover-supplied next_coeffs and checks commit(next_coeffs) == fold_commitments[i].
4. It checks the fold equation fold_value(a, b, bit_i, xs[i]) == next_value, where next_value is rounds[i+1].a, or the final claimed value in the last round.

fold_value(a, b, bit, x) = (a + b) / 2        if bit = 0
fold_value(a, b, bit, x) = (a - b) / (2 * x)  if bit = 1

That is the even/odd split f(x) = f_even(x^2) + x * f_odd(x^2) read at x and -x. At the very end the verifier checks eval_poly(final_coeffs, xs[n]) == claimed.

What a folding proof is supposed to do, for a non-crypto reader

A polynomial commitment lets a prover publish a short fingerprint of a big polynomial and later convince a verifier of its value at a point without resending the whole thing. FRI and BaseFold do this by folding: each round combines the even-indexed and odd-indexed coefficients into a polynomial of half the degree, using a random challenge. After about log(degree) rounds the polynomial is a constant the verifier can check directly.

The security rests on one thing: each folded polynomial has to be provably the fold of the previous one, and the first one has to be the committed one. A sound verifier enforces that by opening the committed data at random points (Merkle-opened queries) and checking the fold relation there. If it skips that and only checks the rounds for internal consistency, the “proof” degenerates into a story the prover tells about polynomials nobody pinned down.

Finding the unsound step

Nothing forces next_coeffs to be the actual fold of the current polynomial. In a sound verifier the folded polynomial is tied to the committed one by queries into the committed oracle. Here the chain of trust breaks after the first round:

• The pinned commitment only bites in round 0, where coeffs must be the real vector.
• From round 1 on, coeffs is the previous round’s next_coeffs, which the prover chose. Its commitment is also prover-supplied (fold_commitments[i]), so the check in step 3 compares the prover’s polynomial against the prover’s own hash of it.
• The only thing linking one round to the next is a single evaluation: next_coeffs(xs[i+1]) must equal fold_value(a, b, bit, xs[i]).

A second weakness makes it worse. rho is derived from the claim alone, not from the prover’s fold commitments, so the prover knows every challenge before choosing any intermediate polynomial. This is weak Fiat-Shamir: the transcript the challenge commits to leaves out exactly the values the prover gets to pick later.

So from round 1 onward I control both a_i = C_i(xs[i]) and b_i = C_i(-xs[i]), where C_i is my polynomial for that round. b_i is free, and fold_value can be driven to any target by solving for it:

• bit = 0: b = 2*target - a
• bit = 1: b = a - 2*target*x

I re-derived both from the definitions and confirmed them over random field elements: (a+b)/2 = target gives b = 2*target - a, and (a-b)/(2x) = target gives b = a - 2*target*x. Two points determine a line, and xs[i] is nonzero, so a degree-1 polynomial is enough for each intermediate round.

Why a degree-1 polynomial per round is enough

Each intermediate C_i has to satisfy two independent point constraints: C_i(xs[i]) = t_i, forced by the previous fold, and C_i(-xs[i]) = b_i, which I choose. Two points through two distinct abscissae (+xs[i] and -xs[i], distinct because xs[i] != 0) have a unique degree-1 solution, so the line always exists. An honest prover would be carrying a polynomial of degree 8191 / 2^i into round i; the verifier never checks the degree halves, only that next_coeffs is non-empty, so these tiny lines sail through where a real fold would not need to.

Building the forgery

For report 271, field payout_authorized (column 3, so the point’s bits end in 1, 1), claimed value 1. The 13-bit point is bits_le(271, 11) ++ bits_le(3, 2). Since 271 = 1 + 2 + 4 + 8 + 256, its low 11 bits little-endian are [1,1,1,1,0,0,0,0,1,0,0], and column 3 adds [1,1]:

point_bits = [1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1]

(I recomputed this directly; it is the per-round bit_i the fold reads.) The forged proof is then built round by round:

1. Round 0 uses the real vector V. Compute the honest a_0 = V(xs[0]) and b_0 = V(-xs[0]), which fixes the first target t_1 = fold_value(a_0, b_0, bit_0, xs[0]).
2. For rounds 1 to n-2, take C_i as the line through (xs[i], t_i) and (-xs[i], 0), so b_i = 0, and carry t_{i+1} = fold_value(t_i, 0, bit_i, xs[i]).
3. In the last round solve for b_{n-1} so that fold_value(t_{n-1}, b_{n-1}, bit_{n-1}, xs[n-1]) = 1, and take C_{n-1} through (xs[n-1], t_{n-1}) and (-xs[n-1], b_{n-1}).
4. The final polynomial is the constant [1], so eval_poly(final_coeffs, xs[n]) = 1 = claimed.
5. Each round’s a and b are the real evaluations of C_i, and fold_commitments[i] = commit(C_{i+1}).

Only round 0 ever touches the real data, and it constrains t_1 alone, which places no constraint on claimed. Everything downstream is mine to set, so claimed = 1 goes through for a field the honest data says is 0.

The solver reimplemented the verifier’s field arithmetic (rather than running the downloaded verifier.py), built the proof, and wrote forged_proof.json.

Submitting the receipt

B=<instance base URL>
curl -sk "$B/api/replay/verifier.py" -o verifier.py        # the published verifier
# plus the manifest, the 8 shards, and reports.json from /api/...

python -I solve_bh.py        # builds the forgery, writes forged_proof.json

curl -sk -X POST "$B/vault" --data-urlencode "proof@forged_proof.json"

The vault answered accepted and showed the sealed attachment, which held the flag (FortID{BU6_B0uN7Y_H0UN73R5...).

Fix

The folded polynomial has to be checked against the committed one, for example with Merkle-opened queries into the committed oracle, so each round’s fold relation is verified at points the prover did not get to choose. The fold challenge has to be bound to each commitment through Fiat-Shamir so the prover cannot pick polynomials after seeing it. And the verifier should enforce that the degree halves each round, which alone would have rejected the degree-1 lines this forgery leans on.

Fiat-Shamir has to cover the whole transcript

Fiat-Shamir turns an interactive proof into a non-interactive one by deriving the “random” challenges from a hash of everything said so far. The rule is that the hash input must include every value the prover commits to before the challenge is used. Here rho was hashed from the claim only, so the prover could read off every xs[i] and then craft all the intermediate commitments to fit. Folding each commitment into the hash that produces the next challenge removes that freedom, because any change to a chosen polynomial changes the challenge it has to satisfy.