TL;DR

The service is a random walk on the 2-isogeny graph of an ordinary elliptic curve over $\mathbb{F}_p$ For this curve, the Frobenius discriminant satisfies

$\Delta = t^2 - 4p = -163 \cdot 2^{256}$

So the 2-isogeny graph is a 2-volcano of height 128 with a single crater vertex

Analysis

The code routin

1
from Crypto.Util.number import *
2
from random import randint
3
import os
4

5
p = 4718527636420634963510517639104032245020751875124852984607896548322460032828353
6
j = 4667843869135885176787716797518107956781705418815411062878894329223922615150642
7

8
flag = os.getenv("FLAG", "SECCON{test_flag}")
9

10

11
def interstellar_flight(j, flight_plans=None):
12
    planet = EllipticCurve(GF(p), j=j)
13
    visited_planets = []
14
    if flight_plans == None:
15
        flight_plans = [randint(0, 2) for _ in range(160)]
16

17
    for flight_plan in flight_plans:
18
        flight = planet.isogenies_prime_degree(2)[flight_plan]
19
        if len(visited_planets) > 1:
20
            if flight.codomain().j_invariant() == visited_planets[-2]:
21
                continue
22
        planet = flight.codomain()
23
        visited_planets.append(planet.j_invariant())
24
    return visited_planets[-1]
25

26

27
print("Currently in interstellar flight...")
28

29
vulcan = interstellar_flight(j)
30
bell = interstellar_flight(j)
31

32
print(f"vulcan's planet is here : {vulcan}")
33
print(f"bell's planet is here : {bell}")
34

35

36
final_flight_plans = list(map(int, input("Master, please input the flight plans > ").split(", ")))
37

38
if interstellar_flight(vulcan, final_flight_plans) == bell:
39
    print(f"FIND THE BELL'S SIGNAL!!! SIGNAL SAY: {flag}")
40
else:
41
    print("LOST THE SIGNAL...")

start from a fixed $j$ over $\mathbb{F}_p$
Each step chooses a 2-isogeny of the current curve (so typically indices $0,1,2$ are possible).
There is a no immediate backtracking rule: it refuses to go back to the previous vertex (after the first move).
It prints two endpoints: vulcan and bell.
must provide a comma+space separated list of indices, and the server checks: interstellar_flight(vulcan, plans) = bell

So the problem is given two vertices in the 2-isogeny graph, output an index sequence that walks from one to the other without backtracking.

For an ordinary elliptic curve $E/\mathbb{F}_p$ , all curves isogenous to $E$ over $\mathbb{F}_p$ have the same trace of Frobenius $t$ (equivalently the same group order).

The Frobenius endomorphism $\pi$ satisfies: $\pi^2 - t\pi + p = 0,$ so the Frobenius discriminant is: $\Delta = t^2 - 4p.$

For ordinary curves, $\mathrm{End}(E)$ is an order in an imaginary quadratic field $K=\mathbb{Q}(\sqrt{\Delta_0})$ , and we can write: $\Delta = \Delta_0 \cdot f_\pi^2$

where:

$\Delta_0$ is the fundamental discriminant of K,
$f_\pi$ is the conductor of the order $\mathbb{Z}[\pi]$ in $\mathcal{O}_K$ .

For a prime $\ell$ (here $\ell=2$ ), the graph of $\ell$ -isogenies inside a fixed isogeny class has the structure of an $\ell$ -volcano

The height of the volcano is $e = v_\ell(f_\pi)$ .
Vertices above the floor have $\ell+1$ outgoing $\ell$ -isogenies.
Each such vertex has exactly one upward edge (toward larger endomorphism ring / toward the crater) and $\ell$ downward edges.

For $\ell=2$ , that means

If we are not on the floor, we usually see 3 2-isogenies.
There is a unique parent (up) and two children (down)

From the provided chall.sage values $p$ is a 262-bit prime.

The starting curve has $\#E(\mathbb{F}_p) = p + 1 - t.$

