Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
34C3 CTF software_update (crypto)
import sage.all
import hashlib
# part1 -
# part2 -
# 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]
print("file '{:3}' is NOT linear independent".format(x))
if len(vectors)==256:
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

This comment has been minimized.

Copy link

commented Mar 17, 2018

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)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.