Fifteenminutes

Doua etape de cate 5 runde: recuperam n (si apoi si m) dintr-un RSA cu e=3 folosind relatii liniare ascunse si latice ortogonale cu LLL.

Sumar

Challenge-ul are 2 etape, fiecare cu 5 runde:

  1. etapa signatures: trebuie gasit nn
  2. etapa encryption: trebuie gasite nn si mm

Serverul raspunde la query-uri de forma resi=(aim+bi)zp mod nres_i = (a_i m + b_i)^{zp} \bmod n, unde la fiecare query ai,bi<2100a_i, b_i < 2^{100} sunt random, iar mm si nn raman fixe pe runda.

Ideea atacului:

  • folosim relatii liniare ascunse intre multe esantioane
  • extragem vectori ortogonali cu LLL pe un lattice de forma [I∣Y][I \mid Y]
  • obtinem multipli de nn, apoi facem gcd
  • in etapa 2 reconstruim subspatiul cubic util, apoi recuperam aa, bb, nn, mm

Dovada rezolvarii

Date importante din main.py:

  • bits = 1500, deci n=pqn = pq are aprox 3000 biti
  • k = 3, deci e=3e = 3
  • se impune p % 3 != 1 si q % 3 != 1
  • maxim 50 query-uri pe runda
  • etapa 1 cere nn, etapa 2 cere nn si mm

Conditia p % 3 != 1 garanteaza practic ca gcd⁡(3,φ(n))=1\gcd(3, \varphi(n)) = 1, deci exista d=3−1 mod φ(n)d = 3^{-1} \bmod \varphi(n).

Pentru o runda cu tt query-uri notam vectorii A=(ai)A = (a_i), B=(bi)B = (b_i), K=(ki)K = (k_i), A3=(ai3)A3 = (a_i^3), A2B=(3ai2bi)A2B = (3 a_i^2 b_i), AB2=(3aibi2)AB2 = (3 a_i b_i^2), B3=(bi3)B3 = (b_i^3).

Etapa 1

Serverul da si=(aim+bi)d mod ns_i = (a_i m + b_i)^d \bmod n. Ridicam la puterea 3:

yi=si3=aim+bi+kiny_i = s_i^3 = a_i m + b_i + k_i n

Pe vectori: Y=mA+B+nKY = mA + B + nK, deci YY sta intr-un subspatiu ascuns de dimensiune 3.

Latice ortogonale. Construim M=[ It∣22000Y ]M = [\,I_t \mid 2^{2000} Y\,]. Un vector de forma (v,22000⟨v,Y⟩)(v, 2^{2000}\langle v, Y\rangle) este scurt cand ⟨v,Y⟩=0\langle v, Y\rangle = 0. LLL intoarce astfel multi vectori ortogonali pe YY. Daca ww e ortogonal pe AA si BB, atunci ⟨w,Y⟩=n⟨w,K⟩\langle w, Y\rangle = n\langle w, K\rangle, deci ⟨w,Y⟩\langle w, Y\rangle este multiplu de nn:

n=gcd⁡( ∣⟨w1,Y⟩∣, ∣⟨w2,Y⟩∣, …)n = \gcd\big(\,|\langle w_1, Y\rangle|,\ |\langle w_2, Y\rangle|,\ \dots\big)

Practic: colectam 40 query-uri, calculam yi=si3y_i = s_i^3, rulam atacul ortogonal, trimitem nn. Aceasta etapa trece stabil 5/5 runde.

Etapa 2

Serverul da ci=(aim+bi)3 mod nc_i = (a_i m + b_i)^3 \bmod n. Ridicare in Z\mathbb{Z}:

ci=ai3m3+3ai2bim2+3aibi2m+bi3−kinc_i = a_i^3 m^3 + 3 a_i^2 b_i m^2 + 3 a_i b_i^2 m + b_i^3 - k_i n

Adica C=m3A3+m2A2B+m AB2+B3−nKC = m^3 A3 + m^2 A2B + m\, AB2 + B3 - nK. Pare 5D, dar direct nu este stabil. Folosim matrice ne-scalata M=[ It∣C ]M = [\,I_t \mid C\,], t=50t = 50. Dupa LLL luam primele t−4t - 4 randuri (fara ultima coloana), obtinem WW, apoi N=ker⁡(W)N = \ker(W). In practica iese dimensiune 4 si ker⁡(W)=span⁡(A3,A2B,AB2,K)\ker(W) = \operatorname{span}(A3, A2B, AB2, K). Deci B3B3 este eliminat, raman exact directiile utile plus KK.