If you ask Sage for the order of the curve constructed from the given starting $j$ , you get: $\#E(\mathbb{F}_p) = p + 63 \quad\Rightarrow\quad t = p+1-(p+63) = -62.$

Now compute the discriminant: $\Delta = t^2 - 4p = (-62)^2 - 4p = 3844 - 4p.$

This factors as $\Delta = -163 \cdot 2^{256}.$

So The CM field is $K = \mathbb{Q}(\sqrt{-163})$ with fundamental discriminant $\Delta_0=-163$ . $f_\pi = 2^{128}$ , hence the $2$ -volcano height is $e=128$ .

Even better: $-163$ is one of the class number 1 discriminants, so the crater has size $h(-163)=1$

That means the $2$ -volcano has a single crater vertex (a unique “root” up to isomorphism).

Concretely, the unique CM $j$ -invariant is the famous Ramanujan value: $j(-163) = -640320^3.$ Working modulo $p$ , the crater $j$ is: $j_{\text{root}} \equiv -640320^3 \pmod p.$

This single root property is the key simplification: every vertex has a unique path upward to the same root.

For $j \notin \{0,1728\}$ , there are generally two non-isomorphic curves over $\mathbb{F}_p$ with the same $j$ : they are quadratic twists of each other.

They have opposite traces: $t(E') = -t(E).$

The server prints only $j$ -invariants, so when we reconstruct a curve locally with

1
E = EllipticCurve(GF(p), j=j)

Sage may choose either twist representative for that $j$ .

But isogenies over $\mathbb{F}_p$ preserve the trace. Since the server starts in the isogeny class with $t=-62$ , both vulcan and bell are in that class (as curve objects on the server), even if constructing from $j$ locally sometimes gives the $t=+62$ twist.

On a $2$ -volcano above the floor

there are 3 neighbors,
exactly one has larger height (the parent),
two have smaller height (children).

So if we can compute the height above the floor $h(j)$ , then the parent is simply the neighbor with $h$ increased by $1$ .

Sage has height_above_floor(2, e), but it is slow because it repeatedly builds modular polynomials.

Hardcode the classical modular polynomial $\Phi_2$

The degree- $2$ modular polynomial in $j$ -invariants is

$\Phi_2(X,Y) = X^3 + Y^3 - X^2Y^2$

$+ 1488(X^2Y + XY^2)$

$- 162000(X^2 + Y^2)$

$+ 40773375XY$

$+ 8748000000(X+Y)$

$- 157464000000000$

For a fixed $Y=j(E)$ , the $j$ -invariants of the curves that are $2$ -isogenous to $E$ (over $\mathbb{F}_p$ ) are exactly the roots of the cubic

$\Phi_2(X, j) = 0 \quad\text{in } \mathbb{F}_p.$

So list neighbors becomes root a cubic over $\mathbb{F}_p$ .

Speed trick: Vieta to avoid repeated factoring Sage’s height_above_floor essentially iterates:

take a neighbor $j_1$ ,
look at $\Phi_2(X, j_1)$
divide out the factor $(X - j_0)$ corresponding to the edge we came from,
take the remaining root to go one step further down

Since $\Phi_2(X, j_1)$ is cubic with roots $(r_0, r_1, r_2)$ and we know $r_0=j_0$ , we can get the other roots via Vieta

If the cubic is $X^3 + a_2 X^2 + a_1 X + a_0$ , then $r_0 r_1 r_2 = -a_0,\qquad r_0 + r_1 + r_2 = -a_2.$

Therefore $r_1 r_2 = \frac{-a_0}{r_0},\qquad r_1 + r_2 = -a_2 - r_0.$

Then $(r_1, r_2)$ are the solutions of $Z^2 - (r_1+r_2)Z + (r_1r_2)=0,$ which is just one square root in $\mathbb{F}_p$ .

This gives an $O(1)$ next step without polynomial division or root finding each time. With caching, computing heights and parent edges becomes fast enough to do online.

Because the crater is a single vertex, the LCA

Build the chain from vulcan upward to the crater, recording at each step the index (0/1/2) of the parent isogeny returned by isogenies_prime_degree(2).
Build the chain from bell upward to the crater (after fixing the twist).
The first common $j$ between those chains is the crater (in practice it really is the crater here).
Concatenate
- vulcan -> crater using the recorded indices,
- crater -> bell by reversing the bell -> crater chain and, at each step, selecting the index whose codomain $j$ matches the next vertex.

This produces a simple path with no immediate backtracking, so the server’s continue never triggers.

Exploit

1
from sage.all import *
2

3
P = 4718527636420634963510517639104032245020751875124852984607896548322460032828353
4
F = GF(P)
5
R = PolynomialRing(F, "x")
6
x = R.gen()
7

8

9
def _phi2_coeffs(y):
10
    y = F(y)
11
    a2 = 1488 * y - y * y - 162000
12
    a1 = 1488 * y * y + 40773375 * y + 8748000000
13
    a0 = y**3 - 162000 * y * y + 8748000000 * y - 157464000000000
14
    return a2, a1, a0
15

16

17
def _phi2_roots_x(y):
18
    a2, a1, a0 = _phi2_coeffs(y)
19
    f = x**3 + a2 * x**2 + a1 * x + a0
20
    return f.roots(multiplicities=False)
21

22

23
def _phi2_other_roots(prev_x_root, y):
24
    a2, _, a0 = _phi2_coeffs(y)
25
    r0 = F(prev_x_root)
26
    prod = -a0  # r0*r1*r2
27
    r1r2 = prod / r0
28
    s = -a2 - r0  # r1+r2
29
    disc = s * s - 4 * r1r2
30
    if not disc.is_square():
31
        return []
32
    sd = disc.sqrt()
33
    inv2 = F(1) / 2
34
    return [(s + sd) * inv2, (s - sd) * inv2]
35

36

37
_height_cache = {}
38

39

40
def _height_above_floor_rank2(j, e=128):
41
    j = int(j)
42
    if j in _height_cache:
43
        return _height_cache[j]
44
    if j in (0, 1728):
45
        _height_cache[j] = e
46
        return e
47

48
    jj = F(j)
49
    j1 = _phi2_roots_x(jj)
50
    if len(j1) < 3:
51
        _height_cache[j] = 0
52
        return 0
53

54
    j0 = [jj, jj, jj]
55
    h = 1
56
    while True:
57
        for i in range(3):
58
            r = _phi2_other_roots(j0[i], j1[i])
59
            if not r:
60
                _height_cache[j] = h
61
                return h
62
            j0[i] = j1[i]
63
            j1[i] = r[0]
64
        h += 1
65

66

67
_floor_cache = {}
68

69

70
def _height_curve(E):
71
    j = int(E.j_invariant())
72
    if j in _floor_cache:
73
        if _floor_cache[j]:
74
            return 0
75
    else:
76
        _floor_cache[j] = E.two_torsion_rank() < 2
77
        if _floor_cache[j]:
78
            return 0
79
    return _height_above_floor_rank2(j)
80

81

82
def _chain_to_root(curve):
83
    chain = []
84
    cur = curve
85
    prev_j = None
86
    h = _height_curve(cur)
87

88
    while True:
89
        if h == 128:
90
            chain.append((cur, None))
91
            return chain
92

93
        iso = cur.isogenies_prime_degree(2)
94
        codoms = [f.codomain() for f in iso]
95
        codom_js = [int(C.j_invariant()) for C in codoms]
96

97
        if prev_j is None:
98
            hs = [_height_curve(C) for C in codoms]
99
            idx = hs.index(max(hs))
100
        else:
101
            cand = [i for i, jj in enumerate(codom_js) if jj != prev_j]
102
            i0 = cand[0]
103
            h0 = _height_curve(codoms[i0])
104
            idx = i0 if h0 > h else cand[1]
105

106
        chain.append((cur, idx))
107
        prev_j = int(cur.j_invariant())
108
        cur = codoms[idx]
109
        h += 1
110

111

112
def _find_index_to(curve, target_j):
113
    iso = curve.isogenies_prime_degree(2)
114
    for i, f in enumerate(iso):
115
        if int(f.codomain().j_invariant()) == target_j:
116
            return i, f.codomain()
117

118

119
def solve(vulcan_j, bell_j):
120
    E_v = EllipticCurve(F, j=vulcan_j)
121
    t_v = int(E_v.trace_of_frobenius())
122

123
    E_b = EllipticCurve(F, j=bell_j)
124
    t_b = int(E_b.trace_of_frobenius())
125
    if t_b != t_v:
126
        E_b = E_b.quadratic_twist()
127
        t_b2 = int(E_b.trace_of_frobenius())
128

129
    chain_v = _chain_to_root(E_v)
130
    chain_b = _chain_to_root(E_b)
131

132
    pos_v = {int(c.j_invariant()): i for i, (c, _) in enumerate(chain_v)}
133
    lca_i_b = None
134
    lca_j = None
135
    for i, (c, _) in enumerate(chain_b):
136
        jj = int(c.j_invariant())
137
        if jj in pos_v:
138
            lca_i_b = i
139
            lca_j = jj
140
            break
141
    if lca_i_b is None:
142
        raise RuntimeError("LCA 업슴")
143
    lca_i_v = pos_v[lca_j]
144

145
    plans = []
146
    for i in range(lca_i_v):
147
        _, idx = chain_v[i]
148
        plans.append(int(idx))
149

150
    js_b_segment = [int(c.j_invariant()) for c, _ in chain_b[: lca_i_b + 1]]
151
    js_down = list(reversed(js_b_segment))
152

153
    cur = chain_v[lca_i_v][0]
154
    for nxt_j in js_down[1:]:
155
        idx, nxt = _find_index_to(cur, nxt_j)
156
        plans.append(int(idx))
157
        cur = nxt
158

159
    return plans
160

161

162
def _recv_until(sock, marker, timeout_sec=120):
163
    deadline = time.time() + timeout_sec
164
    buf = b""
165
    while marker not in buf:
166
        try:
167
            chunk = sock.recv(4096)
168
        except socket.timeout:
169
            continue
170
        if not chunk:
171
            break
172
        buf += chunk
173
    return buf
174

175

176
def main():
177
    host = "last-flight.seccon.games"
178
    port = 5000
179
    if len(sys.argv) >= 2:
180
        host = sys.argv[1]
181
    if len(sys.argv) >= 3:
182
        port = int(sys.argv[2])
183

184
    with socket.create_connection((host, port), timeout=20) as sock:
185
        sock.settimeout(5.0)
186
        data = _recv_until(sock, b"Master, please input the flight plans > ", timeout_sec=180)
187
        text = data.decode(errors="replace")
188
        m1 = re.search(r"vulcan's planet is here\s*:\s*(\d+)", text)
189
        m2 = re.search(r"bell's planet is here\s*:\s*(\d+)", text)
190
        if not (m1 and m2):
191
            raise RuntimeError("failed to parse vulcan/bell from:\n%s" % text)
192

193
        vulcan = int(m1.group(1))
194
        bell = int(m2.group(1))
195

196
        plans = solve(vulcan, bell)
197
        payload = ", ".join(map(str, plans)).encode() + b"\n"
198
        sock.sendall(payload)
199

200
        out = b""
201
        deadline = time.time() + 120
202
        while time.time() < deadline:
203
            try:
204
                chunk = sock.recv(4096)
205
            except socket.timeout:
206
                continue
207
            if not chunk:
208
                break
209
            out += chunk
210
            if b"SIGNAL SAY:" in out or b"LOST THE SIGNAL" in out:
211
                break
212
        sys.stdout.write(out.decode(errors="replace"))
213

214

215
if __name__ == "__main__":
216
    main()

1
SECCON{You_have_made_your_wish_so_you_have_got_to_make_it_true}

[SECCON CTF 14] Last Flight writeup

TL;DR

Analysis

Exploit