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

We only have option 1, which shows the prime number $p$ and the most significant bits of $a$ and $b$:

        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 $\mathrm{key} = \mathrm{SHA256}\left(a^b \mod{p}\right))$ for AES and encrypts the flag:

        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 $a$ and $b$ given a single point of the curve, $p$ and the most significant bits of $a$ and $b$.

Coppersmith method

Let’s put the information we have in mathematical terms. Let’s define $a_H$ and $b_H$ as the most significant bits of $a$ and $b$, respectively. Hence, we know that $a = 2^r a_H + a_L$ and $b = 2^r b_H + b_L$ for some $170 \leqslant r \leqslant 340$. If we are able to find $r$, $a_L$ and $b_L$, we can find $a$ and $b$.

The only equation we can use is the curve’s equation:

$$ y^2 = x^3 + ax + b \mod{p} $$

Substituting $a$ and $b$ we get:

$$ y^2 = x^3 + (2^r a_H + a_L) x + 2^r b_H + b_L \mod{p} $$

Notice that the unknowns are mainly $a_L$ and $b_L$ (we can do a brute force attack on $r$ if needed).

Hence, we can define a polynomial $P(t, z)$ that satisfies $P(a_L, b_L) = 0 \mod{p}$:

$$ P(t, z) = xt + z - (y^2 + x^3 + 2^r a_H + 2^r b_H) $$

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 $r$ (we can do a bit of brute force):

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 $a_H$ and $b_H$ and I choose the ones that are bigger, so that Coppersmith method is more likely to succeed.

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.