Elliptic Labyrinth Revenge
5 minutes to read
This challenge is Elliptic Labyrinth modified to force CTF players use the intended way to solve the challenge.
Finding differences
The provided source code is a bit different:
import os, json
from hashlib import sha256
from random import randint
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all_cmdline import *
from secret import FLAG
class ECC:
def __init__(self, bits):
self.p = getPrime(bits)
self.a = randint(1, self.p)
self.b = randint(1, self.p)
def gen_random_point(self):
return EllipticCurve(GF(self.p), [self.a, self.b]).random_point()
def menu():
print("1. Get parameters of path")
print("2. Try to exit the labyrinth")
option = input("> ")
return option
def main():
ec = ECC(512)
A = ec.gen_random_point()
print("This is the point you calculated before:")
print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))
while True:
choice = menu()
if choice == '1':
r = randint(ec.p.bit_length() // 3, 2 * ec.p.bit_length() // 3)
print(
json.dumps({
'p': hex(ec.p),
'a': hex(ec.a >> r),
'b': hex(ec.b >> r)
}))
elif choice == '2':
iv = os.urandom(16)
key = sha256(long_to_bytes(pow(ec.a, ec.b, ec.p))).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = pad(FLAG, 16)
print(
json.dumps({
'iv': iv.hex(),
'enc': cipher.encrypt(flag).hex()
}))
else:
print('Bye.')
exit()
if __name__ == '__main__':
main()
This time, there is no such option to request random points in the curve. We are just provided with a single random point at the beginning:
A = ec.gen_random_point()
print("This is the point you calculated before:")
print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))
Then we only have option 1, which shows the prime number $p$ and the most significant bits of $a$ and $b$ (as in Elliptic Labyrinth):
if choice == '1':
r = randint(ec.p.bit_length() // 3, 2 * ec.p.bit_length() // 3)
print(
json.dumps({
'p': hex(ec.p),
'a': hex(ec.a >> r),
'b': hex(ec.b >> r)
}))
Option 2 is the same as option 3 in Elliptic Labyrinth. It uses $\mathrm{key} = \mathrm{SHA256}\left(a^b \mod{p}\right))$ for AES and encrypts the flag:
elif choice == '2':
iv = os.urandom(16)
key = sha256(long_to_bytes(pow(ec.a, ec.b, ec.p))).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = pad(FLAG, 16)
print(
json.dumps({
'iv': iv.hex(),
'enc': cipher.encrypt(flag).hex()
}))
So the objective is to find parameters $a$ and $b$ given a single point of the curve, $p$ and the most significant bits of $a$ and $b$.
Coppersmith method
Let’s put the information we have in mathematical terms. Let’s define $a_H$ and $b_H$ as the most significant bits of $a$ and $b$, respectively. Hence, we know that $a = 2^r a_H + a_L$ and $b = 2^r b_H + b_L$ for some $170 \leqslant r \leqslant 340$. If we are able to find $r$, $a_L$ and $b_L$, we can find $a$ and $b$.
The only equation we can use is the curve’s equation:
$$ y^2 = x^3 + ax + b \mod{p} $$
Substituting $a$ and $b$ we get:
$$ y^2 = x^3 + (2^r a_H + a_L) x + 2^r b_H + b_L \mod{p} $$
Notice that the unknowns are mainly $a_L$ and $b_L$ (we can do a brute force attack on $r$ if needed).
Hence, we can define a polynomial $P(t, z)$ that satisfies $P(a_L, b_L) = 0 \mod{p}$:
$$ P(t, z) = xt + z - (y^2 + x^3 + 2^r a_H + 2^r b_H) $$
As it happened in Bank-er-smith, when having most significant bits of a number known, a typical method to apply is Coppersmith (which uses LLL lattice reduction under the hood). This time, the problem is that we have a bivariate polynomial. But there are Coppersmith method implementations for bivariate polynomials and even for multivariate polynomials.
Finding an implementation
The most used implementations are defund and ubuntor. The flag in Elliptic Labyrinth made reference to defund’s implementation, but I didn’t manage to make it work properly (neither ubuntor).
In the end, I found this GitHub Gist with yet another Coppersmith method implementation for bivariate polynomials that worked most of the times.
Python implementation
Then, we only have to collect the information from the challenge and apply Coppersmith method trying to guess $r$ (we can do a bit of brute force):
def main():
io = get_process()
io.recvline()
data = json.loads(io.recvline().decode())
x_p, y_p = int(data['x'], 16), int(data['y'], 16)
io.sendlineafter(b'> ', b'2')
data = json.loads(io.recvline().decode())
iv, enc = bytes.fromhex(data['iv']), bytes.fromhex(data['enc'])
a_highs, b_highs = [], []
for _ in range(50):
io.sendlineafter(b'> ', b'1')
data = json.loads(io.recvline().decode())
p = int(data['p'], 16)
a_highs.append(int(data['a'], 16))
b_highs.append(int(data['b'], 16))
aH, bH = sorted(a_highs)[-1], sorted(b_highs)[-1]
r_mean = 512 - aH.bit_length()
found = False
for r in range(r_mean - 5, r_mean + 5):
PR = PolynomialRing(Zmod(p), names='x,y')
x, y = PR.gens()
S = y_p ** 2 - x_p ** 3 - (aH << r) * x_p - (bH << r)
pol = x_p * x + y - S
try:
aL, bL = bivariate(pol, 2 ** r, 2 ** r)
a, b = int(aL + (aH << r)), int(bL + (bH << r))
if (y_p ** 2 - x_p ** 3 - a * x_p - b) % p == 0:
found = True
break
except IndexError:
pass
if found:
key = sha256(long_to_bytes(pow(a, b, p))).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
io.success(unpad(cipher.decrypt(enc), 16).decode())
else:
io.failure('Not found')
Notice that I collect a few values for $a_H$ and $b_H$ and I choose the ones that are bigger, so that Coppersmith method is more likely to succeed.
Flag
When running the script, it will fail some times, but it will eventually succeed:
$ python3 solve.py 165.232.108.240:31791
[+] Opening connection to 165.232.108.240 on port 31791: Done
[-] Not found
[*] Closed connection to 165.232.108.240 port 31791
$ python3 solve.py 165.232.108.240:31791
[+] Opening connection to 165.232.108.240 on port 31791: Done
[+] HTB{y0u_5h0u1d_h4v3_u53d_c00p325m17h}
[*] Closed connection to 165.232.108.240 port 31791
The full script can be found in here: solve.py.