#【AIS3 Pre-Exam 2026 Writeup】Crypto - EasyZKP

Source first. There are only Python files, so checksec, gdb, glibc, and printf were not useful here. File layout came before any protocol guess.

rg --files -uu

The important files were:

shared/zkp.py
proof/app.py
verifier/chal.py
solve.py

shared/zkp.py had the proof logic.

def hash_suffix(flag, suffix):
    return hashlib.sha256(flag + suffix).digest()

def compute_proof_from_digest(digest, seed):
    value = 0
    for byte in digest:
        for offset in range(7, -1, -1):
            if (byte >> offset) & 1 == 0:
                raw_value = value + seed
                value = raw_value % N
            else:
                value = pow(value, seed, N)
    return value

So proof is based on:

sha256(flag || suffix)

Then it scans all 256 bits. A 0 adds seed. A 1 does exponentiation with seed.

At first I thought maybe the proof function itself had some direct algebra trick for random seed. That looked too hard. The challenge gives random seed in the real verification path, and without the digest there was no direct way to compute the answer.

The verifier has two menu options.

if choice == "1":
    option_oracle()
elif choice == "2":
    option_challenge()

option_challenge() is the final gate. It repeats 16 rounds:

shown_nonce, server_part_b64 = build_nonce()
suffix = decode_suffix(shown_nonce) + decode_suffix(server_part_b64)
seed = secrets.randbelow(N - 2) + 2
expected = compute_proof(FLAG, suffix, seed)

The server gives server_part, I give shown_nonce, and it checks the proof. No binary mitigation here. The boundary is the Docker service split: verifier talks to internal prover.

option_oracle() looked more interesting. It lets me ask the internal prover for a proof, and also flip SHA-256 digest bits.

def fetch_proof(user_part_b64, server_part_b64, seed, bit_flip_indices=None):
    flip_query = ""
    if bit_flip_indices is not None:
        for index in bit_flip_indices:
            flip_query += f"&f={index}"
    url = f"{PROVER_URL}?p={server_part_b64}{flip_query}&d={user_part_b64}&s={seed}"

This line was suspicious. user_part_b64 is put into the URL without URL encoding.

My first small test was about base64 parsing. If I put &s=... after some base64 text, the HTTP query parser sees another parameter. The prover side uses:

query = parse_qs(parsed.query, keep_blank_values=True)
seed = int(query["s"][0])

When two s parameters exist, it takes the first one. So I can send:

<valid_base64>&s=<my_seed>

and control the prover seed.

Same idea also works for f.

<valid_base64>&s=<my_seed>&f=0&f=1&...

I kept this for the 128-query limit.

Next problem: choose a good seed. The modulus was:

N = 1371086445846712667727718527036585861739497962228620061686456237722902428356146756731186939

I tried factoring it. sympy.factorint(..., limit=1000000) did not split it. FactorDB did.

python3 - <<'PY'
import urllib.request
N = "1371086445846712667727718527036585861739497962228620061686456237722902428356146756731186939"
print(urllib.request.urlopen("http://factordb.com/api?query=" + N).read().decode())
PY

Result:

p = 1062991560384192946446466724143851978243633013
q = 1289837564986090927380812179078126226643568303

So:

LAM = lcm(p - 1, q - 1)

With seed = lambda(N), exponentiation becomes useful. For invertible values:

x ^ lambda(N) = 1 mod N

The proof state gets a simple shape:

0-bit: value = value + lambda(N)
1-bit: value = value ^ lambda(N)

If a 1 happens after the state is non-zero, it resets the state to 1. After that, trailing zero bits make:

1 + k * lambda(N)

If there was no such reset, the result is:

k * lambda(N)

So the output tells me where the last useful 1 bit is. I was not sure it would be clean for every state, so I wrote a decoder and tested random digests locally.

def decode_lambda_output(value):
    hits = []
    for k in range(257):
        if (k * LAM) % N == value:
            hits.append(("linear", k))
        if (1 + k * LAM) % N == value:
            hits.append(("reset", k))
    if len(hits) != 1:
        raise ValueError(...)
    return hits[0]

No ambiguity showed up in my local checks. The decoder looked usable.

Now the oracle can recover one digest.

Flow:

fix suffix S
inject seed = lambda(N)
ask proof
decode where the last 1 bit is
flip that bit to 0
repeat

When the decoder says reset, k, the bit position is:

255 - k

Flip it. Then ask again. This peels 1 bits from right to left.

When the decoder says linear, k, the remaining unknown prefix is only leading ones followed by zeros. At that point the digest is known.

The limit was annoying:

SUBORACLE_LIMIT = 128

