Sumar
Challenge-ul are 2 etape, fiecare cu 5 runde:
- etapa signatures: trebuie gasit
- etapa encryption: trebuie gasite si
Serverul raspunde la query-uri de forma , unde la fiecare query sunt random, iar si raman fixe pe runda.
Ideea atacului:
- folosim relatii liniare ascunse intre multe esantioane
- extragem vectori ortogonali cu
LLLpe un lattice de forma - obtinem multipli de , apoi facem
gcd - in etapa 2 reconstruim subspatiul cubic util, apoi recuperam , , ,
Dovada rezolvarii
Date importante din main.py:
bits = 1500, deci are aprox 3000 bitik = 3, deci- se impune
p % 3 != 1siq % 3 != 1 - maxim 50 query-uri pe runda
- etapa 1 cere , etapa 2 cere si
Conditia p % 3 != 1 garanteaza practic ca , deci exista .
Pentru o runda cu query-uri notam vectorii , , , , , , .
Etapa 1
Serverul da . Ridicam la puterea 3:
Pe vectori: , deci sta intr-un subspatiu ascuns de dimensiune 3.
Latice ortogonale. Construim . Un vector de forma este scurt cand . LLL intoarce astfel multi vectori ortogonali pe . Daca e ortogonal pe si , atunci , deci este multiplu de :
Practic: colectam 40 query-uri, calculam , rulam atacul ortogonal, trimitem . Aceasta etapa trece stabil 5/5 runde.
Etapa 2
Serverul da . Ridicare in :
Adica . Pare 5D, dar direct nu este stabil. Folosim matrice ne-scalata , . Dupa LLL luam primele randuri (fara ultima coloana), obtinem , apoi . In practica iese dimensiune 4 si . Deci este eliminat, raman exact directiile utile plus .
Vectorii satisfac relatia . Folosim coloanele lui ca puncte proiective in , construim matricea monoamelor de grad 2, gasim cuadrica unica, apoi din matricea ei simetrica extragem o forma liniara . da subspatiul de dimensiune 3 dorit, iar .
Recuperare . Cautam combinatii mici , , cu filtrul: toate coordonatele sunt cuburi perfecte nenegative si radacinile cubice au marime plauzibila. Cand trece filtrul, radacinile sunt candidati pentru .
Recuperare . Cautam vector pentru in acelasi cu , deci pe fiecare coordonata si . Apoi cerem ca sa fie in . Raman de obicei 1-2 candidati .
Recuperare si . Construim polinoamele . La toate sunt 0 modulo , deci . Facem gcd pe mai multe rezultante si obtinem . Apoi in facem gcd polinomial pe perechi; cand gcd-ul este liniar . La final validam pe toate esantioanele ca .
Capcana de I/O in etapa 2: daca trimiti 50 query-uri, bucla serverului se inchide natural; daca mai trimiti
Edupa cele 50, acelEpoate fi citit lainput("n="). Fix corect: etapa 1 foloseste 40 query-uri si apoiE; etapa 2 exact 50 query-uri, faraE. 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}