Vectorii (A3i,A2Bi,AB2i)(A3_i, A2B_i, AB2_i) satisfac relatia A2Bi2=3 A3i AB2iA2B_i^2 = 3\, A3_i\, AB2_i. Folosim coloanele lui NN ca puncte proiective in P3\mathbb{P}^3, construim matricea monoamelor de grad 2, gasim cuadrica unica, apoi din matricea ei simetrica extragem o forma liniara λ\lambda. ker⁡(λ)\ker(\lambda) da subspatiul de dimensiune 3 dorit, iar U=span⁡(A3,A2B,AB2)U = \operatorname{span}(A3, A2B, AB2).

Recuperare aia_i. Cautam combinatii mici v=xU0+yU1+zU2v = xU_0 + yU_1 + zU_2, x,y,z∈[−20,20]x,y,z \in [-20, 20], cu filtrul: toate coordonatele sunt cuburi perfecte nenegative si radacinile cubice au marime plauzibila. Cand trece filtrul, radacinile sunt candidati pentru aia_i.

Recuperare bib_i. Cautam vector pentru A2BA2B in acelasi UU cu curi=3ai2bicur_i = 3 a_i^2 b_i, deci pe fiecare coordonata curi mod (3ai2)=0cur_i \bmod (3 a_i^2) = 0 si 0≤bi<21000 \le b_i < 2^{100}. Apoi cerem ca AB2i=3aibi2AB2_i = 3 a_i b_i^2 sa fie in span⁡(U)\operatorname{span}(U). Raman de obicei 1-2 candidati bb.

Recuperare nn si mm. Construim polinoamele fi(x)=(aix+bi)3−cif_i(x) = (a_i x + b_i)^3 - c_i. La x=mx = m toate sunt 0 modulo nn, deci n∣Res⁡(fi,fj)n \mid \operatorname{Res}(f_i, f_j). Facem gcd pe mai multe rezultante si obtinem nn. Apoi in Zn[x]\mathbb{Z}_n[x] facem gcd polinomial pe perechi; cand gcd-ul este liniar g(x)=ux+v⇒m=−vu−1 mod ng(x) = ux + v \Rightarrow m = -v u^{-1} \bmod n. La final validam pe toate esantioanele ca (aim+bi)3 mod n=ci(a_i m + b_i)^3 \bmod n = c_i.

Capcana de I/O in etapa 2: daca trimiti 50 query-uri, bucla serverului se inchide natural; daca mai trimiti E dupa cele 50, acel E poate fi citit la input("n="). Fix corect: etapa 1 foloseste 40 query-uri si apoi E; etapa 2 exact 50 query-uri, fara E. Acest fix a facut solverul stabil end-to-end.

Solver

from __future__ import annotations

import time
from itertools import combinations, product as iprod
from math import gcd

from pwn import args, context, log, process, remote
from sage.all import (
    QQ, Integer, PolynomialRing, ZZ, Zmod, lcm, matrix, prime_range, vector,
)

ROUNDS = 5
NUM_QUERIES_SIG = 40
NUM_QUERIES_ENC = 50
COMBO_BOUND = 20
B_BOUND = 2 ** 100
QUERY_TOKEN = b"A"
END_TOKEN = b"E"
RECV_TIMEOUT = 30


def recv_res(io):
    deadline = time.time() + 120
    while time.time() < deadline:
        raw = io.recvline(timeout=RECV_TIMEOUT)
        if not raw:
            continue
        line = raw.decode(errors="ignore").strip()
        if line.startswith("res="):
            return int(line[4:])
    raise TimeoutError("timed out waiting for res=")


def collect_res(io, count, send_end=True):
    values = []
    for _ in range(count):
        io.sendline(QUERY_TOKEN)
        values.append(recv_res(io))
    if send_end:
        io.sendline(END_TOKEN)
    return values


def connect():
    if args.LOCAL:
        return process(["python3", "main.py"])
    host = args.HOST or "127.0.0.1"
    port = int(args.PORT or 1337)
    return remote(host, port, timeout=RECV_TIMEOUT)


def gcd_many(values):
    g = 0
    for value in values:
        g = gcd(g, abs(int(value)))
    return g


