Elliptic Labyrinth

4 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 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. Get point in path")
    print("3. Try to exit the labyrinth")
    option = input("> ")
    return option


def main():
    ec = ECC(512)

    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':
            A = ec.gen_random_point()
            print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))
        elif choice == '3':
            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 $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)

Since ECC is not used to encrypt information, I will leave the explanation here.

Finding curve parameters

The server shows some information about the curve parameters with option 1:

        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)
                }))

For instance, we already have the value of $p$, and also the most significant bits of $a$ and $b$. The intended way to find $a$ and $b$ and thus solve the challenge is using these information. I will cover the intended solution on Elliptic Labyrinth Revenge.

There is option 2, which provides us with random points in the curve:

        elif choice == '2':
            A = ec.gen_random_point()
            print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))

The remaining option prints the encrypted flag using $\mathrm{key} = \mathrm{SHA256}\left(a^b \mod{p}\right))$ for AES:

        elif choice == '3':
            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()
                }))

Solution

Having the ability to request random points of the curve, we can get two of them (say $(x_1, y_1)$ and $(x_2, y_2)$) and use a system of equations to find $a$ and $b$ because:

$$ \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} $$

Python implementation

The above procedure is programmed in Python as follows:

def main():
    host, port = sys.argv[1].split(':')
    io = remote(host, port)

    io.sendlineafter(b'> ', b'1')
    data = json.loads(io.recvline().decode())

    p = int(data['p'], 16)

    io.sendlineafter(b'> ', b'2')
    data = json.loads(io.recvline().decode())
    x1, y1 = int(data['x'], 16), int(data['y'], 16)

    io.sendlineafter(b'> ', b'2')
    data = json.loads(io.recvline().decode())
    x2, y2 = int(data['x'], 16), int(data['y'], 16)

    a = (y1 ** 2 - y2 ** 2 - x1 ** 3 + x2 ** 3) * pow(x1 - x2, -1, p) % p  
    b = (y1 ** 2 - x1 ** 3 - a * x1) % p

    io.sendlineafter(b'> ', b'3')
    data = json.loads(io.recvline().decode())
    iv, enc = bytes.fromhex(data['iv']), bytes.fromhex(data['enc'])

    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())

Flag

If we run it, we will find the flag (the message refers to the intended way, which is covered in Elliptic Labyrinth Revenge):

$ python3 solve.py 167.71.143.44:32580
[+] Opening connection to 167.71.143.44 on port 32580: Done  
[+] HTB{d3fund_s4v3s_th3_d4y!}
[*] Closed connection to 167.71.143.44 port 32580

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