AceBear CTF 2019 - F3737 Solver

solve.py

from hashlib import sha512
BLOCKSIZE = 16

def reduce_modulo_37(i):
    return int(i % 37)

class F3737(object):
    """
    This class represents a vector in F37^37. Only basic operations (addition
    and scalar multiplication) are provided.
    """

    def __init__(self, components):
        self.components = list(map(reduce_modulo_37, components))
        assert len(self.components) == 37

    def __add__(self, other):
        return F3737(
            map(lambda x, y: x + y, self.components, other.components))

    def __mul__(self, scalar):
        return F3737(map(lambda x: x * scalar, self.components))

    def __eq__(self, other):
        return self.components == other.components

    def __str__(self):
        return str(self.components)

    def __repr__(self):
        return repr(self.components)


def f3737_hash(input):
    """
    This function somehow makes the output of sha512 become a vector of F37^37.
    """
    if input == b'EVALUATE_TO_ZERO':
        return F3737([0] * 37)
    h = int(sha512(input).hexdigest(), 16)
    result = [0] * 37
    for i in range(37):
        result[i] = h % 37
        h = h // 37
    return F3737(result)

def myhash(innput):
        """
        `f3737_hash` is used as a block hash function to construct this one.
        """
        i = 0
        result = F3737([0] * 37)
        while True:
            block = innput[BLOCKSIZE * i: BLOCKSIZE * (i + 1)]
            if not block:
                break
            result += f3737_hash(block) * i
            i += 1
        return result

import string
import random

ALLOWED_LETTERS = string.ascii_letters + string.digits + '_'

# PREPARE VECTOR
M = VectorSpace(Integers(37),37)
vecs = []
dic = []
while True:
    vecs = []
    dic = []
    for i in range(37):
        rand = random.SystemRandom()
        password = ''.join(rand.choice(ALLOWED_LETTERS) for _ in range(16))
        hash_value = f3737_hash(password)
        arr = [Integer(i) for i in str(hash_value)[1:-1].split(',')]
        vec = M(arr)
        vecs += [vec]
        dic += [password]
    if not M.are_linearly_dependent(vecs):
        break

# TRACKER
zero = 'EVALUATE_TO_ZERO'
def pretty_print(arr):
    test = 0
    for i in arr[::-1]:
        test *= 37
        test += int(i)
    return test

table = {}
for i in range(len(dic)):
    table[pretty_print(vecs[i])] = (vecs[i],dic[i])

# WORKER
def gen_with_pos(target, pos):
    if (pos == 0):
        return ''
    result = zero*(pos)+target+zero*(36-pos)
    return result

def edit_block(passwd, target, pos):
    if pos == 0:
        return passwd
    if (passwd == ''):
        passwd = gen_with_pos(zero,1)
    block = 0
    while True:
        this_block = passwd[block*37*BLOCKSIZE:(block+1)*37*BLOCKSIZE]
        if (this_block == ''):
            passwd = passwd + gen_with_pos(target,pos)
            break
        if (this_block[BLOCKSIZE*pos:BLOCKSIZE*(pos+1)] != zero):
            block += 1
            continue
        else:
            this_block = this_block[:BLOCKSIZE*pos]+target+this_block[BLOCKSIZE*(pos+1):]
            passwd = passwd[:37*block*BLOCKSIZE] + this_block + passwd[37*(block+1)*BLOCKSIZE:]
            break
    return passwd

# CONNECT
import socket
host = 'f3737.ctf.whitehub.net'
port = 13737 

soc = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
soc.connect((host,port))
for chall in range(3):
    # GET CHALLENGE
    rep = soc.recv(1024)
    print rep
    target = [Integer(i) for i in rep[rep.index('[')+1:rep.index(']')].split(',')]
    rep = soc.recv(1024)
    print rep 

    # PREPARE MATRIX
    this_chall = []
    for i in vecs:
        this_chall.append(M(i))
    this_chall.append(M(target))
    aug = matrix(this_chall)
    prepare = aug.transpose()
    final = prepare.echelon_form()

    # TRACE BACK FROM WEIGHT TO PASSWORD
    final_dic = {}
    for j in range(37):
        asd = []
        for i in range(37):
            asd.append(prepare[i][j])
        passwd = table[pretty_print(asd)][1]
        val = final[j][-1]
        final_dic[passwd] = int(val)

    # GENERATE PASSWORD
    final_pass = ''
    for i in final_dic:
        #print final_dic[i], i
        final_pass = edit_block(final_pass, i, final_dic[i])

    print final_pass
    print 'final_pass', myhash(final_pass)
    print 'target.   ', target
    soc.send(final_pass+'\n')

rep = soc.recv(1024)
print rep
rep = soc.recv(1024)
print rep