Converging Visions

9 minutes to read

We are provided with the server source code in Python:

from secret import FLAG, p, a, b
from random import randint
from utils import EllipticCurve

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(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.get_point(x)
            self.EP = self.P
        except:
            return 'Point not on curve'

        return ('Point confirmed on curve', self.P.x, self.P.y)

    def nextPoints(self):
        seed, enc_seed = self.prng.rotate()
        self.P *= seed
        self.EP *= enc_seed
        return ('New Points', self.EP.x, self.EP.y, self.P.x, self.P.y)


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 Px == response[3] and Py == response[4]:
                        print(
                            'You have confirmed the location. However, It\'s dangerous 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, shutting 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). The implementation is found in utils.py. 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 $E$ be an elliptic curve defined in Weierstrass form as:

$$ E: \; y^2 = x^3 + ax + b $$

Where $(x, y)$ are points within the curve.

In ECC, the above elliptic curve is considered under a finite field (for example, $\mathbb{F}_p$, with $p$ a prime number). Hence, the curve can be renamed as $E(\mathbb{F}_p)$.

As a result, the points in the curve form an abelian group under addition:

The operation is internal (i.e. $P + Q \in E(\mathbb{F}_p) \; \forall P, Q \in E(\mathbb{F}_p)$)
There is a unique identity element usually called $O$, such that $P + O = O + P = P$. This is also known as “point at infinity”
Every point has a unique inverse point, that is $\exists! Q \in E(\mathbb{F}_p) \;|\; P + Q = O \;\; \forall P \in E(\mathbb{F}_p)$. We can also say that $Q = -P$ 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:

$$ kP = \underbrace{P + \dots + P}_{k\; \text{times}} $$

In order to use ECC, we must take a generator point $G$ of the curve, then take a number $n$ and multiply $n$ by $G$. The public key is formed by the points $G$ and $nG$ (apart from the curve parameters $a$, $b$ and the finite field $\mathbb{F}_p$); and the private key is the number $n$.

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 $n$ given $G$ and $nG$.

Finding curve parameters

In option 1, we are allowed to enter a number $x$ and the server will try to give us the corresponding $y$ so that the point $(x, y)$ belongs to the curve:

            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.get_point(x)
            self.EP = self.P
        except:
            return 'Point not on curve'

        return ('Point confirmed on curve', self.P.x, self.P.y)

Here we have an oracle to find $p$ using binary search, because we can test values of $x$ and approximate to $p$ depending on the response ('Coordinate greater than curve modulus' vs. other message). This is the code to find $p$:

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 $a$ and $b$ by taking two random points of the curve (options 1 or 2). The process is to solve a system of two modular equations on variables $a$ and $b$:

$$ \begin{cases} y_1^2 = x_1^3 + a x_1 + b \mod{p} \\ y_2^2 = x_2^3 + a x_2 + b \mod{p} \\ \end{cases} $$

Substracting both equations, we have:

$$ y_1^2 - y_2^2 = x_1^3 - x_2^3 + a (x_1 - x_2) \mod{p} $$

So, we can isolate $a$:

$$ a = (y_1^2 - y_2^2 - x_1^3 + x_2^3) \cdot (x_1 - x_2)^{-1} \mod{p} $$

And then it is trivial to find $b$:

$$ b = y_1^2 - x_1^3 - a x_1 \mod{p} $$

This is the implementation in Python:

    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.x, self.EP.y, self.P.x, self.P.y)

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 $\mathrm{EP}$ and $\mathrm{enc\_seed} \cdot \mathrm{EP}$, we must somehow find $\mathrm{enc\_seed}$, that is, solve the ECDLP.

Smart’s attack

The key to solve the ECDLP is that the curve’s order is prime (actually, $|E(\mathbb{F}_p)| = p$). So we have an anomalous curve, which might be vulnerable to Smart’s attack to solve the ECDLP easily.

Smart’s attack is a complex method that requires knowledge on algebraic number theory, Hensel’s Lemma and $p$-adic numbers. For more information, read these resources (I found them useful to understand the attack from a high-level perspective):

I found an implementation of Smart’s attack in SageMath in this write-up 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):

$$ s_{j + 1} = a s_j^3 + b s_j + i \mod{p q} $$

Then, $\mathrm{enc\_seed} = s_{j + 1}^2 \mod{p q}$. Curiously, the formula looks like another eliptic curve.

The pseudo-random numbers $s_j$ are considered $\mod{p q}$. However, when multiplying these numbers by a point of the elliptic curve, they will be reduced to $\mod{p}$, since the curve is defined over $\mathbb{F}_p$. Hence, the PRNG formula can be considered just $\mod{p}$.

Since we know $\mathrm{enc\_seed}$ from Smart’s attack, we can compute the square root $\mod{p}$ (not $\mod{p q}$ because of the previous fact). Once having the seed $s_{j + 1}$, we will be able to find $s_{j + 2}$ applying the formula and predict the output of 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 138.68.166.146:32377
[+] Opening connection to 138.68.166.146 on port 32377: Done
[*] Got modulus p = 98807859381918657537428263421507671098277046895420042063839316200156326157051
[*] Got parameters a = 98708286800573747697090965573671079833937605909055221396616155663745907151444 and b = 22235152944190699843327692243188159330817147202763072426796844569091456960352
[*] Smart Attack -> enc_seed = 67440516568350265495759321275724631446066647201660934349374726772648832000938
[*] Trying next point (87513424733445795282705291920052722262294072879428526676725037034102784539109 : 46304974323527743139807054678481352167321888237327768089633252894299079270136 : 1)...  
[+] You have confirmed the location. However, It's dangerous to go alone. Take this:  HTB{th1s_4tt4ck_w4s_r3411y___SM4RT!}
[*] Closed connection to 138.68.166.146 port 32377

The full script can be found in here: solve.py.