A full year without a writeup? Never! 2025 is ending and it was such a full year, but playing with a:b is important, so here we are again. Still remote but I will join more in person next year >.<

Also, this is my first isogeny challenge except for training ones in Cryptohack, so I will try to explain the steps that were interesting for me.

crypto - Last Flight

Challenge

• Author: kanon
• Solves: 32
• Points: 166

I got split up from them. It is the final chance. Can you find a special flight?

This challenge deals with isogenies and asks us to walk a bit on an isogeny graph. Generally this should not be easy (CSIDH?) if we do not have additional information like where some points are mapped (SIDH attack) and if the graph is big enough/has no specific structures.

Challenge Details

The server defines a specific curve E and then starts to walk on the 2-isogeny graph “randomly” for 160 steps.

#server.sage

p = 4718527636420634963510517639104032245020751875124852984607896548322460032828353
j = 4667843869135885176787716797518107956781705418815411062878894329223922615150642

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]

The server performs an interstellar flight twice, one from E to “vulcan” and one from E to “bell”, then asks us to find the path from vulcan to bell.

#server.sage
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(", ")))

First Ideas

The first thing we noticed is that the number of jumps is not fixed. In particular, the 2-isogeny graph is 3-regular, so every time we have three directions we can jump to. In general, you would discard the direction you are coming from and choose randomly between the other two. In this case, instead, the code chooses randomly among the three directions, and if the direction is the wrong one it simply skips the jump. This means that the number of jumps is not fixed but has average value 2/3 * 160 = 105. A meet-in-the-middle attack on the graph would cost 2^53, not cryptographically safe but not breakable in 24 hours.

This is only the average cost for an attack. If we create a way to detect the number of effective jumps that happened during the interstellar flight efficiently, we could connect many times to the server to rerandomize the paths until both of them have a small number of effective jumps and the cost of the meet-in-the-middle attack becomes feasible.

To explore this idea we tried offline to see how the number of effective jumps behaves statistically, and we saw that you have a flight with 90-ish jumps every 100 attempts and we cannot go much below that. Estimating this a bit more means that we would need to connect to the server around 10,000 times, run the estimator for the number of effective jumps, and then run in parallel two meet-in-the-middle attacks of estimated hardness 2^45.

Suddenly this doesn’t seem like a good path anymore. Also, the server takes time to generate the two curves. We decided not to pursue this path. 30 minutes later: “a proof of work has been added to this challenge”. This is CLEARLY not the path. Back to the drawing board.

Volcanoes

Choosing “vulcan” as one of the names of the two planets was clearly a hint towards using isogeny volcanoes, so we gladly accept the hint and open the usual paper on isogeny volcanoes (HERE if you do not know the paper).

Small intro to this from a non-expert like myself, starting from scratch. If you take the graph of 2-isogenies in Zp, you have a graph that has as nodes elliptic curves and as edges 2-isogenies between them. The graph is 3-regular, so each curve is connected to three others via 2-isogenies. We can walk on this graph by starting from a curve, taking the codomain of one of the 2-isogenies starting from it and repeating the process with the new curve. As of now, we do not know many techniques to move on this graph except for this one, so computing the path between two arbitrary curves in this graph is generally difficult.

The structure of the connected components of this graph is that of a volcano. This means that there is a “top” cycle that connects some curves with each other, and from each of the nodes in this cycle there is a binary tree that goes down. By taking a curve E in this graph we can obtain information about the structure of this graph. In particular, by looking at the trace of Frobenius we can obtain information about the structure of the volcano.

Sage 10.7 helps us with these computations by allowing us to define easily the field $K:=\mathcal{Q}(\sqrt{t^2-4p})$, where $t:=p+1-ord(E)$, and to ask for its discriminant. We see that $K$ only has one class. In particular, this means that the volcano we are working with only has one point in the top cycle and is, in fact, a collection of three binary trees with the same root node.

Extra note: At this moment Drago lit up because this is quite rare and only happens because the discriminant is $163$ (times a power of two). Now, this is not really relevant to the solution of the challenge, but the fact that the number of classes of $K$ can be this low is due to the fact that $e^{\pi\sqrt{163}}$ is super close to an integer. Since he was really happy about this I will put a link to this HERE xD

Climbing Volcanoes

Why is this volcano structure useful for our solve? Well, it is easy to understand at which height of the volcano a curve is.

To be fast and efficient you could compute it with traces, polynomials, and similar things, but it was not too slow to simply ask Sage 10.7 to compute the endomorphism order of the curve and look at the conductor. From theory we know that the conductor is $2^{depth}$ where depth is the vertical position of the curve in the volcano.

This means that, if we look at the codomain of the 2-isogenies starting from a curve, and compute their depth, we can understand if we are moving up or down in the volcano. In particular, it is easy to create a path from a generic curve to a curve on the top cycle of the volcano.

In general, this is not enough to construct paths between two random curves because the size of this cycle is big enough to be similar to DLOG in big groups. In this case, instead, the cycle is super small (only one element)! So we can connect two curves by simply creating the path upwards for both of them and then considering the union of those paths.