def ortho_lattice(y_vec):
    t = len(y_vec)
    scale = ZZ(2) ** 2000
    mtx = matrix(ZZ, t, t + 1)
    for i in range(t):
        mtx[i, i] = 1
        mtx[i, t] = ZZ(y_vec[i]) * scale
    reduced = mtx.LLL()
    rows = []
    for i in range(t):
        if reduced[i, t] == 0:
            rows.append([int(reduced[i, j]) for j in range(t)])
    return rows


def solve_n_ortho(y_values, dim_subspace):
    t = len(y_values)
    perp = ortho_lattice(y_values)
    log.info(f"    got {len(perp)} orthogonal vectors")
    need = t - dim_subspace
    if len(perp) < need:
        raise RuntimeError(f"not enough orthogonal vectors ({len(perp)} < {need})")
    v = matrix(ZZ, perp[:need])
    s = v.right_kernel().matrix().LLL()
    log.info(f"    recovered subspace dim: {s.nrows()}")
    if s.nrows() < dim_subspace:
        raise RuntimeError(f"subspace too small ({s.nrows()}), need >= {dim_subspace}")
    u = s[: dim_subspace - 1]
    w = u.right_kernel().matrix()
    y_vec = vector(ZZ, y_values)
    multiples = []
    for i in range(w.nrows()):
        val = abs(int(w[i] * y_vec))
        if val > 0:
            multiples.append(val)
    if not multiples:
        raise RuntimeError("no non-zero multiples from orthogonal projection")
    n = multiples[0]
    for val in multiples[1:]:
        n = gcd(n, val)
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
        while n % p == 0 and n > p:
            n //= p
    return n


def recover_n_sig(responses):
    y_values = [ZZ(r) ** 3 for r in responses]
    log.info("    computing orthogonal lattice ...")
    return solve_n_ortho(y_values, dim_subspace=3)


def find_invertible_cols(basis, k):
    n = basis.ncols()
    for start in range(n - k + 1):
        cols = list(range(start, start + k))
        mtx = matrix(QQ, [[basis[r, c] for r in range(k)] for c in cols])
        if mtx.det() != 0:
            return cols, mtx
    for cols in combinations(range(n), k):
        cols = list(cols)
        mtx = matrix(QQ, [[basis[r, c] for r in range(k)] for c in cols])
        if mtx.det() != 0:
            return cols, mtx
    return None, None


