Elliptic Labyrinth Revenge

5 minutes to read

This challenge is Elliptic Labyrinth modified to force CTF players use the intended way to solve the challenge.

Finding differences

The provided source code is a bit different:

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. Try to exit the labyrinth")
    option = input("> ")
    return option


def main():
    ec = ECC(512)

    A = ec.gen_random_point()
    print("This is the point you calculated before:")
    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()

This time, there is no such option to request random points in the curve. We are just provided with a single random point at the beginning:

    A = ec.gen_random_point()
    print("This is the point you calculated before:")
    print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))

Then we only have option 1, which shows the prime number and the most significant bits of and (as in Elliptic Labyrinth):

        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 is the same as option 3 in Elliptic Labyrinth. It uses 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 and given a single point of the curve, and the most significant bits of and .

Coppersmith method

Let’s put the information we have in mathematical terms. Let’s define and as the most significant bits of and , respectively. Hence, we know that and for some . If we are able to find , and , we can find and .

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

Substituting and we get:

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

Hence, we can define a polynomial that satisfies :

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. The flag in Elliptic Labyrinth made reference to defund’s implementation, but I didn’t manage to make it work properly (neither ubuntor).

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 (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 and 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 165.232.108.240:31791
[+] Opening connection to 165.232.108.240 on port 31791: Done
[-] Not found
[*] Closed connection to 165.232.108.240 port 31791

$ python3 solve.py 165.232.108.240:31791
[+] Opening connection to 165.232.108.240 on port 31791: Done
[+] HTB{y0u_5h0u1d_h4v3_u53d_c00p325m17h}
[*] Closed connection to 165.232.108.240 port 31791

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