34C3 CTF software_update (crypto)

software_update.sage

import sage.all
import hashlib

# part1 - https://www.youtube.com/watch?v=Vgdhlh6evjI
# part2 - https://www.youtube.com/watch?v=EOlddNofKxo

# prepare a table of bits
def bits_of(x):
    bits = []
    for c in "{:08b}".format(x):
        bits += [int(c)]
    return bits

# list of 8bit arrays/vectors
# bits_table[ 0] = [0,0,0,0, 0,0,0,0]
# bits_table[ 3] = [0,0,0,0, 0,0,1,1]
# bits_table[86] = [0,1,0,1, 0,1,1,0]
bits_8_table = [bits_of(x) for x in xrange(0x100)] 

def mk_vector(filename):
    bits_256 = []
    # sha256 of the filename+"\0"
    result = hashlib.sha256(filename)
    # for each byte of the hash we get each bit
    for byte in result.digest():
        # add the next 8 bits to the bits vector
        bits_256 += bits_8_table[ord(byte)]
    # return the bit vector
    return bits_256

GF2 = Zmod(2)

vectors = []
filenames = []
# loop over some numbers
for x in xrange(99999):
    # generate a 256bit vector from a possible filename
    filename = "{}\0".format(x)
    new_256_vector = mk_vector(filename)
    # create a matrix of all old vectors + the potential new one in GF(2)
    m = matrix(GF2, vectors + [new_256_vector]).transpose()
    # check the rank of this matrix
    rank = m.rank()
    # if rank increased, keep this file and vector because it's linear independent
    if rank > len(vectors):
        print("file '{:3}' is linear independent".format(x))
        vectors += [new_256_vector]
        filenames += [filename]
    else:
        print("file '{:3}' is NOT linear independent".format(x))
    if len(vectors)==256:
        break

GOAL = []
# the signed hash is the "point" that we want to get to in the vector space
for c in '\xba\x89\x07\x9d3\x17\xcb,\x90\x9b\x91 {\xf5\x8aP\xb8=\xa6Gc\xf6\xf9\xb0Qw\x1a\xb5\xa8U\x8f\xd0':
    GOAL += bits_8_table[ord(c)]


# create the whole matrix in GF(2) with all 256 bit vectors
m = matrix(GF2, vectors).transpose()
solved_equation = m.solve_right(vector(GOAL))
print solved_equation
for x, s in zip(solved_equation, filenames):
    #print x, s
    if x:
        print s

Great video!

For the reference, the bit vector conversion can be simplified by creating a large integer :

def mk_vector(filename):
    h = hashlib.sha256(filename).digest()
    i = int(h.encode('hex'), 16)
    return map(int, '{:0256b}'.format(i))

Or, using python3:

def mk_vector(filename):
    h = hashlib.sha256(filename).digest()
    i = int.from_bytes(h, 'big')
    return list(map(int, '{:0256b}'.format(i)))