<- CRYPTO

Quadratic Points

7 minutes to read

We are provided with the server source code in Python:

from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG
from utils import EllipticCurve, find_valid_quadratic_coefficients

import sys
import signal


def get_input_with_timeout(prompt, timeout):
    def alarm_handler(signum, frame):
        print("\nTime limit exceeded. Exiting...")
        sys.exit()

    signal.signal(signal.SIGALRM, alarm_handler)
    signal.alarm(timeout)

    try:
        input_data = input(prompt).strip()
        return int(input_data)
    except KeyboardInterrupt:
        pass
    finally:
        signal.alarm(0)  # Disable the alarm

    return None


for i in range(7):
    x1, x2 = find_valid_quadratic_coefficients()
    print(f'Hello Cryptographer, please enter the coefficients of the quadratic equation to proceed, hint: a*x^2 + b*x + c == 0, x = {x1}\n')  

    ai = get_input_with_timeout("a: ", 2)
    bi = get_input_with_timeout("b: ", 2)
    ci = get_input_with_timeout("c: ", 2)

    res = ai * x1 ** 2 + bi * x1 + ci
    res *= 10 ** 13  # did you think I would be that careless?

    if int(res) != 0 or any(i == 0 or abs(i) > 60 for i in [ai, bi, ci]):
        print("Nope!")
        exit()

print("You passed the first test, now onto the second\n")

p = getPrime(40)
E = EllipticCurve(p, [bi, ci])
G = E.random_point()
flag = bytes_to_long(FLAG)
Gn = E.mul(flag, G)

print(f"G = {G.xy()}")
print(f"Gn = {Gn.xy()}")
print(f"p = {E.p}")

Source code analysis

First of all, the server asks us to find the coefficients for a quadratic polynomial with a given root (7 times):

for i in range(7):
    x1, x2 = find_valid_quadratic_coefficients()
    print(f'Hello Cryptographer, please enter the coefficients of the quadratic equation to proceed, hint: a*x^2 + b*x + c == 0, x = {x1}\n')  

    ai = get_input_with_timeout("a: ", 2)
    bi = get_input_with_timeout("b: ", 2)
    ci = get_input_with_timeout("c: ", 2)

    res = ai * x1 ** 2 + bi * x1 + ci
    res *= 10 ** 13  # did you think I would be that careless?

    if int(res) != 0 or any(i == 0 or abs(i) > 60 for i in [ai, bi, ci]):
        print("Nope!")
        exit()

We don’t know function find_valid_quadratic_coefficients, but we can guess it computes a random quadratic polynomial and returns the roots as x1 and x2.

Once we pass the first 7 questions, we get the following code where the server uses the flag:

print("You passed the first test, now onto the second\n")  

p = getPrime(40)
E = EllipticCurve(p, [bi, ci])
G = E.random_point()
flag = bytes_to_long(FLAG)
Gn = E.mul(flag, G)

print(f"G = {G.xy()}")
print(f"Gn = {Gn.xy()}")
print(f"p = {E.p}")

Here, we will need to solve an elliptic curve discrete logarithm problem, which won’t be difficult since the prime p is a 40-bit integer. But we will see it later.

First part

So, in math terms, we are given $x_1$, and we must find coefficients $a$, $b$, and $c$ such that:

$$ a x_1^2 + b x_1 + c = 0 $$

Also, notice that $a$, $b$, and $c$ are integers, since get_input_with_timeout casts to int:

def get_input_with_timeout(prompt, timeout):
    def alarm_handler(signum, frame):
        print("\nTime limit exceeded. Exiting...")  
        sys.exit()

    signal.signal(signal.SIGALRM, alarm_handler)
    signal.alarm(timeout)

    try:
        input_data = input(prompt).strip()
        return int(input_data)
    except KeyboardInterrupt:
        pass
    finally:
        signal.alarm(0)  # Disable the alarm

    return None

Integer linear relations

For each question, we have a single equation and three unknowns! There is no straight-forward way to solve this. However, we can use lattices. For instance,

$$ M = \begin{pmatrix} x_1^2 & x_1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}; \qquad M \cdot \begin{pmatrix} a \\ b \\ c \\ \end{pmatrix} = \begin{pmatrix} 0 \\ a \\ b \\ c \end{pmatrix} $$

The lattice spanned by the columns of $M$ contains a vector $(0, a, b, c)$, which is supposed to be short, because $0 < |a|, |b|, |c| \leqslant 60$:

    if int(res) != 0 or any(i == 0 or abs(i) > 60 for i in [ai, bi, ci]):  
        print("Nope!")
        exit()

Plus, we can increase the fact that vector $(0, a, b, c)$ is short by multiplying by $10^{13}$, like the server:

    res = ai * x1 ** 2 + bi * x1 + ci
    res *= 10 ** 13  # did you think I would be that careless?

So, we will be using the following matrix $M$:

$$ M = \begin{pmatrix} 10^{13} \cdot x_1^2 & 10^{13} \cdot x_1 & 10^{13} \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} $$

We will be able to find vector $(0, a, b, c)$ by reducing the lattice basis with LLL. This algorithm will output a basis of the same lattice, but with short vectors, and we expect $(0, a, b, c)$ to be in the reduced lattice basis. More information about this technique in:

