Writeup: Toxic Waste - CyberEdu CTF (Crypto)

Overview

This challenge implements a KZG Polynomial Commitment scheme on a supersingular elliptic curve, but with a shuffled setup. We must prove polynomial evaluations at 100 random points such that the Lagrange interpolation of the (z, y) pairs yields a polynomial of degree > 40. In other words, we need to forge KZG opening proofs.

The key insight: although the SRS (Structured Reference String) is shuffled, we can recover its ordering using the Weil pairing with a distortion map on the supersingular curve. Once unshuffled, we factor the public polynomial to extract the toxic waste (alpha) and forge all proofs.

Source Code Analysis

Curve Setup

p = 6 * getPrime(512) - 1         # p ≡ 2 mod 3 -> supersingular!
E = EllipticCurve(GF(p), [0, 1])  # y^2 = x^3 + 1, j-invariant = 0
G1 = E.gens()[0] * 6
o = G1.order()                     # o = (p+1)/6, a ~512-bit prime

The curve y^2 = x^3 + 1 with p ≡ 2 mod 3 is a supersingular curve with #E(GF(p)) = p + 1. This is crucial because it means the embedding degree is 2 -- the Weil pairing produces non-trivial elements in GF(p^2).

The Setup Function -- Core Vulnerability

def setup(deg=40):
    alpha = secrets.randbelow(o)    # the "toxic waste" -- secret!
    vec = [G1, alpha*G1, alpha^2*G1, ..., alpha^39*G1]  # SRS
    Pol = [random coefficients]

    # Ensures Pol(alpha) = 0
    PP = sum(alpha^i * Pol[i] for i in range(deg))
    Pol[0] -= PP

    Pub = [(vec[i], Pol[i]) for i in range(deg)]

    # "Whoops!" - Fisher-Yates shuffle
    for i in range(len(Pub)-1, 0, -1):
        j = secrets.randbelow(i+1)
        Pub[j], Pub[i] = Pub[i], Pub[j]

    return Pub, G2 * alpha

The server gives us:

• 40 pairs (P_i, c_i) where P_i = alpha^sigma(i) * G1 and c_i = Pol[sigma(i)] for an unknown permutation sigma
• G2alpha = alpha * G2 (used in the pairing verification)

Critical constraint: sum(c_i * alpha^sigma(i)) = 0 mod o, meaning alpha is a root of the polynomial Pol(x).

KZG Verification

# pair(pi, G2alpha - z*G2) == pair(C - y*G1, G2)
assert pi.weil_pairing(G2alpha - z*G2, o) == (C - y*G1).weil_pairing(G2, o)

Win Condition

pol = R.lagrange_polynomial(pairs)  # Interpolation from 100 (z, y) pairs
if pol.degree() > 40:               # Degree must be > 40
    print(open("flag.txt").read())

We must pass all 100 pairing checks, but the resulting interpolation must have degree > 40.

Attack Strategy

The attack consists of three stages:

Stage 1: Unshuffle the SRS with a Distortion Map

On the supersingular curve y^2 = x^3 + 1, there exists a distortion map:

phi(x, y) = (omega * x, y)

where omega is a primitive cube root of unity in GF(p^2) satisfying omega^2 + omega + 1 = 0.

This map sends points from E(GF(p)) to a different subgroup in E(GF(p^2)), making the Weil pairing produce non-trivial values.

Key property: For two points P_i = alpha^(s_i) * G1 and P_j = alpha^(s_j) * G1:

e(P_i, phi(P_j)) = g^(alpha^(s_i + s_j))

where g = e(G1, phi(G1)).

This means: two pairs (i,j) and (k,l) yield the same pairing value if and only if s_i + s_j = s_k + s_l.

We build a 40x40 pairing matrix:

w = Fp2.gen()  # omega: w^2 + w + 1 = 0

def distortion_map(P):
    x, y = P.xy()
    return E2(w * x, y)

M = [[e(P_i, phi(P_j)) for j in range(40)] for i in range(40)]

Finding sigma = 0

We group matrix entries by their value. Singleton groups (containing only 1 pair) are highly informative:

From these 4 singletons, we identify the points with sigma = 0 and sigma = 1 by finding which diagonal singleton connects to an off-diagonal singleton and successfully builds a complete chain of all 40 elements.

Building the Ordering Chain

Once we know the indices for sigma = 0 (idx_0) and sigma = 1 (idx_1), we build a chain:

# ref_col: M[i][idx_0] = g^(alpha^sigma(i)) -> maps value to index
ref_col = {M[i][idx_0]: i for i in range(40)}

# For current point with sigma = s:
# M[current][idx_1] = g^(alpha^(s + 1))
# Look it up in ref_col -> gives the index with sigma = s + 1
current = idx_1
for s in range(2, 40):
    target = M[current][idx_1]
    next_idx = ref_col[target]
    sigma[next_idx] = s
    current = next_idx

This works because M[current][idx_1] = g^(alpha^(s+1)) and M[next][idx_0] = g^(alpha^sigma(next)). If the values match, then sigma(next) = s + 1.

Stage 2: Recovering Alpha

With the permutation sigma known, we reconstruct the polynomial:

Pol(x) = sum(ordered_coeffs[i] * x^i for i in range(40))

We know that Pol(alpha) = 0 by construction in setup. So alpha is a root of Pol(x). We factor it over GF(o):

roots = Pol.roots()  # Factorization over GF(o)
for root, _ in roots:
    if root * G1 == alpha_G1:  # Verify against SRS
        alpha = root
        break

A degree-39 polynomial has at most 39 roots, and we verify each with a cheap elliptic curve operation.

Stage 3: Forging KZG Openings

With alpha in hand, we can forge any polynomial evaluation proof.

We commit C = G1 (representing the constant polynomial f(x) = 1):