def build_u_subspace(cipher_values):
    t = len(cipher_values)
    mtx = matrix(ZZ, t, t + 1)
    for i in range(t):
        mtx[i, i] = 1
        mtx[i, t] = ZZ(cipher_values[i])
    reduced = mtx.LLL()
    w = matrix(ZZ, t - 4, t)
    for i in range(t - 4):
        for j in range(t):
            w[i, j] = reduced[i, j]
    n_basis = matrix(ZZ, w.right_kernel().basis()).LLL()
    qm = matrix(ZZ, t, 10)
    for i in range(t):
        z0 = ZZ(n_basis[0, i]); z1 = ZZ(n_basis[1, i])
        z2 = ZZ(n_basis[2, i]); z3 = ZZ(n_basis[3, i])
        qm[i, 0] = z0 * z0; qm[i, 1] = z0 * z1; qm[i, 2] = z0 * z2; qm[i, 3] = z0 * z3
        qm[i, 4] = z1 * z1; qm[i, 5] = z1 * z2; qm[i, 6] = z1 * z3
        qm[i, 7] = z2 * z2; qm[i, 8] = z2 * z3; qm[i, 9] = z3 * z3
    qker = qm.right_kernel().matrix()
    if qker.nrows() < 1:
        raise RuntimeError("quadric kernel not found")
    q = vector(QQ, qker[0])
    a0 = matrix(QQ, 4, 4)
    a0[0, 0] = q[0]
    a0[0, 1] = a0[1, 0] = q[1] / 2
    a0[0, 2] = a0[2, 0] = q[2] / 2
    a0[0, 3] = a0[3, 0] = q[3] / 2
    a0[1, 1] = q[4]
    a0[1, 2] = a0[2, 1] = q[5] / 2
    a0[1, 3] = a0[3, 1] = q[6] / 2
    a0[2, 2] = q[7]
    a0[2, 3] = a0[3, 2] = q[8] / 2
    a0[3, 3] = q[9]
    lam_basis = a0.right_kernel().basis()
    if not lam_basis:
        raise RuntimeError("failed to recover lambda")
    lam = vector(QQ, lam_basis[0])
    scale = lcm([x.denominator() for x in lam])
    lam = vector(ZZ, [ZZ(x * scale) for x in lam])
    g = gcd_many([x for x in lam if x != 0])
    lam = vector(ZZ, [x // g for x in lam])
    uc = matrix(ZZ, [list(lam)]).right_kernel().matrix()
    rows = []
    for row in uc.rows():
        qrow = vector(QQ, row)
        l = lcm([x.denominator() for x in qrow])
        ints = [int(x * l) for x in qrow]
        g2 = gcd_many([x for x in ints if x != 0])
        rows.append([x // g2 for x in ints])
    return (matrix(ZZ, rows).LLL() * n_basis).LLL()


def recover_a_from_u(u_basis, combo_bound=COMBO_BOUND):
    t = u_basis.ncols()
    candidates = []
    search = range(-combo_bound, combo_bound + 1)
    for x, y, z in iprod(search, repeat=3):
        if x == 0 and y == 0 and z == 0:
            continue
        vec = x * u_basis[0] + y * u_basis[1] + z * u_basis[2]
        values = [int(vec[i]) for i in range(t)]
        if sum(1 for v in values if v < 0) > sum(1 for v in values if v > 0):
            values = [-v for v in values]
        if any(v < 0 for v in values):
            continue
        roots = []
        ok = True
        for value in values:
            r = int(Integer(value).nth_root(3, truncate_mode=True)[0])
            if r ** 3 == value:
                roots.append(r)
            elif (r + 1) ** 3 == value:
                roots.append(r + 1)
            else:
                ok = False
                break
        if not ok or all(r == 0 for r in roots):
            continue
        if max(roots) >= 2 ** 101:
            continue
        candidates.append((max(roots), sum(roots), roots))
    if not candidates:
        raise RuntimeError("failed to recover A3 / a_i")
    candidates.sort(key=lambda item: (item[0], item[1]))
    return candidates[0][2]


def enumerate_b_candidates(u_basis, a_vec, combo_bound=COMBO_BOUND):
    t = len(a_vec)
    cols3, m3 = find_invertible_cols(u_basis, 3)
    if cols3 is None:
        raise RuntimeError("U has rank < 3")
    out = []
    seen = set()
    search = range(-combo_bound, combo_bound + 1)
    for x, y, z in iprod(search, repeat=3):
        if x == 0 and y == 0 and z == 0:
            continue
        vec = x * u_basis[0] + y * u_basis[1] + z * u_basis[2]
        base = [int(vec[i]) for i in range(t)]
        for sgn in [1, -1]:
            cur = [sgn * v for v in base]
            ok = True
            b_tmp = []
            for i in range(t):
                den = 3 * a_vec[i] * a_vec[i]
                if den == 0 or cur[i] % den != 0:
                    ok = False
                    break
                b_i = cur[i] // den
                if b_i < 0 or b_i >= B_BOUND:
                    ok = False
                    break
                b_tmp.append(int(b_i))
            if not ok or all(v == 0 for v in b_tmp):
                continue
            key = tuple(b_tmp)
            if key in seen:
                continue
            ab2 = vector(ZZ, [3 * a_vec[i] * b_tmp[i] * b_tmp[i] for i in range(t)])
            rhs = vector(QQ, [ab2[c] for c in cols3])
            try:
                coef = m3.solve_right(rhs)
            except Exception:
                continue
            if coef * u_basis != ab2:
                continue
            seen.add(key)
            out.append(b_tmp)
    return out


def poly_gcd_mod_n(fi, fj):
    f = fi
    g = fj
    while not g.is_zero():
        f, g = g, f % g
        if not g.is_zero():
            try:
                g = g * g.leading_coefficient() ** (-1)
            except Exception:
                pass
    try:
        f = f * f.leading_coefficient() ** (-1)
    except Exception:
        pass
    return f


def recover_n_m_from_ab(a_vec, b_vec, cipher_values):
    t = len(cipher_values)
    pz = PolynomialRing(ZZ, "x")
    x = pz.gen()
    k = min(12, t)
    polys = [(ZZ(a_vec[i]) * x + ZZ(b_vec[i])) ** 3 - ZZ(cipher_values[i]) for i in range(k)]
    vals = [abs(polys[i].resultant(polys[j])) for i, j in combinations(range(k), 2)]
    n = vals[0]
    for val in vals[1:]:
        n = gcd(n, val)
    n = abs(n)
    for p in prime_range(2, 2000):
        while n % p == 0 and n > p:
            n //= p
    if n.bit_length() < 2500:
        return None, None
    rz = PolynomialRing(Zmod(n), "x")
    xx = rz.gen()
    m = None
    for i in range(min(8, t)):
        fi = (ZZ(a_vec[i]) * xx + ZZ(b_vec[i])) ** 3 - ZZ(cipher_values[i])
        try:
            fi = fi * fi.leading_coefficient() ** (-1)
        except Exception:
            pass
        for j in range(i + 1, min(9, t)):
            fj = (ZZ(a_vec[j]) * xx + ZZ(b_vec[j])) ** 3 - ZZ(cipher_values[j])
            try:
                fj = fj * fj.leading_coefficient() ** (-1)
            except Exception:
                pass
            try:
                g = poly_gcd_mod_n(fi, fj)
            except Exception:
                continue
            if g.degree() == 1:
                try:
                    m_try = int((-g[0] * g[1] ** (-1)) % n)
                except Exception:
                    continue
                ok = True
                for u in range(min(8, t)):
                    if pow((a_vec[u] * m_try + b_vec[u]) % n, 3, n) != cipher_values[u] % n:
                        ok = False
                        break
                if ok:
                    m = m_try
                    break
        if m is not None:
            break
    if m is None:
        return int(n), None
    return int(n), int(m)


def recover_stage2(cipher_values):
    u_basis = build_u_subspace(cipher_values)
    a_vec = recover_a_from_u(u_basis)
    log.info(f"        recovered a_i vector (a[:3]={a_vec[:3]})")
    b_candidates = enumerate_b_candidates(u_basis, a_vec)
    log.info(f"        candidate b vectors: {len(b_candidates)}")
    if not b_candidates:
        raise RuntimeError("no valid b candidate found")
    for idx, b_vec in enumerate(b_candidates):
        n, m = recover_n_m_from_ab(a_vec, b_vec, cipher_values)
        if n is None or m is None:
            continue
        ok = True
        for i in range(len(cipher_values)):
            if pow((a_vec[i] * m + b_vec[i]) % n, 3, n) != cipher_values[i] % n:
                ok = False
                break
        if ok:
            log.info(f"      selected b candidate #{idx}")
            return n, m
    raise RuntimeError("failed to recover (n, m) from all b candidates")


def solve():
    io = connect()
    for rnd in range(ROUNDS):
        log.info(f"[sig {rnd + 1}/{ROUNDS}] collecting {NUM_QUERIES_SIG} queries ...")
        sig_values = collect_res(io, NUM_QUERIES_SIG, send_end=True)
        n = recover_n_sig(sig_values)
        log.success(f"[sig {rnd + 1}/{ROUNDS}] n recovered ({n.bit_length()} bits)")
        io.recvuntil(b"n=")
        io.sendline(str(n).encode())
    for rnd in range(ROUNDS):
        log.info(f"[enc {rnd + 1}/{ROUNDS}] collecting {NUM_QUERIES_ENC} queries ...")
        cipher_values = collect_res(io, NUM_QUERIES_ENC, send_end=False)
        n, m = recover_stage2(cipher_values)
        log.success(f"[enc {rnd + 1}/{ROUNDS}] n recovered ({n.bit_length()} bits)")
        log.success(f"[enc {rnd + 1}/{ROUNDS}] m recovered")
        io.recvuntil(b"n=")
        io.sendline(str(n).encode())
        io.recvuntil(b"m=")
        io.sendline(str(m).encode())
    log.success("All rounds passed! Getting flag...")
    io.interactive()


if __name__ == "__main__":
    context.log_level = args.LOG_LEVEL or "info"
    solve()

Rularea trece toate rundele si scoate flagul:

>> sage -python solve.py HOST=35.198.137.88 PORT=32059
[+] [sig 1/5] n recovered (2999 bits)
...
[+] [enc 5/5] n recovered (2999 bits)
[+] [enc 5/5] m recovered
[+] All rounds passed! Getting flag...
[*] Switching to interactive mode
"You have intercepted someone else's communication, but your time is limited. Act fast before it's too late!"

flag{ortho_lattice_ftw_56f17b85f9a3d5891b0f}

Flag: flag{ortho_lattice_ftw_56f17b85f9a3d5891b0f}