May Contain Hackers 2022 - Curvy
This is the solution of the challenge “Squaring Off” given during the MCH CTF. It consisted in solving the 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:
|
|
According to the name, we were on the lead to deal with elliptic curve. We collected several points:
|
|
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:
|
|
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:
|
|
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:
|
|
Giving the exponent to the program outputs the flag. Here is the full solution.