A random 256-bit digest has about 128 one bits. Direct mode often works, but not always. I added a fallback mode by injecting all f parameters at the start:

&f=0&f=1&...&f=255

Those injected flips happen inside the HTTP request and do not consume the verifier flip quota. This gives the complement digest. Recover it and invert bits back.

My run solved in direct mode:

[+] recovered digest via direct mode in 120 proof queries
[+] suffix length = 53
[+] digest = f5cbe358f564933e88f9c96ffa2309650c504063fa8ea431a8113ac9abe41472

At this point I had:

S
sha256(flag || S)

I still did not know flag. Direct brute force of flag was not a plan. The hash is SHA-256 and the flag is not small enough.

I went back to option_challenge(). The verifier computes:

sha256(flag || shown_nonce || server_part)

That matches the SHA-256 length extension shape. If I know:

sha256(flag || S)
len(flag || S)

then I can compute:

sha256(flag || S || padding || server_part)

So in challenge mode, I send:

shown_nonce = base64(S || sha256_padding(len(flag) + len(S)))

The server appends its server_part, and the message becomes the one I can extend.

The only missing value is len(flag). I tried it from 1 to 128. Wrong length only returns wrong and goes back to the menu, so it is cheap.

The correct length was 62. After that, every round uses the same recovered digest, extends it with the new server suffix, computes compute_proof_from_digest(), and sends the proof.

Full exploit script:

#!/usr/bin/env python3
import base64
import os
import struct
from math import gcd, lcm

from pwn import context, remote

from shared.zkp import N, compute_proof_from_digest


HOST = "chals1.ais3.org"
PORT = 48765

P = 1062991560384192946446466724143851978243633013
Q = 1289837564986090927380812179078126226643568303
LAM = lcm(P - 1, Q - 1)

assert P * Q == N
assert gcd(LAM, N) == 1
assert all(gcd((k * LAM) % N, N) == 1 for k in range(1, 257))
assert all(gcd((1 + k * LAM) % N, N) == 1 for k in range(257))


K = [
    0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5,
    0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5,
    0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3,
    0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174,
    0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC,
    0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA,
    0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7,
    0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967,
    0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13,
    0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,
    0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3,
    0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070,
    0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5,
    0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3,
    0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208,
    0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2,
]


def b64e(raw):
    return base64.urlsafe_b64encode(raw).decode()


def b64d(data):
    return base64.urlsafe_b64decode(data.encode())


def bits_to_bytes(bits):
    return bytes(
        sum(bits[i + j] << (7 - j) for j in range(8))
        for i in range(0, 256, 8)
    )


def decode_lambda_output(value):
    hits = []
    for k in range(257):
        if (k * LAM) % N == value:
            hits.append(("linear", k))
        if (1 + k * LAM) % N == value:
            hits.append(("reset", k))
    if len(hits) != 1:
        raise ValueError(f"ambiguous lambda-state output: {value} -> {hits}")
    return hits[0]


def recv_menu(io):
    io.recvuntil(b">\n")


def recover_digest_once(invert):
    io = remote(HOST, PORT)
    recv_menu(io)
    io.sendline(b"1")
    io.recvuntil(b"server suffix = ")
    server_b64 = io.recvline().strip().decode()
    server_part = b64d(server_b64)
    io.recvuntil(b"nonce:\n")

    user_part = b"ais3-easyzkp:" + os.urandom(8)
    user_b64 = b64e(user_part)
    injected = user_b64 + f"&s={LAM}"
    if invert:
        injected += "".join(f"&f={i}" for i in range(256))
    io.sendline(injected.encode())

    found_ones = []
    flipped = set()
    for query_index in range(128):
        recv_menu(io)
        io.sendline(b"1")
        io.recvuntil(b"proof = ")
        proof = int(io.recvline().strip())
        kind, k = decode_lambda_output(proof)
        if kind == "linear":
            leading_ones = 256 - k
            bits = [0] * 256
            for index in range(leading_ones):
                bits[index] = 1
            for index in found_ones:
                bits[index] = 1
            if invert:
                bits = [bit ^ 1 for bit in bits]
            io.close()
            return user_part + server_part, bits_to_bytes(bits), query_index + 1

        position = 255 - k
        if position in flipped:
            io.close()
            raise ValueError(f"repeated flip position {position}")
        found_ones.append(position)
        flipped.add(position)

        recv_menu(io)
        io.sendline(b"2")
        io.recvuntil(b"bit index:\n")
        io.sendline(str(position).encode())
        io.recvuntil(b"bit flipped\n")

    io.close()
    return None, None, 128