Path of curves

To do this, we take the starting curve E that we are given and we compute its height. We notice that it is not in the cycle (depth=0) but it is immediately below (depth=1). We look at the codomains of the 2-isogenies and we walk upward by one to reach Eroot.

We now define a function that, given any curve, returns the path upward from that curve to Eroot.

#solve.sage

#Computing Eroot
E = EllipticCurve(GF(p), j=j)
print([A.codomain() for A in E.isogenies_prime_degree(2)])
print([A.codomain().endomorphism_order() for A in E.isogenies_prime_degree(2)])
Eroot = E.isogenies_prime_degree(2)[1].codomain()
jroot = Eroot.j_invariant()

#Computing path from curve to Eroot
def root_path(p_j):
    EE = EllipticCurve_from_j(p_j)
    OEE = EE.endomorphism_order()
    starting_cond = math.log(OEE.conductor(),2)
    
    path=[]
    cond=starting_cond
    tempE = EE
    while cond>0:
        print(cond)
        options = [A.codomain() for A in tempE.isogenies_prime_degree(2)]
        for i in range(len(options)):
            tempOEE = options[i].endomorphism_order()
            if math.log(tempOEE.conductor(),2)<cond:
                tempE = options[i]
                cond = math.log(tempOEE.conductor(),2)
                path.append(tempE)
                break

    return path

Now we can simply compute the two paths to the root and then we won! Easy, right?

Path of indexes

No, not that easy xD The math problem is over now but we still need to submit the solution in a way that the server accepts. As always, the easiest part is the most time-consuming for cryptographers, so I will spend some words on the pain I suffered—even if it is not caused by math but by code.

Right now we have the path between vulcan and bell as the j-invariant of all the curves that we cross along the way. The problem is that the server performs the interstellar flight by looking at the three possible isogenies from the current curve (as output of currentE.isogenies_prime_degree(2)) and uses the index $i$ to choose element $i$ of this list.

Now, one node represents a big class of curves that are isomorphic with each other (i.e., have the same j-invariant). The problem is that Sage returns the isogenies in a different order for different curves even if they are isomorphic with each other. This means that we need to recreate the path by walking on the EXACT curves that the server is walking on, and doing it on curves that are merely isomorphic is not enough.

By looking at the final check, we notice that the server starts from vulcan by considering the curve EllipticCurve_from_j(vulcan) and then always moves to the curve obtained as isogeny.codomain() from the $i$-th isogeny in curve.isogenies_prime_degree(2).

So, we recreate this exact procedure by taking the curve EllipticCurve_from_j(vulcan) and deciding the steps by looking at the j-invariant of the possible codomains of isogenies, then taking that codomain as the next curve and repeating.

It is not technically difficult, but it creates a difference between the math problem and the code that was painful for some time.

Final Code

#solve.sage

from pwn import *
import subprocess
import re
from multiprocessing import Pool

context.log_level = 'info'

def compute_root_path(j):
    return root_path(j)[0]

io = remote('last-flight.seccon.games', 5000)

# ------- Math things ----

p = 4718527636420634963510517639104032245020751875124852984607896548322460032828353
j = 4667843869135885176787716797518107956781705418815411062878894329223922615150642

E = EllipticCurve(GF(p), j=j)
Eroot = E.isogenies_prime_degree(2)[1].codomain()
jroot = Eroot.j_invariant()

# ---- PoW phase ----
while True:
    line = io.recvline().decode().strip()
    print("[*] recv:", line)
    if line.startswith("hashcash"):
        pow_line = line
        break

parts = pow_line.split()
bits = parts[1][3:]
resource = parts[2]

token = subprocess.check_output(
    ["hashcash", f"-mb{bits}", resource]
).strip()

io.recvuntil(b'hashcash token:')
io.sendline(token)

# ---- Parse server output ----
vulcan = None
bell = None

while vulcan is None or bell is None:
    line = io.recvline().decode().strip()
    print("[*] recv:", line)

    if "vulcan's planet is here :" in line:
        vulcan = int(re.search(r"\d+", line).group())
    elif "bell's planet is here :" in line:
        bell = int(re.search(r"\d+", line).group())

print("\n[+] Parsed planets:")
print("vulcan =", vulcan)
print("bell   =", bell)

# ---- Actual math solve ----
first_curves_half = root_path(vulcan)
second_curves_half = root_path(bell)

curves_path = first_curves_half[:-1] + second_curves_half[::-1]
j_path = [vulcan] + [A.j_invariant() for A in curves_path] + [bell]

full_index_path = jpath_to_index_path(j_path)

# ---- Sending things -----
io.recvuntil(b"Master, please input the flight plans > ")

payload = ", ".join(map(str, full_index_path))
print("[*] Sending:", payload[:80], "...")

io.sendline(payload.encode())

while True:
    try:
        print(io.recvline(timeout=2).decode(), end="")
    except EOFError:
        break