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
Also, notice that 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 straightforward way to solve this. However, we can use lattices. For instance,
The lattice spanned by the columns of
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
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
We will be able to find vector
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
Note that
So, we need to solve an elliptic curve discrete logarithm problem (ECDLP) to find
This time, the ECDLP is easy to solve because
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:
When solving an ECDLP, we don’t get
As a result, we will be able to join all the results using the Chinese Remainder Theorem (CRT) and finally find
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
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
.