<- ECSC 2023

Kernel searcher

6 minutes to read

I have a super secret isogeny. Wanna know where your point ends up? Just send me your favourite coordinates.

Challenge contributed by CryptoHack

Challenge files:

We are given a SageMath script that hides the flag under an isogeny and allows us to evaluate the isogeny in any point we desire.

Source code analysis

The relevant part of the script is this one:

import json
from Crypto.Util.number import bytes_to_long

proof.all(False)

A, B = 2**216, 3**137
p = A * B - 1

F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [0, 6, 0, 1, 0])

# Torsion Basis for E[A]
P, Q = canonical_torsion_basis(E, A)

import os
flag = os.environ.get("FLAG", "ECSC{fake_flag_for_testing}").strip().encode()
ker = P + bytes_to_long(flag) * Q
challenge_isogeny = E.isogeny(
    ker, algorithm="factored", model="montgomery"
)

def accept_point(data):
    data = json.loads(data)
    try:
        x0 = int(data["x0"], 16)
        x1 = int(data["x1"], 16)
        x = F([x0, x1])
    except Exception as e:
        print(e)
        return {"error": "Invalid Fp2 value"}
    
    if not E.is_x_coord(x):
        return {"error": "Invalid Point"}

    P = E.lift_x(x)
    imP = challenge_isogeny(P)
    return json.dumps({"x0": hex(imP[0][0]), "x1": hex(imP[0][1])})

def main():
    print(f"Welcome to my isogeny factory!")
    print(f"My isogeny is so secret, I'll let you evaluate any point you like!")
    while True:
        data = input("Send the point you wish to evaluate: ")
        output = accept_point(data)
        print(output)

if __name__ == "__main__":
    main()

Basically, the server uses a given elliptic curve on , where .

The elliptic curve is defined as:

Notice that is a finite field where the elements are polynomials on of degree . This elliptic curve is supersingular.

Then, the server finds two points and whose order is . With those points, the server defines the kernel of the isogeny as , where is the flag.

Isogeny

An isogeny is just a homomorphism between two (supersingular) elliptic curves. And the kernel of a homomorphism is the set of elements that are mapped to the identity element.

Let’s denote the isogeny by , so we have that . Since the kernel is defined by a single point, any multiple of that point is in the kernel (including the point at infinity). Therefore, for any .

Moreover, since is a group homomorphism, it follows that . So, we have

Solution

We can obtain by solving the elliptic curve discrete logarithm problem (ECDLP). The issue here is that we still don’t know the codomain of the isogeny.

Finding curve parameters

After a bit of research and testing, we can see that the codomain is an elliptic curve with the following structure:

For some that depends on .

We are able to obtain that value if we know a point of the codomain curve.

Here, I tried some interesting points. For instance, I sent the point to the server, and the output was a point . The server only outputs the coordinate, but when testing locally, I saw that the coordinate was always equal to . Hence, we can solve the codomain curve equation for :

io = get_process()

io.sendlineafter(b'Send the point you wish to evaluate: ',
                 json.dumps({'x0': '0', 'x1': '0'}).encode())
data = json.loads(io.recvline().decode())
x0, x1 = int(data.get('x0'), 16), int(data.get('x1'), 16)
X = F([x0, x1])
C = (- X ** 3 - X) / (X ** 2)

EE = EllipticCurve(F, [0, C, 0, 1, 0])

Discrete logarithm

And now we are ready to solve the discrete logarithm with the image points of and :

io.sendlineafter(b'Send the point you wish to evaluate: ',
                 json.dumps({'x0': hex(P[0][0]), 'x1': hex(P[0][1])}).encode())
data = json.loads(io.recvline().decode())
x0, x1 = int(data.get('x0'), 16), int(data.get('x1'), 16)
imP = EE.lift_x(F([x0, x1]))

io.sendlineafter(b'Send the point you wish to evaluate: ',
                 json.dumps({'x0': hex(Q[0][0]), 'x1': hex(Q[0][1])}).encode())
data = json.loads(io.recvline().decode())
x0, x1 = int(data.get('x0'), 16), int(data.get('x1'), 16)
imQ = EE.lift_x(F([x0, x1]))
io.close()

And this is easy to solve because the order of and is , a power of . Therefore, the image points have also a power of as order.

Let’s say and . We want to solve the equation

Since the order of and are powers of , we can express in binary:

If we multiply by the order of , we get , if we divide the order by and multiply, we have

Now, if is the point at infinity (the zero element), we know that , otherwise, .

After that, we can see that

Now we multiply both sides by , and we have

Again, if is zero, then , otherwise .

Then,

And we multiply by to determine . We continue all the process until we find all bits from to :

def dlog(G, nG):
    i = -1
    bits = []
    order = A

    while order:
        i += 1
        order //= 2

        if order * (nG - (sum(bits)) * G) != 0 * G:
            bits.append(2 ** i)

    return sum(bits)


d = dlog(imQ, -imP)
io.success(bytes.fromhex(hex(int(d))[2:]).decode())

Flag

And finally, we find the flag:

$ python3 solve.py
[+] Starting local process '/usr/bin/sage': pid 7514
[*] Stopped process '/usr/bin/sage' (pid 7514)
[+] ECSC{learning_to_isogeny}

The full script can be found in here: solve.py.