Implementation

The above technique can be written in Python with some SageMath functions:

def find_integer_relation(x: float) -> tuple[int, int, int]:
    M = Matrix(QQ, [
        [x ** 2, x, 1],
        [1,      0, 0],
        [0,      1, 0],
        [0,      0, 1],
    ])

    M[0, :] *= 10 ** 13

    L = M.T.LLL()

    for row in L.rows():
        ai, bi, ci = map(int, row[1:4])
        res = ai * x ** 2 + bi * x + ci
        res *= 10 ** 13

        if int(res) == 0 and all(0 < abs(z) <= 60 for z in [ai, bi, ci]):  
            return ai, bi, ci

    return 0, 0, 0

Notice how we loop through the rows of the reduced matrix (SageMath does LLL in rows) until we find one that is valid for the server.

So, we repeat this process 7 times and we pass to the second part:

Second part

Let’s recall this part, which is simple:

p = getPrime(40)
E = EllipticCurve(p, [bi, ci])  
G = E.random_point()
flag = bytes_to_long(FLAG)
Gn = E.mul(flag, G)

print(f"G = {G.xy()}")
print(f"Gn = {Gn.xy()}")
print(f"p = {E.p}")

So, we are given $G$, $n \cdot G$ and $p$, where $G$ is a point in the elliptic curve $E$:

$$ E : y^2 = x^3 + b_i x + c_i \mod{p} $$

Note that $b_i$ and $c_i$ come from the last round of the previous part.

So, we need to solve an elliptic curve discrete logarithm problem (ECDLP) to find $n$ from $G$ and $n \cdot G$. We need this because $n$ is the flag as an integer value.

This time, the ECDLP is easy to solve because $p$ is a 40-bit prime, so algorithms like Baby-step Giant-step will finish pretty quickly. However, the problem is that the flag is not a 40-bit integer (5 bytes)…

Chinese Remainder Theorem

Here we must apply a trick that is quite common in CTF competitions, and it is to reconnect to the server. With this, we can pass the first part and get another sample for the flag.

In the end, we aim to get something like:

$$ \begin{cases} \mathrm{flag} \equiv n_1 \pmod{o(G_1)} \\ \mathrm{flag} \equiv n_2 \pmod{o(G_2)} \\ \dots\\ \mathrm{flag} \equiv n_k \pmod{o(G_k)} \\ \end{cases} $$

When solving an ECDLP, we don’t get $\mathrm{flag}$, but $n_i = \mathrm{flag} \mod{o(G_i)}$, and the order of $G_i$ a 40-bit integer (more or less). So, we need to get more samples with different points.

As a result, we will be able to join all the results using the Chinese Remainder Theorem (CRT) and finally find $\mathrm{flag}$. We will need to ensure that all orders $o(G_i)$ are coprime.

In order to implement it, we can define a function to connect to the server, pass the first part and then solve the ECDLP. We will return the values $n_i$ and $o(G_i)$:

def get_flag_order() -> tuple[Integer, Integer]:
    io = get_process()
    a = b = c = 0

    for r in range(7):
        round_prog.status(str(r + 1))
        io.recvuntil(b'x = ')
        x = float(io.recvlineS())
        a, b, c = find_integer_relation(x)

        if a == b == c == 0:
            io.close()
            return Integer(0), Integer(0)

        io.sendlineafter(b'a: ', str(a).encode())  
        io.sendlineafter(b'b: ', str(b).encode())
        io.sendlineafter(b'c: ', str(c).encode())

    io.recvuntil(b'G = ')
    Gx, Gy = literal_eval(io.recvlineS())
    io.recvuntil(b'Gn = ')
    nGx, nGy = literal_eval(io.recvlineS())
    io.recvuntil(b'p = ')
    p = literal_eval(io.recvlineS())
    io.close()

    E = EllipticCurve(GF(p), [b, c])
    G = E(Gx, Gy)
    nG = E(nGx, nGy)
    n = nG.log(G)
    order = G.order()
    return n, order

Next, we collect all samples and keep computing the CRT until we get the flag as HTB{...}:

round_prog = log.progress('Round')
samples_prog = log.progress('Samples')
flag_prog = log.progress('Flag')

flags, orders = [], []
flag = b''

while not flag.startswith(b'HTB{'):
    samples_prog.status(str(len(flags)))  

    try:
        f, o = get_flag_order()
    except EOFError:
        continue

    if f == o == 0:
        continue

    for oo in orders:
        if gcd(oo, o) != 1:
            break
    else:
        flags.append(f)
        orders.append(o)

        n = int(crt(flags, orders))
        flag = long_to_bytes(n)
        flag_prog.status(str(flag))

flag_prog.success(flag.decode())

Flag

At this point, we can get the flag (it might take around 2 minutes):

$ python3 solve.py 94.237.54.45:31855
[\] Round: 7
[0] Samples: 16
[+] Flag: HTB{th1s_h4s_t0_b3_4_l0ng_fl4g_f0r_CRT_purp0s3s___s0rry_1f_th4t_w4s_4nn0y1ng(:}

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