Last Flight
authored by kanon
special thanks quocbao21_
I got split up from them. It is the final chance. Can you find a special flight?
from Crypto.Util.number import *
from random import randint
import os
p = 4718527636420634963510517639104032245020751875124852984607896548322460032828353
j = 4667843869135885176787716797518107956781705418815411062878894329223922615150642
flag = os.getenv("FLAG", "SECCON{test_flag}")
def interstellar_flight(j, flight_plans=None):
planet = EllipticCurve(GF(p), j=j)
visited_planets = []
if flight_plans == None:
flight_plans = [randint(0, 2) for _ in range(160)]
for flight_plan in flight_plans:
flight = planet.isogenies_prime_degree(2)[flight_plan]
if len(visited_planets) > 1:
if flight.codomain().j_invariant() == visited_planets[-2]:
continue
planet = flight.codomain()
visited_planets.append(planet.j_invariant())
return visited_planets[-1]
print("Currently in interstellar flight...")
vulcan = interstellar_flight(j)
bell = interstellar_flight(j)
print(f"vulcan's planet is here : {vulcan}")
print(f"bell's planet is here : {bell}")
final_flight_plans = list(map(int, input("Master, please input the flight plans > ").split(", ")))
if interstellar_flight(vulcan, final_flight_plans) == bell:
print(f"FIND THE BELL'S SIGNAL!!! SIGNAL SAY: {flag}")
else:
print("LOST THE SIGNAL...")
素数$p$と開始点$j$が定義されています。有限体$\mathbb{F}_p$上の同種写像グラフにおける長さ160の非バックトラックランダムウォークを2本生成し、終点vulcanとbellが与えられます。
私たちは、vulcanからbellに写すようなインデックス列0/1/2のリストを提出し、それが正しければフラグを得ることができます。
解法
曲線の確認
今回、SageのEllipticCurve(GF(p), j=j)は$ j \neq 0, 1728$のとき、short Weierstrass modelとなります。
そもそも、Weierstrass modelは、
$$
y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6
$$
となります。
ここで、今回定義されている$p,j$の場合のWeierstrassの係数を調べてみましょう。以下のプログラムを実行してみます。
p = 4718527636420634963510517639104032245020751875124852984607896548322460032828353
j = 4667843869135885176787716797518107956781705418815411062878894329223922615150642
E = EllipticCurve(GF(p), j=j)
print(E.ainvs())
すると、以下のように表示されます。
(0, 0, 0, 3888692665638047937045570002487084378458447133902318295621022455533667665827573, 2154486936412009487314246715912840515820627580708215847435236912193598988144532)
ここで、ainvs関数は、[a1, a2, a3, a4, a6]をリストかタプルで返却されるため、今回、$a_1, a_2, a_3$は0であることがわかります。
つまり、
$$
y^2 = x^3 + a_4x+a_6
$$
となります。これが、short Weierstrass modelとなります。
short Weierstrass modelのとき、$j$-不変量は
$$
j = 1728 \cdot \frac{4a_4^3}{4a_4^3 + 27a_6^2}
$$
で求められます。
さて、少し式変形すると、以下のようになります。
$$
\frac{j}{1728} = \frac{4a_4^3}{4a_4^3 + 27a_6^2}
$$
両辺に分母をかけ、整理すると
$$
\frac{j}{1728} \cdot 27a_6^2 = 4a_4^3\left( 1 - \frac{j}{1728}\right)
$$
となり、両辺に1728をかけると
$$
27ja_6^2 = 4a_4^3(1728-j)
$$
となります。
ここで、$k = j-1728$とすると、
$$
27ja_6^2 = -4ka_4^3
$$
となります。この式を満たすように$a_4,a_6$を選べばよいので、たとえば
$$
a_4 = -3jk, a_6 = -2jk^2
$$
と置くと両辺が一致します。
なお、short Weierstrass model
$$
E: y^2 = x^3 + a_4x + a_6
$$
では、2-torsion pointは $[2]P=\mathcal{O}$を満たす点であり、標数が2でないときは必ず$y=0$を満たします。
したがって、その$x$座標は
$$
f(x) = x^3 + a_4x + a_6
$$
の根に一致します。
Sageのisogenies_prime_degree()は、定義域$E$である分離可能な $l$-次同種写像を整列した順に列挙します。特に、isogenies_prime_degree(2)は、3 本の 2-同種写像を返します。短い Weierstrass 形ではそれらは 3 つの非自明 2-捩れ点（$y=0$ の解）に対応し、Sage はそれらを一定の規則で並べるため、インデックス 0/1/2 で選択できます。
根だけを用いた2-同種写像の移動
今回の$p$は262ビットかつ$GF(p)$なので、素数体です。
そのため、先ほどの3次方程式$f(x)$の根を求めるには有限体上で$f(x)$を分解する、すなわち、
$$
f(x) = (x-r_0)(x-r_1)(x-r_2)
$$
をなるように因数分解をするということです。
しかし、これを毎回やるのはかなり時間が食ってしまいますし、接続は概ね10分程度で切れてしまうため時間が足りないのは明白です。
ここで、曲線を以下で考えてみましょう。
$$
y^2 = (x-r_0)(x-r_1)(x-r_2)
$$
このように、根$r_0, r_1, r_2$を状態として持っています。
この時、
\begin{align}
r'_0 &= -2r_k\\
r'_{\pm} &= r_k \pm 2\sqrt{(r_k-r_j)(r_k-r_l)}
\end{align}
とすると、根を更新できます。
ルートの探索
2-同種写像グラフの連結成分が「火山（isogeny volcano）」の層構造を持つことを利用して、vulcan と bell の間の経路を機械的に復元することが僕たちの目的です。
火山では頂点が level（高さ）で分割され、一般に
$$
V_0, V_1, \dots, V_d
$$
のように層をなします。ここで surface は$V_0$、floorは$V_d$とみなせます。
そして、今回の問題では直前の辺をすぐ戻る操作が禁止されています。したがって、ある頂点から子方向（下降）に 1 歩進むと、次の頂点で親方向の辺は直前に通った辺と一致し、その親方向へは戻れません。よって一度下降を始めると、その後は子方向の選択しか残らず、強制的に下降し続けて floorへ到達します。
以上より、各頂点でfloor まで最短何手で降りられるかという距離$\delta(v)$を計算できれば、隣接3頂点のうち$\delta(\text{neighbor})$が最大になる方向が親（上向き）である、と一意に判定できます。
さて、私たちは
- vulcan から親を辿って root までの祖先列を作る
- bell から親を辿って root までの祖先列を作る
- 2 つの祖先列が最初に一致する頂点を見つける
といったルールを繰り返すことで、解くことができます。
なぜなら、今回は木なので経路は一意で
$$
vulcan \to \cdots \to \text{最初に一致する頂点} \to \cdots \to bell
$$
がそのまま求める経路となるからです。
以上を参考にして作成したsolverは以下です(チャッピーと協力しました)。
import random
import re
from dataclasses import dataclass
from typing import Optional
import subprocess
import gmpy2
from pwn import remote, context
p = 4718527636420634963510517639104032245020751875124852984607896548322460032828353
j0 = 4667843869135885176787716797518107956781705418815411062878894329223922615150642
_P = gmpy2.mpz(p)
HOST = "last-flight.seccon.games"
PORT = 5000
context.log_level = "info"
def inv_mod(a):
return int(gmpy2.invert(gmpy2.mpz(a) % _P, _P))
def legendre_symbol(a):
return int(gmpy2.powmod(gmpy2.mpz(a) % _P, (p - 1) // 2, _P))
_TS_Q = p - 1
_TS_S = 0
while _TS_Q % 2 == 0:
_TS_S += 1
_TS_Q //= 2
_TS_Z = 2
while legendre_symbol(_TS_Z) != p - 1:
_TS_Z += 1
_TS_C0 = int(gmpy2.powmod(gmpy2.mpz(_TS_Z), _TS_Q, _P))
_TS_Q_MPZ = gmpy2.mpz(_TS_Q)
_TS_Q1_DIV2_MPZ = gmpy2.mpz((_TS_Q + 1) // 2)
def mod_sqrt(a):
a %= p
if a == 0:
return 0
if legendre_symbol(a) != 1:
return None
m = _TS_S
c = _TS_C0
am = gmpy2.mpz(a)
t = int(gmpy2.powmod(am, _TS_Q_MPZ, _P))
r = int(gmpy2.powmod(am, _TS_Q1_DIV2_MPZ, _P))
while t != 1:
i = 1
t2 = (t * t) % p
while i < m and t2 != 1:
t2 = (t2 * t2) % p
i += 1
b = int(gmpy2.powmod(gmpy2.mpz(c), 1 << (m - i - 1), _P))
m = i
c = (b * b) % p
t = (t * c) % p
r = (r * b) % p
return r
def curve_coeffs_from_j(j):
j %= p
k = (j - 1728) % p
a4 = (-3 * j * k) % p
a6 = (-2 * j * k * k) % p
return a4, a6
def j_from_roots(roots):
r0, r1, r2 = roots
a4 = (r0 * r1 + r0 * r2 + r1 * r2) % p
a6 = (-r0 * r1 * r2) % p
num = (1728 * 4 * pow(a4, 3, p)) % p
den = (4 * pow(a4, 3, p) + 27 * pow(a6, 2, p)) % p
return (num * inv_mod(den)) % p
@dataclass(frozen=True)
class StepResult:
roots: Optional[list[int]]
back_idx: Optional[int]
def isogeny_step(roots, idx):
rk = roots[idx]
rj = roots[(idx + 1) % 3]
rl = roots[(idx + 2) % 3]
t = ((rk - rj) % p) * ((rk - rl) % p) % p
s = mod_sqrt(t)
if s is None:
return StepResult(None, None)
twos = (2 * s) % p
back_root = (-2 * rk) % p
nxt = [back_root, (rk + twos) % p, (rk - twos) % p]
nxt.sort()
return StepResult(nxt, nxt.index(back_root))
def _choose_idx_not_back(back_idx):
return 0 if back_idx != 0 else 1
def path_len_to_floor_from_edge(roots, first_idx, best):
first = isogeny_step(roots, first_idx)
if first.roots is None:
return 1
cur = first.roots
back_idx = first.back_idx
steps = 1
while steps < best:
idx = _choose_idx_not_back(back_idx)
nxt = isogeny_step(cur, idx)
steps += 1
if nxt.roots is None:
return steps
cur = nxt.roots
back_idx = nxt.back_idx
return best
def dist_to_floor(roots):
best = 10**18
for idx in range(3):
best = min(best, path_len_to_floor_from_edge(roots, idx, best))
return best
def reaches_floor_within(roots, back_idx, max_steps):
cur = roots
b = back_idx
for _ in range(max_steps):
idx = _choose_idx_not_back(b)
nxt = isogeny_step(cur, idx)
if nxt.roots is None:
return True
cur = nxt.roots
b = nxt.back_idx
return False
def find_parent_step(roots, delta):
for idx in range(3):
nxt = isogeny_step(roots, idx)
if nxt.roots is None:
continue
if not reaches_floor_within(nxt.roots, nxt.back_idx, delta):
return idx, nxt.roots
return None
def q_mul(u, v, a, b):
u0, u1, u2 = u
v0, v1, v2 = v
w0 = (u0 * v0) % p
w1 = (u0 * v1 + u1 * v0) % p
w2 = (u0 * v2 + u1 * v1 + u2 * v0) % p
w3 = (u1 * v2 + u2 * v1) % p
w4 = (u2 * v2) % p
c0 = (w0 - w3 * b) % p
c1 = (w1 - w3 * a - w4 * b) % p
c2 = (w2 - w4 * a) % p
return (c0, c1, c2)
def q_pow(base, exp, a, b):
res = (1, 0, 0)
cur = base
e = exp
while e:
if e & 1:
res = q_mul(res, cur, a, b)
cur = q_mul(cur, cur, a, b)
e >>= 1
return res
def roots_from_j(j):
a4, a6 = curve_coeffs_from_j(j)
return roots_cubic_monic_no_x2(a4, a6)
def poly_trim(poly):
while len(poly) > 1 and poly[-1] == 0:
poly.pop()
return poly
def poly_deg(poly):
return len(poly) - 1
def poly_scale(poly, sc):
sc %= p
return [(c * sc) % p for c in poly]
def poly_mod(dividend, divisor):
num = poly_trim(dividend[:])
den = poly_trim(divisor[:])
db = poly_deg(den)
inv_lc = inv_mod(den[db])
while poly_deg(num) >= db and not (len(num) == 1 and num[0] == 0):
da = poly_deg(num)
coef = (num[da] * inv_lc) % p
shift = da - db
for i in range(db + 1):
num[i + shift] = (num[i + shift] - coef * den[i]) % p
poly_trim(num)
return num
def poly_gcd(pa, pb):
a0 = poly_trim(pa[:])
b0 = poly_trim(pb[:])
while not (len(b0) == 1 and b0[0] == 0):
a0, b0 = b0, poly_mod(a0, b0)
return poly_scale(a0, inv_mod(a0[-1]))
def poly_div_exact(dividend, divisor):
num = poly_trim(dividend[:])
den = poly_trim(divisor[:])
db = poly_deg(den)
inv_lc = inv_mod(den[db])
q = [0] * (max(0, poly_deg(num) - db) + 1)
while poly_deg(num) >= db and not (len(num) == 1 and num[0] == 0):
da = poly_deg(num)
coef = (num[da] * inv_lc) % p
shift = da - db
q[shift] = coef
for i in range(db + 1):
num[i + shift] = (num[i + shift] - coef * den[i]) % p
poly_trim(num)
if not (len(num) == 1 and num[0] == 0):
raise ValueError("polynomial not divisible")
return poly_trim(q)
def roots_quadratic(poly):
poly = poly_trim(poly[:])
if poly_deg(poly) != 2:
return []
a0 = poly[0] % p
a1 = poly[1] % p
a2 = poly[2] % p
if a2 == 0:
return []
disc = (a1 * a1 - 4 * a2 * a0) % p
sd = mod_sqrt(disc)
if sd is None:
return []
inv2a = inv_mod((2 * a2) % p)
x1 = ((-a1 + sd) * inv2a) % p
x2 = ((-a1 - sd) * inv2a) % p
return [x1] if x1 == x2 else [x1, x2]
def roots_cubic_monic_no_x2(a, b):
a %= p
b %= p
f = [b, a, 0, 1]
x = (0, 1, 0)
xp = q_pow(x, p, a, b)
if xp != x:
xp_minus_x = poly_trim([xp[0] % p, (xp[1] - 1) % p, xp[2] % p])
g = poly_gcd(f, xp_minus_x)
dg = poly_deg(g)
if dg == 1:
# g = u0 + u1*x
return [(-g[0] * inv_mod(g[1])) % p]
if dg == 2:
return sorted(roots_quadratic(g))
return []
while True:
c = random.randrange(p)
gx = (c, 1, 0) # x + c
h = q_pow(gx, (p - 1) // 2, a, b) # in F_p[x]/(f)
h_minus_1 = poly_trim([(h[0] - 1) % p, h[1] % p, h[2] % p])
d = poly_gcd(f, h_minus_1)
dd = poly_deg(d)
if 0 < dd < 3:
break
roots = []
dd = poly_deg(d)
if dd == 1:
roots.append((-d[0] * inv_mod(d[1])) % p)
q = poly_div_exact(f, d)
if poly_deg(q) == 2:
roots.extend(roots_quadratic(q))
else:
roots.extend(roots_quadratic(d))
q = poly_div_exact(f, d)
if poly_deg(q) == 1:
roots.append((-q[0] * inv_mod(q[1])) % p)
roots = sorted(set(roots))
if len(roots) != 3:
raise ValueError("unexpected root count: %d" % len(roots))
return roots
def ancestor_js_from_roots(start_roots):
delta = dist_to_floor(start_roots)
cur = start_roots
cur_delta = delta
out = []
while True:
out.append(j_from_roots(cur))
parent = find_parent_step(cur, cur_delta)
if parent is None:
break
_, cur = parent
cur_delta += 1
return out
def find_lca_by_j(anc_a, anc_b):
pos_a = {j: i for i, j in enumerate(anc_a)}
for i_b, j in enumerate(anc_b):
i_a = pos_a.get(j)
if i_a is not None:
return j, i_a, i_b
raise ValueError("no LCA found (unexpected in tree volcano)")
def step_index_to_reach_next_j(cur_roots, target_j):
for idx in range(3):
nxt = isogeny_step(cur_roots, idx)
if nxt.roots is None:
continue
if j_from_roots(nxt.roots) == target_j:
return idx, nxt.roots
raise ValueError("failed to follow j-path")
def solve_instance(vulcan_j, bell_j):
roots_v = roots_from_j(vulcan_j)
roots_b = roots_from_j(bell_j)
anc_v = ancestor_js_from_roots(roots_v)
anc_b = ancestor_js_from_roots(roots_b)
lca_j, idx_v, idx_b = find_lca_by_j(anc_v, anc_b)
left = anc_v[: idx_v + 1]
right = list(reversed(anc_b[:idx_b]))
path_js = left + right
if path_js[0] != vulcan_j or path_js[-1] != bell_j:
raise ValueError("bad j-path construction")
cur = roots_v
plans = []
for target_j in path_js[1:]:
idx, cur = step_index_to_reach_next_j(cur, target_j)
plans.append(idx)
return plans
def hashcash_solve(resource, bits):
out = subprocess.check_output(["hashcash", f"-mb{bits}", resource], text=True)
return out.strip()
def _parse_hashcash_resource(banner):
txt = banner.decode(errors="ignore")
for line in txt.splitlines():
line = line.strip()
if line.startswith("hashcash -mb28 "):
parts = line.split()
if parts:
return parts[-1]
raise RuntimeError("failed to parse hashcash resource")
def _parse_planets(chal):
txt = chal.decode(errors="ignore")
vulcan = None
bell = None
for line in txt.splitlines():
if "vulcan's planet is here" in line:
m = re.search(r":\s*(-?\d+)\s*$", line)
if m:
vulcan = int(m.group(1))
if "bell's planet is here" in line:
m = re.search(r":\s*(-?\d+)\s*$", line)
if m:
bell = int(m.group(1))
if vulcan is None or bell is None:
raise RuntimeError("failed to parse vulcan/bell")
return vulcan, bell
io = remote(HOST, PORT)
banner = io.recvuntil(b"hashcash token: ")
resource = _parse_hashcash_resource(banner)
stamp = hashcash_solve(resource, 28)
io.sendline(stamp.encode())
print("[+] Sent hashcash token:", stamp)
chal = io.recvuntil(b"Master, please input the flight plans > ")
vulcan_j, bell_j = _parse_planets(chal)
print(f"[+] Received challenge: vulcan_j={vulcan_j}, bell_j={bell_j}")
plans = solve_instance(vulcan_j, bell_j)
print(f"[+] Computed flight plans: {plans}")
io.sendline((", ".join(map(str, plans))).encode())
io.interactive()
Flag: SECCON{You_have_made_your_wish_so_you_have_got_to_make_it_true}
おまけ
なんでこれ32solvesもあるんだ。。。