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 be an elliptic curve defined in Weierstrass form as:

Where are points within the curve.

In ECC, the above elliptic curve is considered under a finite field (for example, , with a prime number). Hence, the curve can be renamed as .

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

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 , and also the most significant bits of and . The intended way to find and 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 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 and ) and use a system of equations to find and because:

Subtracting both equations, we have:

So, we can isolate :

And then it is trivial to find :

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.