Elliptic Labyrinth
6 minutes to read
We are provided with the server source code in Python:
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 secret import FLAG
class ECC:
def __init__(self, bits):
while True:
self.p = getPrime(bits)
if self.p % 4 == 3:
break
self.a = randint(1, self.p)
self.b = randint(1, self.p)
def gen_random_point(self):
x = randint(2, self.p-2)
return (x, pow(x**3 + self.a*x + self.b, (self.p+1)//4, self.p))
def menu():
print("1. Get path parameters")
print("2. Try to exit the labyrinth")
option = input("> ")
return option
def main():
ec = ECC(512)
A = ec.gen_random_point()
print("This is your lucky point:")
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()
The server uses Elliptic Curve Cryptography (ECC), but it only generates a curve and uses the curve parameters to generate an AES key to encrypt the flag (so ECC is not actually used for encryption).
ECC background
Elliptic Curve Cryptography is a public-key cryptosystem, so there is a public key and a private key.
Let
Where
In ECC, the above elliptic curve is considered under a finite field (for example,
As a result, the points in the curve form an abelian group under addition:
- The operation is internal (i.e.
) - There is a unique identity element usually called
, such that . This is also known as “point at infinity” - Every point has a unique inverse point, that is
. We can also say that abusing additive notation - The operation is associative (and also commutative)
Since ECC is not used to encrypt information, I will leave the explanation here.
Finding curve parameters
We only have option 1
, which shows the prime number
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
uses
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
Coppersmith method
Let’s put the information we have in mathematical terms. Let’s define
The only equation we can use is the curve’s equation:
Substituting
Notice that the unknowns are mainly
Hence, we can define a polynomial
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. I didn’t manage to make any of them work properly.
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
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
Flag
When running the script, it will fail some times, but it will eventually succeed:
$ python3 solve.py 138.68.166.146:32398
[+] Opening connection to 138.68.166.146 on port 32398: Done
[-] Not found
[*] Closed connection to 138.68.166.146 port 32398
$ python3 solve.py 138.68.166.146:32398
[+] Opening connection to 138.68.166.146 on port 32398: Done
[+] HTB{w3_h0p3_th1s_0n3_h3lp3d_y0u_und3rst4nd_sm411_r00ts}
[*] Closed connection to 138.68.166.146 port 32398
The full script can be found in here: solve.py
.