May Contain Hackers 2022 - Curvy
Elliptic curve discrete logarithm with unknown curve parameters and unknown y coordinate.
Description
The road to understanding cryptography can be curvy. Connect to curvy.ctf.zone on port 6011 and show you know how to get to 1337.
This challenge has been provided by https://squeamishossifrage.eu/. Visit the site for more Crypto challenges! (after finishing the MCH2022 CTF of course ;-) )
Details
Points: 400
Category: Crypto
Validations: 5
Solution
The connection to the service gave some information:
Since you are at MCH and might think you are a hacker, maybe you can tell us how many steps it takes to get to 1337?
2
Nope if you take 2 steps you will end up at 10246385595908412093322394614482812
According to the name, we were on the lead to deal with elliptic curve. We collected several points:
x1 = 1
x2 = 10246385595908412093322394614482812
x3 = 39363994084598900187252501570838981
x4 = 21407548750102312410625794491436912
x5 = 32685866221368843545964725685301333
However, we were given a single coordinate and we did not know if it was $x$ or $y$. We tried to figure out the maximum value possible with a binary search:
import socket
idx = 116
bound = (1 << idx)
previous = 0
for i in range(116):
bound = bound | (1 << idx)
print(f"Testing {hex(bound)}")
s = socket.socket()
s.connect(('curvy.ctf.zone', 6011))
print (s.recv(1024).decode())
s.send(str(bound).encode())
rsp = s.recv(1024)
print(rsp)
if rsp == b'Sorry but you are not even on the right road.\n':
bound = previous
else:
previous = bound
idx -= 1
s.close()
We and up with the value $54283205379427155782089046839411710$ and we remarked that giving this value as input circle back to the output 1. In addition $p=54283205379427155782089046839411711$ (the value plus one) is prime. Thus were a bit confused and we could not really figure out what this stuff was doing. Finally one of our team mate figure out that following the link given in description give the source code of the challenge. It was definitly an elliptic curve and we only got the x coordinate. We figure out afterwards that we could also verify this hypothesis by using the double formulas. To compute the coordinate $x_{2P}$ of $2\cdot P$ we have $x_{2P} = \lambda ^ 2 - 2x_P$. Thus we could have computed $x_{2P} + 2x_P = \lambda ^ 2$ for several points and test that it is a square.
Nevertheless, we used the doubling formulas to recover $a$ and $b$. We have $x_{2P} = \lambda ^ 2 - 2x_P = ((3x_P + 1) (2y_P)^{-1})^2 - 2x_P$. Then replacing $y_P$ by the curve equation gives $x_{2P} = ((3x_P + 1)^2 (4(x_P^3 + ax + b)))^{-1}) - 2x_P$. Thus with two equations and three points: $x_1$,$x_2$ and $x_4$ we are able to solve the problem for $a$ and $b$. Finally we could build the elliptic curve and check if everything was fine:
sage: a = 49850651047495986645822557378918223
sage: b = 21049438014429831351540675253466229
sage: E = EllipticCurve(GF(p),[a,b])
sage: G = E(1,sqrt(F(a+ b+1)))
sage: Q = E(1337,sqrt(F(a*1337+ b+1337^3)))
sage: (2*G)[0] == x2
True
We just needed to solve the discrete logarithm for the point $Q = (1337, 38690346723225979506289175587604733)$. We remarked that the order of the curve is equal to the prime $p$ and thus the curve is super singular. Then the Smart attack applies in this case and allows to solve the discrete logarithm in a couple of seconds:
$ sage solve.sage 1 ✘ 4s
x = 4189812079514248908161689197409449
x*G = (1337 : 38690346723225979506289175587604733 : 1)
Giving the exponent to the program outputs the flag. Here is the full solution.