exploit.sage

#!/usr/bin/env sage

import re
import sys
import socket

from collections import namedtuple


PublicKey = namedtuple('PublicKey', ['n', 'e', 'y'])


def long_to_bytes(n):
    b = n.hex()
    b += '0' * (len(b)%2)
    return b.decode('hex')


def extract_numbers(line):
    matches = re.findall(b'\d+', line)
    return list(map(int, matches))


def get_public_key(file):
    n, e, y = extract_numbers(file.readline())
    return PublicKey(n, e, y)


def get_round_params(file, c):
    file.readline()
    file.readline()
    a = extract_numbers(file.readline())[0]
    file.write((str(c) + '\n').encode())
    file.flush()
    z = extract_numbers(file.readline())[0]
    file.readline()
    file.write(b'y\n')
    file.flush()
    return a, z


def get_flag(z, n):
    M = MatrixSpace(ZZ, 2)([
        [1, z],
        [0, n]
    ])
    for x in M.LLL().list():
        for f in map(long_to_bytes, map(abs, [x, x * 2])):
            if 'Cup' in f:
                return f


def main(address):
    while True:
        sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        sock.connect(address)
        file = sock.makefile('rwb')
        key = get_public_key(file)
        a, z = get_round_params(file, 1)
        sock.close()
        flag = get_flag(z, key.n)
        if flag:
            print(flag)
            break
        else:
            print('failed. trying again...')


if __name__ == '__main__':
    ip = sys.argv[1] if len(sys.argv) > 1 else '0.0.0.0'
    main((ip, 41397))