Skip to content

Instantly share code, notes, and snippets.

# LiveOverflow/software_update.sage Created Mar 16, 2018

34C3 CTF software_update (crypto)
 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 = [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

### vxgmichel commented Mar 17, 2018 • edited

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