Elliptic
Crypto challenge created by me for GCC CTF 2024
Elliptic
I made this challenge for GCC CTF 2024, it’s supposed to be medium difficulty.
The problem
The source code can be found here. The challenge implements a knapsack problem on elliptic curve points. The good thing is that we can choose the curve we work on.
The solution
The knapsack problem is a known problem over the numbers but not over elliptic curve points for which it’s not solvable faster than with bruteforce (because we can’t use lattices). So our goal is to transfer this problem to the integers.
But how can we get usable numbers out of elliptic curve points ?
It’s interesting to note that each point is a multiple of a point generator of the curve and if we add two of those points, the multipliers are added.
a*G + b*G = (a+b)*G
This is how we can transfer our problem to integers. However we still have to find those multiplier. Luckily we can choose our curve, but there are some restrictions.
We can’t directly use a curve with a smooth order because of the following check.
E = EllipticCurve(GF(p),[a,b])
G = E.gens()[0]
o = G.order()
l = factor(o)
assert int(l[-1][0]).bit_length() >= 0x56
We however can use other weak curves, either supersingular curves that are subject to the MOV attack or anomalous curves subject to the SMART attack.
The problem with the first type of curves is that the discrete logarithm we need to compute takes too much time to be computed over 40 times so we have to use the second one which is much faster.
This is because the MOV attack sends the point in GF(p^k) for p being the prime of the curve and k a small number, which is a structure a bit complex so a bit slow. Meanwhile the SMART attack sends the points in GF(p) where computations are much simpler.
So our plan :
If we try with a normal curve size like 128 bits it won’t work because the lattice will be too dense, so we need to create a curve with a big prime, I choose 768 bits and it works well.
Because I’m a bit lazy I decided to use this function to create the anomalous curve https://github.com/jvdsn/crypto-attacks/blob/master/shared/ecc.py#L62.
The SMART attack can be found on a lot of websites and forum and same thing for the knapsack problem.
Solve script
You can find the solve script here.
If you find any issue or have any question, dm me on discord stating the subject in the first message.