def recover_digest():
    attempt = 0
    while True:
        attempt += 1
        for invert in (False, True):
            suffix, digest, queries = recover_digest_once(invert)
            mode = "complement" if invert else "direct"
            if digest is not None:
                print(f"[+] recovered digest via {mode} mode in {queries} proof queries")
                print(f"[+] suffix length = {len(suffix)}, digest = {digest.hex()}")
                return suffix, digest
            print(f"[-] {mode} mode attempt {attempt} exhausted 128 proof queries")


def sha256_padding(message_len):
    zero_len = (56 - (message_len + 1) % 64) % 64
    return b"\x80" + b"\x00" * zero_len + struct.pack(">Q", message_len * 8)


def rotr(value, count):
    return ((value >> count) | (value << (32 - count))) & 0xFFFFFFFF


def sha256_compress(state, block):
    w = list(struct.unpack(">16I", block))
    for index in range(16, 64):
        s0 = rotr(w[index - 15], 7) ^ rotr(w[index - 15], 18) ^ (w[index - 15] >> 3)
        s1 = rotr(w[index - 2], 17) ^ rotr(w[index - 2], 19) ^ (w[index - 2] >> 10)
        w.append((w[index - 16] + s0 + w[index - 7] + s1) & 0xFFFFFFFF)

    a, b, c, d, e, f, g, h = state
    for index in range(64):
        s1 = rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25)
        ch = (e & f) ^ (~e & g)
        temp1 = (h + s1 + ch + K[index] + w[index]) & 0xFFFFFFFF
        s0 = rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22)
        maj = (a & b) ^ (a & c) ^ (b & c)
        temp2 = (s0 + maj) & 0xFFFFFFFF
        h, g, f, e, d, c, b, a = (
            g,
            f,
            e,
            (d + temp1) & 0xFFFFFFFF,
            c,
            b,
            a,
            (temp1 + temp2) & 0xFFFFFFFF,
        )

    return [
        (state[0] + a) & 0xFFFFFFFF,
        (state[1] + b) & 0xFFFFFFFF,
        (state[2] + c) & 0xFFFFFFFF,
        (state[3] + d) & 0xFFFFFFFF,
        (state[4] + e) & 0xFFFFFFFF,
        (state[5] + f) & 0xFFFFFFFF,
        (state[6] + g) & 0xFFFFFFFF,
        (state[7] + h) & 0xFFFFFFFF,
    ]


def sha256_extend(digest, original_len, extra):
    state = list(struct.unpack(">8I", digest))
    processed_len = original_len + len(sha256_padding(original_len))
    payload = extra + sha256_padding(processed_len + len(extra))
    assert len(payload) % 64 == 0
    for offset in range(0, len(payload), 64):
        state = sha256_compress(state, payload[offset:offset + 64])
    return struct.pack(">8I", *state)


def solve_challenge(suffix, digest, min_len=1, max_len=128):
    io = remote(HOST, PORT)
    for flag_len in range(min_len, max_len + 1):
        print(f"[*] trying flag length {flag_len}")
        recv_menu(io)
        io.sendline(b"2")
        line = io.recvline()
        if not line.startswith(b"pass "):
            raise RuntimeError(line)

        ok = True
        for round_index in range(1, 17):
            io.recvuntil(b"server suffix = ")
            server_b64 = io.recvline().strip().decode()
            server_part = b64d(server_b64)
            io.recvuntil(b"nonce:\n")

            glue = sha256_padding(flag_len + len(suffix))
            shown_nonce = b64e(suffix + glue)
            io.sendline(shown_nonce.encode())

            io.recvuntil(b"seed = ")
            seed = int(io.recvline().strip())
            io.recvuntil(b"proof:\n")

            extended = sha256_extend(digest, flag_len + len(suffix), server_part)
            proof = compute_proof_from_digest(extended, seed)
            io.sendline(str(proof).encode())

            result = io.recvline().strip()
            if result != b"ok":
                print(f"[-] length {flag_len} failed at round {round_index}: {result.decode(errors='replace')}")
                ok = False
                break
            print(f"[+] length {flag_len} round {round_index}/16 ok")

        if ok:
            flag = io.recvline().strip().decode()
            print(f"[+] flag = {flag}")
            io.close()
            return flag

    io.close()
    raise RuntimeError("flag length not found")


def main():
    context.log_level = "error"
    suffix, digest = recover_digest()
    solve_challenge(suffix, digest)


if __name__ == "__main__":
    main()

Run:

python3 solve.py

Output reached 16 rounds with flag length 62.

AIS3{simple_oracle_and_dramatic_injections_leading_forge_XDDD}