C = G1  # commitment: f(x) = 1

For each challenge z, we send a random y (not f(z) = 1) with the forged proof:

# pi = (1 - y) / (alpha - z) * G1
scalar = (1 - y) * pow(alpha - z, -1, o) % o
pi = scalar * G1

Why does this pass verification? The pairing check:

LHS = e(pi, (alpha - z) * G2)
    = e(scalar * G1, (alpha - z) * G2)
    = e(G1, G2)^(scalar * (alpha - z))
    = e(G1, G2)^(1 - y)

RHS = e(C - y * G1, G2)
    = e((1 - y) * G1, G2)
    = e(G1, G2)^(1 - y)

LHS == RHS

Since y is chosen randomly for each query, the 100 pairs (z, y) don't lie on any polynomial of degree <= 40. Lagrange interpolation yields degree 99 > 40.

Solver

import socket, time, random, re
from collections import defaultdict

# === Connection & Parsing ===
s = socket.socket()
s.settimeout(120)
s.connect(('TARGET_HOST', TARGET_PORT))

p = int(recvline(s).strip().split(' = ')[1])
pub_raw = eval(recvline(s).strip()[len("pub = "):])

# === Curve Setup (SageMath) ===
E = EllipticCurve(GF(p), [0, 1])
Fp2 = GF(p^2, 'x', modulus=[1, 1, 1])
E2 = EllipticCurve(Fp2, [0, 1])
w = Fp2.gen()  # primitive cube root: w^2 + w + 1 = 0

pub_pts = [E(pt[0], pt[1]) for (pt, c) in pub_raw]
pub_coeffs = [int(c) for (pt, c) in pub_raw]
o = pub_pts[0].order()
P_e2 = [E2(P) for P in pub_pts]

# === Stage 1: Unshuffle via Pairing Matrix ===
phi_pts = [E2(w * P.xy()[0], P.xy()[1]) for P in P_e2]

M = [[P_e2[i].weil_pairing(phi_pts[j], o)
      for j in range(40)] for i in range(40)]

# Find singletons -> identify sigma=0 and sigma=1
val_to_pairs = defaultdict(list)
for i in range(40):
    for j in range(i, 40):
        val_to_pairs[M[i][j]].append((i, j))

singletons = {v: ps for v, ps in val_to_pairs.items() if len(ps) == 1}
diag_sing = [(v, ps[0]) for v, ps in singletons.items()
             if ps[0][0] == ps[0][1]]
offdiag_sing = [(v, ps[0]) for v, ps in singletons.items()
                if ps[0][0] != ps[0][1]]

# Try each candidate, build chain
for _, (cand, _) in diag_sing:
    ref = {M[i][cand]: i for i in range(40)}
    for _, (a, b) in offdiag_sing:
        c1 = b if a == cand else (a if b == cand else None)
        if c1 is None: continue
        try:
            sigma = {cand: 0, c1: 1}
            cur = c1
            for ss in range(2, 40):
                nxt = ref[M[cur][c1]]
                if nxt in sigma: raise KeyError
                sigma[nxt] = ss
                cur = nxt
            if len(sigma) == 40:
                idx_0, idx_1 = cand, c1
                break
        except KeyError: continue

# === Stage 2: Recover Alpha ===
inv_sigma = {v: k for k, v in sigma.items()}
ordered_coeffs = [pub_coeffs[inv_sigma[s]] for s in range(40)]

R = PolynomialRing(GF(o), 'x')
Pol = sum(R.gen()^i * c for i, c in enumerate(ordered_coeffs))
roots = Pol.roots()

G1_pt = pub_pts[inv_sigma[0]]
for root, _ in roots:
    if int(root) != 0 and int(root) * G1_pt == pub_pts[inv_sigma[1]]:
        alpha = int(root)
        break

# === Stage 3: Forge KZG Openings ===
# Commit C = G1
recvuntil(s, "C = ")
sendline(s, f"{G1_pt.xy()[0]},{G1_pt.xy()[1]}")

o_int = int(o)
for i in range(100):
    buf = recvuntil(s, "y = ")
    z = int(re.search(r'z\s*=\s*(\d+)', buf).group(1))

    y = random.randint(2, o_int - 1)  # random y, not f(z)
    scalar = ((1 - y) * pow((alpha - z) % o_int, o_int - 2, o_int)) % o_int
    pi_pt = int(scalar) * G1_pt

    sendline(s, str(y))
    recvuntil(s, "pi = ")
    sendline(s, f"{pi_pt.xy()[0]},{pi_pt.xy()[1]}")

# Flag!
print(s.recv(4096).decode())

Output

[*] Computing 40x40 pairing matrix...
[+] Successfully unshuffled all 40 SRS points!
[*] Factoring Pol(x) to find alpha...
[+] Found alpha!
[+] Alpha verified!
[*] Completed 100/100 queries
WHAT!
flag{Alph4_h4s_t0_b3_1nc1n3r4t3d_947a1a1e8895d3d483ab}

Takeaways

1. Toxic waste must be destroyed. The flag itself says it: "Alpha has to be incinerated." In real KZG deployments, the secret parameter alpha must be erased after setup through a trusted setup ceremony (e.g., Powers of Tau).
2. Supersingular curves have distortion maps. For y^2 = x^3 + 1 with j = 0, the map phi(x,y) = (omega*x, y) enables non-trivial Weil pairings between points in the same subgroup -- something impossible on ordinary curves.
3. Shuffling the SRS is not enough. Although the ordering of the SRS points is scrambled, the underlying algebraic structure (multiplicative relations between points) remains intact and can be reconstructed via pairings.
4. KZG binding relies on alpha being secret. Once alpha is known, the entire scheme collapses – an attacker can open a commitment to any value at any point.