<- SEKAICTF

マスタースパーク

12 minutes to read

We are given a SageMath script called challenge.sage:

from Crypto.Util.number import *
import os
from timeout_decorator import timeout, TimeoutError

load("GA.sage")

FLAG = os.getenv("FLAG")
secret = getPrime(256)
choice = set()


@timeout(60)
def T_T(p, primes, secret):

    assert isPrime(p)
    assert len(primes) > 3

    Fp = GF(p)
    Fp2.<j> =  GF(p ^ 2, modulus=x ^ 2 + 1)
    ls = len(factor(p + 1)) - 2

    m = ceil((sqrt(p) ** (1 / ls) - 1) / 2)
    alice_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
    bob_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
    EC = montgomery(Fp2, 0)
    P = EC.gens()[0]
    k = 1
    alice_pub, Q = group_action(p, primes, Fp, Fp2, 0, alice_priv, k * P)
    share_bob, Q = group_action(p, primes, Fp, Fp2, alice_pub, bob_priv, secret * Q)  
    bob_pub, P = group_action(p, primes, Fp, Fp2, 0, bob_priv, P)
    share_alice, P = group_action(p, primes, Fp, Fp2, bob_pub, alice_priv, P)
    return P, Q


def check(p):
    assert isPrime(p)
    assert p.bit_length() <= 96
    assert ((p + 1) // 4) % 2 == 1
    prime_list = []
    cnt = 0

    for p, i in factor((p + 1) // 4):
        assert not p in choice
        if i > 1:
            cnt += 1
            choice.add(p)
            assert int(p).bit_length() <= 32
        else:
            prime_list.append(p)
            choice.add(p)

    assert all([int(p).bit_length() <= 16 for p in prime_list])
    assert cnt == 1

    return prime_list


def main():
    while True:
        try:
            p = int(input("input your prime number or secret > "))
            if int(p).bit_length() == 256:
                if p == secret:
                    print(FLAG)
                    exit()
                print("not flag T_T")
            else:
                prime_list = check(p)
                P, Q = T_T(p, prime_list, secret)
                print(P.xy())
                print(Q.xy())
        except:
            print("T_T")
            exit()
main()

Moreover, we have GA.sage with some functions used by the main script:

from random import randint

# I received advice from Mitsu to write this program. I appreciate it very much  

def montgomery(Fp2, A):
    return EllipticCurve(Fp2, [0, A, 0, 1, 0])

def to_montgomery(Fp, Fp2, E, G):
    Ep = E.change_ring(Fp).short_weierstrass_model()
    a, b = Ep.a4(), Ep.a6()
    P.<x> = PolynomialRing(Fp)
    r = (x^3 + a*x + b).roots()[0][0]
    s = sqrt(3 * r^2 + a)
    if not is_square(s):
        s = -s
    A = 3 * r / s
    phi = E.isomorphism_to(EllipticCurve(Fp2, [0, A, 0, 1, 0]))
    return Fp(A), phi(G)

def group_action(p, primes, Fp, Fp2, pub, priv, G):
    E = montgomery(Fp2, pub)
    es = priv[:]
    while any(es):
        x = Fp.random_element()
        P = E.lift_x(x)
        s = 1 if P[1] in Fp else -1
        S = [i for i, e in enumerate(es) if sign(e) == s and e != 0]
        k = prod([primes[i] for i in S])
        Q = ((p + 1) // k) * P
        
        for i in S:
            R = (k // primes[i]) * Q
            if R.is_zero():
                continue
            phi = E.isogeny(R)
            E = phi.codomain()
            Q, G = phi(Q), phi(G)
            es[i] -= s
            k //= primes[i]
    return to_montgomery(Fp, Fp2, E, G)

Source code analysis

In this challenge, we are allowed to enter prime numbers, with some properties, that will be used for a key exchange protocol:

def main():
    while True:
        try:
            p = int(input("input your prime number or secret > "))  
            if int(p).bit_length() == 256:
                if p == secret:
                    print(FLAG)
                    exit()
                print("not flag T_T")
            else:
                prime_list = check(p)
                P, Q = T_T(p, prime_list, secret)
                print(P.xy())
                print(Q.xy())
        except:
            print("T_T")
            exit()

The key exchange protocol is implemented in T_T:

@timeout(60)
def T_T(p, primes, secret):

    assert isPrime(p)
    assert len(primes) > 3

    Fp = GF(p)
    Fp2.<j> =  GF(p ^ 2, modulus=x ^ 2 + 1)
    ls = len(factor(p + 1)) - 2

    m = ceil((sqrt(p) ** (1 / ls) - 1) / 2)
    alice_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
    bob_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
    EC = montgomery(Fp2, 0)
    P = EC.gens()[0]
    k = 1
    alice_pub, Q = group_action(p, primes, Fp, Fp2, 0, alice_priv, k * P)
    share_bob, Q = group_action(p, primes, Fp, Fp2, alice_pub, bob_priv, secret * Q)  
    bob_pub, P = group_action(p, primes, Fp, Fp2, 0, bob_priv, P)
    share_alice, P = group_action(p, primes, Fp, Fp2, bob_pub, alice_priv, P)
    return P, Q

CSIDH

As can be seen, it defines an elliptic curve over $\mathbb{F}_{p^2}$. Specifically, this is a supersingular elliptic curve. Then, the key exchange protocol is based on group actions. Therefore, this is a CSIDH protocol. In fact, the group_action function is the same CSIDH uses:

def group_action(p, primes, Fp, Fp2, pub, priv, G):
    E = montgomery(Fp2, pub)
    es = priv[:]
    while any(es):
        x = Fp.random_element()
        P = E.lift_x(x)
        s = 1 if P[1] in Fp else -1
        S = [i for i, e in enumerate(es) if sign(e) == s and e != 0]  
        k = prod([primes[i] for i in S])
        Q = ((p + 1) // k) * P
        
        for i in S:
            R = (k // primes[i]) * Q
            if R.is_zero():
                continue
            phi = E.isogeny(R)
            E = phi.codomain()
            Q, G = phi(Q), phi(G)
            es[i] -= s
            k //= primes[i]
    return to_montgomery(Fp, Fp2, E, G)

To learn more about isogeny-based cryptography, I definitely recommend CryptoHack.

In brief, Alice’s private key is a list of random integers between $-m$ and $m$. The CSIDH protocol uses this list to walk from a base elliptic curve $E_0$ to another elliptic curve $E_a$ by computing several isogenies. Bob does the same with his private key to walk from $E_0$ to $E_b$. The public keys are the Montgomery coefficient of the elliptic curves $E_a$ and $E_b$. Then, Alice can use her private key to walk from $E_b$ to $E_{ba}$, whereas Bob uses his private key to walk from $E_a$ to $E_{ab}$. Both end elliptic curves are the same, so the shared secret is the Montgomery coefficient of the curves.

I have left a lot of concepts to explain about CSIDH and isogenies, but we don’t need to actually know them to solve this challenge. Just keep in mind that an isogeny is a homomorphism between two supersingular elliptic curves.

Solution

If we take a closer look at T_T, we see that the actual CSIDH public values from Alice and Bob are not returned from the function:

    EC = montgomery(Fp2, 0)
    P = EC.gens()[0]
    k = 1
    alice_pub, Q = group_action(p, primes, Fp, Fp2, 0, alice_priv, k * P)
    share_bob, Q = group_action(p, primes, Fp, Fp2, alice_pub, bob_priv, secret * Q)  
    bob_pub, P = group_action(p, primes, Fp, Fp2, 0, bob_priv, P)
    share_alice, P = group_action(p, primes, Fp, Fp2, bob_pub, alice_priv, P)
    return P, Q

Instead, we are given two points $P$ and $Q$ that are transformed by the isogenies. Let’s define the isogenies:

$$ \phi_a: E_0 \to E_a \qquad \phi_b: E_0 \to E_b $$

Isogenies

Following the key exchange protocol, the above lines of SageMath code can be expressed in math terms as:

$$ \begin{split} {}^{(1)} \quad & Q \leftarrow \phi_a(k \cdot P) \\ {}^{(2)} \quad & Q \leftarrow \phi_b(\mathrm{secret} \cdot Q) \\ \\ {}^{(3)} \quad & P \leftarrow \phi_b(P) \\ {}^{(4)} \quad & P \leftarrow \phi_a(P) \\ \end{split} $$

  • In ${}^{(1)}$, we know that $k = 1$ and that $P$ is a generator of $E_0$; therefore, $Q \in E_a$
  • In ${}^{(2)}$, since $Q \in E_a$, then $\mathrm{secret} \cdot Q \in E_a$ as well. Then, after applying $\phi_b$, we get $Q \in E_{ab}$
  • In ${}^{(3)}$, we know $P \in E_0$, so when applying $\phi_b$, we get $P \in E_b$
  • In ${}^{(4)}$, we know $P \in E_b$, so when applying $\phi_a$, we get $P \in E_{ab}$

So, in the end, the points $P$ and $Q$ that are given to us belong to $E_{ab}$. As a result, we are able to compute the parameters of the curve equation. Specifically, we can use a single point to get the Montgomery coefficient $A$:

$$ P_\mathrm{y}^2 = P_\mathrm{x}^3 + A P_\mathrm{x}^2 + P_\mathrm{x} \iff A = (P_\mathrm{y}^2 - P_\mathrm{x}^3 - P_\mathrm{x}) \cdot (P_\mathrm{x}^2)^{-1} $$

Therefore, we can define $E_{ab}$. Now, we are interested in finding $\mathrm{secret}$, which is a value we need to know in order to get the flag:

FLAG = os.getenv("FLAG")
secret = getPrime(256)

# ...

def main():
    while True:
        try:
            p = int(input("input your prime number or secret > "))  
            if int(p).bit_length() == 256:
                if p == secret:
                    print(FLAG)
                    exit()

Notice that the $Q$ we have from the T_T function is related to the initial $P$ point (the generator of $E_0$), let’s actually label it as $P_G$:

$$ Q = \phi_b(\mathrm{secret} \cdot \phi_a(k \cdot P_G)) $$

Since $\phi_a$ and $\phi_b$ are isogenies (group homomorphisms), point addition is preserved (and also multiplication by scalar), so

$$ \begin{split} Q & = \phi_b(\mathrm{secret} \cdot \phi_a(k \cdot P_G)) \\ & = \phi_b(\mathrm{secret} \cdot k \cdot \phi_a(P_G)) \\ & = (\mathrm{secret} \cdot k) \cdot \phi_b(\phi_a(P_G)) \\ \end{split} $$

Further, since $k = 1$ we can simplify it to $Q = \mathrm{secret} \cdot \phi_b(\phi_a(P_G))$.

Then, notice that the $P$ returned by T_T is just $P = \phi_a(\phi_b(P_G))$. It looks similar to the previous $Q$ expression, but the order of the isogenies is reversed. However, we are talking about CSIDH, where the “C” stands for commutative, so $\phi_a(\phi_b(P_G)) = \phi_b(\phi_a(P_G))$.

Discrete logarithm

As a result, we have:

$$ \begin{cases} P = \phi_a(\phi_b(P_G)) \\ Q = \mathrm{secret} \cdot \phi_b(\phi_a(P_G)) \end{cases} \quad \Longrightarrow Q = \mathrm{secret} \cdot P $$

So, the challenge reduces to solving a discrete logarithm over $E_{ab}$! This one is easy to solve because the curve is supersingular, so the order of the curve is smooth (it has many small factors). An algorithm like Pohlig-Hellman will find the solution pretty quickly. In SageMath, we can simply use the log method

Prime generation

We have skipped one part of the challenge, that has to do with the primes we can send to the server:

def check(p):
    assert isPrime(p)
    assert p.bit_length() <= 96
    assert ((p + 1) // 4) % 2 == 1
    prime_list = []
    cnt = 0

    for p, i in factor((p + 1) // 4):
        assert not p in choice
        if i > 1:
            cnt += 1
            choice.add(p)
            assert int(p).bit_length() <= 32
        else:
            prime_list.append(p)
            choice.add(p)

    assert all([int(p).bit_length() <= 16 for p in prime_list])  
    assert cnt == 1

    return prime_list

As can be seen, the primes must be $p < 2^{96}$ and also $\frac{p + 1}{4} \mod{2} = 1$. This means that

$$ \frac{p + 1}{4} = 2 \cdot n + 1 \iff p + 1 = 8 n + 4 \iff p = 8n + 3 $$

Then, the server takes the prime factors of $\frac{p + 1}{4}$ and adds them to a set called choice. For prime factors that appear more than once (the exponent is greater than $1$), the counter cnt is increased and the prime factor must be less than $2^{32}$. On the other hand, if the prime factor appears once, it is appended to prime_list. At the end, the function checks that all primes in prime_list are less than $2^{16}$ and that cnt equals 1.

So, we see that the prime $p$ must have the following structure (a bit more restrictive than before):

$$ p = 4 \cdot q_1 \cdot q_2 \cdots q_l \cdot r^e - 1 $$

Where all $q_i$ and $r$ are odd prime numbers and $e$ is some exponent greater than $1$, so that

$$ \frac{p + 1}{4} = q_1 \cdot q_2 \cdots q_l \cdot r^e \equiv 1 \pmod{2} $$

Notice also that $l > 3$, because it is verified in T_T:

@timeout(60)
def T_T(p, primes, secret):  

    assert isPrime(p)
    assert len(primes) > 3

    # ...

The way I generated these prime numbers is not so interesting, since I just used random prime numbers within the range we are allowed and checked if the prime factors were already in the choice set. I also used $l = 4$ and $e = 2$ for simplicity:

def gen_prime():
    global choice
    prev_choice = set(choice)

    while True:
        p = 4 * prod(random_prime(2 ** 8) for _ in range(4)) * random_prime(2 ** 14) ** 2 - 1  
        try:
            check(p)
            return p
        except AssertionError:
            choice = set(prev_choice)

CRT

Finally, we are able to send a known prime and solve the discrete logarithm $Q = \mathrm{secret} \cdot P$ on the curve $E_{ab}$, which we can recover using one point.

However, $\mathrm{secret}$ is a 256-bit number, whereas the primes we are sending are at most 96-bit numbers. Therefore, we will need to solve several discrete logarithms using different primes. With all the intermediate results, we can use the CRT to join them all and find the $\mathrm{secret}$ value (this is actually a kind of Pohlig-Hellman algorithm).

Implementation

First, we connect to the instance, define some constants, send a prime number and get the points $P$ and $Q$:

io = get_process()

dlogs, mods = [], []

for _ in range(8):
    p = gen_prime()
    Fp = GF(p)
    Fp2 = GF(p ** 2, modulus=[1, 0, 1], names='j')
    j = Fp2.gens()[0]

    io.sendlineafter(b'input your prime number or secret > ', str(p).encode())
    io.recvuntil(b'(')
    Px = j * int(io.recvuntil(b'*j + ', drop=True).decode()) + int(io.recvuntil(b', ', drop=True).decode())  
    Py = j * int(io.recvuntil(b'*j + ', drop=True).decode()) + int(io.recvuntil(b')', drop=True).decode())
    io.recvuntil(b'(')
    Qx = j * int(io.recvuntil(b'*j + ', drop=True).decode()) + int(io.recvuntil(b', ', drop=True).decode())
    Qy = j * int(io.recvuntil(b'*j + ', drop=True).decode()) + int(io.recvuntil(b')', drop=True).decode())

Now, we find the curve $E_{ab}$:

    A = (Py ** 2 - Px ** 3 - Px) / (Px ** 2)
    Eab = EllipticCurve(Fp2, [0, A, 0, 1, 0])  

    P = Eab(Px, Py)
    Q = Eab(Qx, Qy)

After that, we can solve the discrete logarithm and append the result and the order to dlogs and mods for later use with the CRT:

    dlogs.append(Q.log(P))  
    mods.append(P.order())

This process repeats 8 times, which is enough information. At this point, we can compute the CRT. Notice that we need to consider positive and negative values of the intermediate results:

for signs in product((-1, 1), repeat=len(dlogs)):
    try:
        secret = crt([s * d for s, d in zip(signs, dlogs)], mods)

        if secret.bit_length() != 256:
            continue

        io.info(f'Testing {secret = }')
        io.sendlineafter(b'input your prime number or secret > ', str(secret).encode())  

        if 'not flag T_T' not in (msg := io.recvlineS()):
            io.success(msg)
            break
    except ValueError:
        pass

I’m not very sure why this is necessary, but I believe it is because $\phi_a(\phi_b(P))$ is not always the same as $\phi_b(\phi_a(P))$, just with a sign difference.

Flag

If we run the script, we will get the flag:

$ python3 solve.py master-spark.chals.sekai.team 1337
[+] Opening connection to master-spark.chals.sekai.team on port 1337: Done
[+] Starting local process '/usr/bin/bash': pid 109
[*] Stopped process '/usr/bin/bash' (pid 109)
[*] Testing secret = 92697392149653184017438929759734443022953789135986999376605724801638735010341
[+] SEKAI{(h0w_4b0u7_70uh0u_pr0j3c7??_OH_WAIT_Help_me,ERINNNNNNNNNNNN!!_https://youtu.be/X8z23t428kU?si=4ufTbouKxwQ6Lbhm}  
[*] Closed connection to master-spark.chals.sekai.team port 1337

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