Converging Visions
9 minutes to read
We are provided with the server source code in Python:
from secret import FLAG, p, a, b
from sage.all_cmdline import *
class PRNG:
def __init__(self, p, mul1, mul2):
self.mod = p * 6089788258325039501929073418355467714844813056959443481824909430411674443639248386564763122373451773381582660411059922334086996696436657009055324008041039
self.exp = 2
self.mul1 = mul1
self.mul2 = mul2
self.inc = int.from_bytes(b'Coordinates lost in space', 'big')
self.seed = randint(2, self.mod - 1)
def rotate(self):
self.seed = (self.mul1 * pow(self.seed, 3) + self.mul2 * self.seed +
self.inc) % self.mod
return self.seed, pow(self.seed, self.exp, self.mod)
class Relic:
def __init__(self, p, a, b):
self.E = EllipticCurve(GF(p), [a, b])
self.P = None
self.EP = None
self.p = p
self.prng = PRNG(p, a, b)
def setupPoints(self, x):
if x >= self.p:
return 'Coordinate greater than curve modulus'
try:
self.P = self.E.lift_x(Integer(x))
self.EP = self.P
except:
return 'Point not on curve'
return ('Point confirmed on curve', self.P[0], self.P[1])
def nextPoints(self):
seed, enc_seed = self.prng.rotate()
self.P *= seed
self.EP *= enc_seed
return ('New Points', self.EP[0], self.EP[1], self.P[0], self.P[1])
def menu():
print('Options:\n')
print('1. Setup Point')
print('2. Receive new point')
print('3. Find true point')
option = input('> ')
return option
def main():
artifact = Relic(p, a, b)
setup = False
while True:
try:
option = menu()
if option == '1':
print('Enter x coordinate')
x = int(input('x: '))
response = artifact.setupPoints(x)
if response[0] == 'Point confirmed on curve':
setup = True
print(response)
elif option == '2':
if setup:
response = artifact.nextPoints()
print('Response')
print((response[0], response[1], response[2]))
else:
print('Configure origin point first')
elif option == '3':
if setup:
print('Input x,y')
Px = int(input('x: '))
Py = int(input('y: '))
response = artifact.nextPoints()
if response[3] == Px and response[4] == Py:
print(
'You have confirmed the location. It\'s dangerous however to go alone. Take this: ',
FLAG)
else:
print('The vessels will never be found...')
exit()
else:
print('Configure origin point first')
else:
print("Invalid option, sutting down")
exit()
except Exception as e:
response = f'An error occured: {e}'
print(response)
exit()
if __name__ == '__main__':
assert p.bit_length() == 256
main()
The server uses Elliptic Curve Cryptography (ECC) with secret parameters (p
, a
, b
). It also uses a custom pseudo-random number generator (PRNG) with the same unknown parameters and a certain formula.
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)
The addition operation has a certain algorithm, which is implemented in the above source code. Once the addition is defined, we can express the product of a point by a scalar like this:
In order to use ECC, we must take a generator point
ECC can be used for Diffie-Hellman key exchange protocol (ECDH), Digital Signature Algorithm (ECDSA) or encryption (ECIES), among others. This cryptosystem relies on the difficulty to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP), that is, find
Finding curve parameters
In option 1
, we are allowed to enter a number
if option == '1':
print('Enter x coordinate')
x = int(input('x: '))
response = artifact.setupPoints(x)
if response[0] == 'Point confirmed on curve':
setup = True
print(response)
However, let’s take a look at method setupPoints
:
def setupPoints(self, x):
if x >= self.p:
return 'Coordinate greater than curve modulus'
try:
self.P = self.E.lift_x(Integer(x))
self.EP = self.P
except:
return 'Point not on curve'
return ('Point confirmed on curve', self.P[0], self.P[1])
Here we have an oracle to find 'Coordinate greater than curve modulus'
vs. other message). This is the code to find
def main():
io = get_process()
left, right = 2 ** 16, 2 ** 256
m = (left + right) // 2
while left < right - 1:
m = (left + right) // 2
io.sendlineafter(b'> ', b'1')
io.sendlineafter(b'x: ', str(m).encode())
data = io.recvline()
if b'Coordinate greater than curve modulus' in data:
right = m - 1
else:
left = m + 1
p = m - 1
io.info(f'Got modulus {p = }')
Then we can find 1
or 2
). The process is the same as in Elliptic Labyrinth: solve a system of two modular equations on variables
points = []
x = 0
while len(points) < 2:
io.sendlineafter(b'> ', b'1')
io.sendlineafter(b'x: ', str(x).encode())
data = io.recvline()
if b'Point confirmed on curve' in data:
point = tuple(
map(int, data.decode().replace(')', '').split(', ')[1:]))
points.append(point)
x += 1
(x1, y1), (x2, y2) = points
a = (y1 ** 2 - y2 ** 2 - x1 ** 3 + x2 ** 3) * pow(x1 - x2, -1, p) % p
b = (y1 ** 2 - x1 ** 3 - a * x1) % p
io.info(f'Got parameters {a = } and {b = }')
Understanding the challenge
Now that we have recovered the curve parameters, let’s review the challenge again to see how we must capture the flag.
In option 3
, we must provide the coordinates of a point P
correctly to see the flag (we only have one chance):
elif option == '3':
if setup:
print('Input x,y')
Px = int(input('x: '))
Py = int(input('y: '))
response = artifact.nextPoints()
if response[3] == Px and response[4] == Py:
print(
'You have confirmed the location. It\'s dangerous however to go alone. Take this: ',
FLAG)
else:
print('The vessels will never be found...')
exit()
else:
print('Configure origin point first')
This point P
comes from the last two entries of response
, which is a tuple returned by nextPoints
:
def nextPoints(self):
seed, enc_seed = self.prng.rotate()
self.P *= seed
self.EP *= enc_seed
return ('New Points', self.EP[0], self.EP[1], self.P[0], self.P[1])
Using option 2
we are given the point EP
, whose coordinates are in positions 1
and 2
of the tuple returned by nextPoints
:
elif option == '2':
if setup:
response = artifact.nextPoints()
print('Response')
print((response[0], response[1], response[2]))
else:
print('Configure origin point first')
Notice that we can control the value of P
and EP
in setupPoints
, but we don’t know the values of seed
and enc_seed
. So, given that we know point
Smart’s attack
The key to solve the ECDLP is that the curve’s order is prime (actually,
Smart’s attack is a complex method that requires knowledge on algebraic number theory, Hensel’s Lemma and
- The Discrete Logarithm Problem on Elliptic Curves of Trace One
- Weak Curves In Elliptic Curve Cryptography
- Anomalous Curves Part 1: Don’t be clever with your elliptic curve order
- Hensel’s Lemma
-adic number
I found an implementation of Smart’s attack in SageMath in this writeup from a CryptoHack challenge. Using this implementation, we can find enc_seed
:
x2 = 6
io.sendlineafter(b'> ', b'1')
io.sendlineafter(b'x: ', str(x2).encode())
E = EllipticCurve(GF(p), [a, b])
EP = E.gens()[0]
io.sendlineafter(b'> ', b'1')
io.sendlineafter(b'x: ', str(EP[0]).encode())
io.sendlineafter(b'> ', b'2')
io.recvline()
point = tuple(
map(int, io.recvline().decode().replace(')', '').split(', ')[1:]))
enc_seed_EP = E(point[0], point[1])
enc_seed = SmartAttack(EP, enc_seed_EP, p)
io.info(f'Smart Attack -> {enc_seed = }')
Analyzing the PRNG
Alright, so we have enc_seed
. Let’s take a look at the class PRNG
:
class PRNG:
def __init__(self, p, mul1, mul2):
self.mod = p * 6089788258325039501929073418355467714844813056959443481824909430411674443639248386564763122373451773381582660411059922334086996696436657009055324008041039
self.exp = 2
self.mul1 = mul1
self.mul2 = mul2
self.inc = int.from_bytes(b'Coordinates lost in space', 'big')
self.seed = randint(2, self.mod - 1)
def rotate(self):
self.seed = (self.mul1 * pow(self.seed, 3) + self.mul2 * self.seed +
self.inc) % self.mod
return self.seed, pow(self.seed, self.exp, self.mod)
We can express the rotate
method using mathematical terms (notice that the class is instantiated as self.prng = PRNG(p, a, b)
in class Relic
):
Then,
The pseudo-random numbers
Since we know nextPoints
, so that we can find the flag. This is the implementation:
seed = int(GF(p)(enc_seed).nth_root(2))
i = int.from_bytes(b'Coordinates lost in space', 'big')
next_seed = (a * pow(seed, 3) + b * seed + i) % p
curr_P = EP * seed
next_P = curr_P * next_seed
io.info(f'Trying next point {next_P}...')
io.sendlineafter(b'> ', b'3')
io.sendlineafter(b'x: ', str(next_P[0]).encode())
io.sendlineafter(b'y: ', str(next_P[1]).encode())
io.success(io.recv().decode())
Flag
If we run the script, we will see the flag:
$ python3 solve.py 209.97.134.50:31201
[+] Opening connection to 209.97.134.50 on port 31201: Done
[*] Got modulus p = 91720173941422125335466921700213991383508377854521057423162397714341988797837
[*] Got parameters a = 57186237363769678415558546920636910250184560730836527033755705455333464722170 and b = 47572366756434660406002599832623767973471965640106574131304711893212728437629
[*] Smart Attack -> enc_seed = 1574017221831123415886137346110982781503978446261518027146689940530621647822
[*] Trying next point (49394339834628750389338231331407606443777974829314059591423185069522974190491 : 36805735502973307035372435592237049388682732097929498134528467141686272904173 : 1)...
[+] You have confirmed the location. It's dangerous however to go alone. Take this: HTB{0Racl3_AS_a_f3A7Ur3_0n_W3aK_CURV3_aND_PRN9??_7H3_s3cur17Y_0F_0uR_CRyP70Sys73M_w1LL_c0LLAp53!!!}
[*] Closed connection to 209.97.134.50 port 31201
The full script can be found in here: solve.py
.