slow-gold - LA CTF 2026 Crypto Writeup

Category: Crypto / Zero-Knowledge Proofs Difficulty: Hard Points: 322 Solves: 19 Flag: lactf{1_h0p3_y0u_l1v3_th1s_0ne_t0_th3_fullest} Solved by: Smothy @ 0xN1umb

"Delta equals zero? More like delta equals hero."

Challenge Description

The scenes of life are gold, so let's take it slow. After all, how often is it that you get a second chance?

nc chall.lac.tf 31183

Author: freed

A Zero-Knowledge proof challenge built on top of a modified emp-zk toolkit. The server (prover) holds two secret arrays that are permutations of each other, and proves this fact using a Schwartz-Zippel polynomial identity check. Our job as the verifier? Guess the actual secret values. Sounds impossible... unless the ZK system has a deliberate backdoor.

TL;DR

The challenge uses a modified emp-zk (Efficient Multi-Party Zero-Knowledge) toolkit where the correctness check is intentionally weakened to only verify one gate instead of all gates. By forcing our verifier's MAC key delta = 0, we make all authentication checks pass trivially while leaking linear equations in the secret values through the correctness check output V. Collect 12 connections, solve a linear system over GF(2^61-1), find polynomial roots via Cantor-Zassenhaus, recover all 10 secret values, submit, get flag. ZK proofs go brrr.

Initial Recon

The challenge provides a full emp-zk toolkit distribution with source code. Key files:

The server (chall.cpp) runs as the prover (ALICE) holding two secret arrays vec1 and vec2 of 10 elements each over the Mersenne prime field GF(p) where p = 2^61 - 1. It proves they're permutations using the Schwartz-Zippel lemma:

If the arrays are permutations, the polynomials are identical, so this holds for any X. The verifier (us, BOB) picks X, the protocol runs, and then we must guess all 10 values of vec1 to get the flag.

In a properly implemented ZK system, we'd learn nothing about the secret values. But this isn't a proper implementation...

Step 1: Finding the Vulnerability

The emp-zk toolkit uses IT-MACs (Information-Theoretic Message Authentication Codes) for all values:

where delta is the verifier's global secret key. The correctness of all multiplications is verified through a batched check using random "chi" coefficients generated by uni_hash_coeff_gen.

Here's where it gets spicy. In the bool version of ostriple.h, the chi coefficients are generated for ALL gates:

uni_hash_coeff_gen(chi, seed, task_n);  // bool version: checks ALL gates

But in the arith version (which our challenge uses):

uni_hash_coeff_gen(chi, seed, 1);  // arith version: generates only 1 coefficient!

And the loop that performs the check:

for (uint32_t i = start + task_n - 1, k = 0; i < start + task_n; ++i, ++k)

This only iterates once, checking only gate 19 (the very last multiplication gate). Gates 0-18 are completely unchecked. This is the intentional vulnerability the challenge author (freed) planted.

Step 2: The Delta=0 Attack

The IT-MAC system relies on delta being a secret random value. But as the verifier, we control delta. What happens if we set delta = 0?

With delta = 0:

• All VOLE correlations become trivial (MAC = key regardless of value)
• The prover's values are accepted without real verification
• But the correctness check value V still contains useful information!

We modified the delta_gen() function:

void delta_gen() {
    delta = 0;  // Force delta to zero
}

Step 3: Mathematical Formulation

The correctness check for gate 19 computes:

Since delta=0, the verifier sees: V_raw before it gets multiplied by delta (which would zero it out). We intercept V_raw before that happens.

Gate 19 is the last step of acc2 = acc2 * (array2[9] + X), which means:

• value_a = accumulated product of (b_0+X)(b_1+X)...(b_8+X) = Q8(X)
• value_b = b_9 + X
• value_c = final accumulated product (all 10 terms)

The relationship becomes:

where ka, kb, kc are the verifier's keys (known to us!) and Q8(X) = (b_0+X)(b_1+X)...(b_8+X).

Expanding Q8 using elementary symmetric polynomials:

This gives us 10 unknowns (e1 through e9, plus b9), and each connection with a different X value gives us 1 linear equation. We need at least 10 equations to solve the system!

Step 4: Data Collection

We built a modified client (solve.cpp) that:

1. Connects as BOB (verifier) with delta=0
2. Sends a chosen evaluation point X
3. Runs the ZK protocol (all checks pass trivially)
4. Captures V_raw, chi_seed, and gate keys ka, kb, kc from stderr

We collected 12 data points (X=1 through X=12) from the remote server:

Each connection takes about 7-10 seconds for the VOLE setup. All 12 completed successfully - beautiful.

Step 5: Solving the Linear System

With 12 equations and 10 unknowns over GF(2^61-1), we have an overdetermined system. Gaussian elimination makes quick work of it:

P = (1 << 61) - 1  # Mersenne prime

# For each data point, build: V/chi + kc - X*ka = kb*Q8 + ka*b9
# Expand Q8 = X^9 + e1*X^8 + ... + e9
# Rearrange into: sum(coeffs * unknowns) = known_value

This recovered:

• Elementary symmetric polynomials e1 through e9
• The value b9 directly

Step 6: Root Finding with Cantor-Zassenhaus

The symmetric polynomials define a degree-9 polynomial whose roots are -(b_0), -(b_1), ..., -(b_8):

We used the Cantor-Zassenhaus algorithm for factoring polynomials over finite fields:

1. Pick random r, compute gcd(f(t), (t+r)^((p-1)/2) - 1)
2. This splits f into roughly equal-degree factors
3. Recurse until all roots found

All 9 roots recovered, negated to get b_0 through b_8, combined with b_9:

The Flag

We sent these 10 values (sorted) back to the server as our guess, and...

"I hope you live this one to the fullest" - challenge description vibes confirmed.

The Solve Script

#!/usr/bin/env python3
"""slow-gold solver - Smothy @ 0xN1umb"""
import re, sys, os, subprocess, time, random

P = (1 << 61) - 1  # Mersenne prime 2^61 - 1

def mod(x): return x % P
def add(a, b): return (a + b) % P
def sub(a, b): return (a - b + P) % P
def mul(a, b): return (a * b) % P
def inv(a): return pow(a, P - 2, P)

def poly_eval(coeffs, x):
    result = 0
    for c in coeffs:
        result = add(mul(result, x), c)
    return result

def gaussian_elimination(matrix, rhs, n):
    m = len(matrix)
    aug = [list(matrix[i]) + [rhs[i]] for i in range(m)]
    for col in range(n):
        pivot = -1
        for row in range(col, m):
            if aug[row][col] != 0:
                pivot = row
                break
        if pivot == -1: continue
        aug[col], aug[pivot] = aug[pivot], aug[col]
        scale = inv(aug[col][col])
        for j in range(n+1):
            aug[col][j] = mul(aug[col][j], scale)
        for row in range(m):
            if row == col or aug[row][col] == 0: continue
            factor = aug[row][col]
            for j in range(n+1):
                aug[row][j] = sub(aug[row][j], mul(factor, aug[col][j]))
    return [aug[i][n] for i in range(n)]

def find_roots_poly(f):
    """Cantor-Zassenhaus over GF(p)"""
    while len(f) > 1 and f[0] == 0: f = f[1:]
    deg = len(f) - 1
    if deg == 0: return []
    if deg == 1: return [mul(sub(0, f[1]), inv(f[0]))]
    roots = []
    stack = [f]
    while stack:
        g = stack.pop()
        while len(g) > 1 and g[0] == 0: g = g[1:]
        dg = len(g) - 1
        if dg == 0: continue
        if dg == 1:
            roots.append(mul(sub(0, g[1]), inv(g[0])))
            continue
        for _ in range(200):
            r = random.randint(0, P - 1)
            h = poly_powmod([1, r], (P-1)//2, g)
            h[-1] = sub(h[-1], 1)
            d = poly_gcd(g[:], h[:])
            while len(d) > 1 and d[0] == 0: d = d[1:]
            dd = len(d) - 1
            if 0 < dd < dg:
                stack.append(d)
                stack.append(poly_div(g, d))
                break
    return roots

# Parse data, build linear system, solve, find roots
# Full implementation at: solve_remote.py

The key steps:

1. Modify ostriple.h: Force delta=0, print V_raw, chi_seed, gate keys
2. Build solve client: Modified verifier that collects data from 12 connections
3. Build linear system: Each (X, V, chi, ka, kb, kc) gives one equation in 10 unknowns
4. Gaussian elimination: Solve over GF(2^61-1) for symmetric polynomials + b9
5. Cantor-Zassenhaus: Factor degree-9 polynomial to recover remaining 9 values
6. Submit sorted values: Send all 10 values to server, receive flag

The Graveyard of Failed Attempts

1. First guess: {1,2,...,10} - We tried the obvious small values. Server said no. The actual values are huge random elements of GF(2^61-1).

2. Hostname resolution disaster - emp-tool's NetIO uses inet_addr() which only accepts IP addresses, not hostnames. chall.lac.tf caused an infinite connect loop. Had to resolve to 34.169.138.235 manually.

3. Binary hanging after guesses - When submitting wrong guesses (all zeros during testing), the server doesn't send the flag and the client blocks forever waiting for 46 bytes. Fixed by adding a data-collection-only mode.

4. Connection timeouts - The VOLE setup takes 7-10 seconds per connection. Initial 30-second timeout was too aggressive for some connections. Bumped to 5 minutes.

5. Understanding the gate structure - Spent a long time figuring out which gate corresponds to which multiplication. The server creates 20 AND gates (10 for acc1, 10 for acc2), and gate 19 is the last one in the acc2 chain.

Key Takeaways

1. ZK systems are only as secure as their implementation - The mathematical framework is sound, but weakening the correctness check from "all gates" to "one gate" creates a devastating information leak.

2. delta=0 is a verifier-side attack - The verifier controls delta. In a real system, a malicious verifier gains nothing because the ZK property protects the prover. But here, the weakened correctness check means the prover accidentally leaks secrets.

3. Schwartz-Zippel is powerful both ways - The same lemma that makes the permutation check work also enables our attack: evaluating the polynomial at multiple points lets us recover all coefficients.

4. IT-MACs with delta=0 - When the global key is zero, MAC = key for any value. All consistency checks pass trivially, but the algebraic structure of the correctness check still carries information.

5. Cantor-Zassenhaus algorithm - Essential tool for root-finding over large finite fields where brute force is impossible (p = 2^61 - 1 has ~2.3 * 10^18 elements).

6. Read the source diff carefully - The vulnerability was hidden in a one-character change: task_n (all gates) vs 1 (one gate) in the chi coefficient generation. Classic CTF move.

Tools Used

• emp-zk toolkit (modified) - Zero-knowledge proof framework
• Python 3 - Linear algebra, polynomial arithmetic, Cantor-Zassenhaus
• CMake/GCC - Building the modified client
• matplotlib - Screenshot generation
• Way too much caffeine
• An unreasonable amount of staring at finite field arithmetic

Writeup by Smothy from 0xN1umb team. ZK proofs? More like ZK oofs. GG freed, beautiful challenge.