Solved after the CTF ended, with @tjbecker (PPP)
Same as blind, but the order of GF(p) isn't smooth anymore.
I found another solution which is more efficient.
- Search a elliptic curve with smooth order
- Recover the index of y using Pohlig-hellman.
- Recover the index of y in each subgroup with naive discrete log.
- Calculate y.
After the CTF ended, there's some discussion of this challenge.
00:29 hellmann| for blinder my guess would be to construct an elliptic curve with small factor in the order and perform dlp there, using oracle operations to implement the ecc group 00:29 _0xbb_| you need to discuss that with y7 later^^ 00:30 hellmann| looking forward :) 00:42 tjbecker| hellmann: that was my approach, but I couldn't get it down to only 0x4000 queries 00:43 tjbecker| would love to see what optimizations I was missing, if that was the intended solution 00:43 hellmann| how close could you get? 00:44 tjbecker| I needed roughly 0x20000, which is 8x too many 00:45 hellmann| still sounds cool, how many curves did you use? what were the factors 00:47 tjbecker| a,b = (242251381217038, 29739910446124) 00:47 tjbecker| gives a curve of order 2 * 3 * 11 * 13 * 17 * 67 * 71 * 131 * 173 * 179 00:48 tjbecker| (which is also nice because it's square free) 00:48 hellmann| nice, I thought about using many curves 00:48 tjbecker| maybe that's what I was missing 00:48 hellmann| maybe with montgomery arithmetic it should be good enough? 00:48 tjbecker| more liekly, I was just bad at optimizing point addition 00:50 tjbecker| yeah I also thought about using Edwards curves, but got too tired to stay up to try it 00:50 tjbecker| I was happy enough with a solution which was much better than sqrt(p) 01:01 sasdf| tjbecker: How do you construct that curve? 01:02 tjbecker| just try random (a,b) pairs, constructing the curve over GF(p) and take the one with the smoothest order 01:02 tjbecker| took like 10 minutes to find that curve
The method using Elliptic curve sounds promising. After @tjbecker gave me his script, we work on optimizing the algorithm together.
Here's the summary of our algorithm:
- Let C = EllipticCurve, T = Target y, G = Generator, o = C.cardinality().
P = C.lift_x(T).
- Similar to what we do in
blind, For each factor f in o:
X = (o / f) G
Y = (o / f) P
i X = Y, which means
P.order() % f = i.
P.order()using Pohlig-Hellman algorithm.
- Calculate T
We can't encrypt arbitary integer directly. We need to construct them using 1 and add operation.
First, we calculate a list of power of two (using double and 1), and we can sum those needed bits to construct arbitary number.
Offline calculation of operation on G
This is our first optimization.
Operation on the elliptic curve is much more expensive than embedding an integer, so we calculated all operation about the generator (i.e.
X = (o / f) G and
i X) offline, and then embed the result using previous algorithm.
For comparsion between
i X and
Y, we only compare their y coordinate.
For square-and-multiply (or double-and-add), we use NAF form instead of typical binary form to minimize the operation count.
When calculating double-and-add, we have to sum a list of numbers. If we sum them sequentially:
result = reduce(add, points, zero)
We (almost) won't hit the cache in add operation.
Instead, we add up neighbors first:
a, b, c, d, e, f, g -> (a+b), (c+d), (e+f), g
We will have a better chance that hit the cache at first round.
For Point multiplication (i.e.
Y = (o / f) P), we know all the operands in advance. We use a greedy algorithm: add up most common pair first. It's not optimal, but much better then merging neighbors first.
A = 0, 1, 2 B = 0, 1, 3 C = 0, 1, 4, 5, 6 D = 5, 6 With following order: Add(0, 1), Add(5, 6), Add(01, 2), Add(01, 3), Add(01, 4), Add(014, 56)
There're two operation using constant power:
inv = exp(x, p-2)
sqrt = exp(x, (p+1)/4)
p-2is a very bad constant when using square-and-multiply, because of it's binary representation:
111111111111111111111111111111111110101101001111. We have to sum all those 1 and that is a huge amount of operations.
Fortunately, we cat factor
123 * 2288414444759, which means we can calculate
exp(exp(x, 123), 2288414444759) instead.
And we can apply similar techniques to
Linear search v.s. Baby Step Giant Step
tjbecker implemented Baby Step Giant Step too. The algorithm has lower complexity, but it needs to run point addition
sqrt(f) times, which needs too much operations.
A better curve with linear search works better.
Search the curve
After we finish our algorithm, we can estimate the cost of each part:
Y = (o / f) Ptakes about 2000 operations of each
Ytakes about 24 operation of each test.
- Expectation of the needed tests to find
f / 2.
We can use the cost for ranking curves when searching. Here's the script we use to search the curve.
Now combining everything together, It's time for getting our flag :) Here's the script.
It uses about 13000 operations on localhost.
So where's the flag?
It seems that I have to find a server in Germany to get the flag...