16 Nov 2020
escr - m0lecon 2020 - crypto
The chall
We are given the code for a custom hash function and we have to create 10 collisions in a row, let’s have a look at the actual code.
def rotl(x, n):
return ((x << n) & 0xffffffffffffffff) | x >> (64 - n)
def rotr(x,n):
return rotl(x, 64 - n)
class ToyHash(object):
def __init__(self):
self.state = [ 0x6A09E667F3BCC908, 0xBB67AE8584CAA73B, 0x3C6EF372FE94F82B,
0x510E527FADE682D1, 0x9B05688C2B3E6C1F, 0x1F83D9ABFB41BD6B,
0x243F6A8885A308D3, 0x13198A2E03707344, 0xA4093822299F31D0]
self.rounds = 91
self.mod = 2**64
def R(self, a, b, c, m1, m2, m3):
self.state[a] = (self.state[a] + self.state[b] + m1) % self.mod
self.state[b] = rotl(self.state[b]^self.state[c]^m2,16)
self.state[c] = (self.state[b] + self.state[c] + m3) % self.mod
self.state[a] = (self.state[a] + self.state[b] + m1) % self.mod
self.state[b] = rotr(self.state[b]^self.state[c]^m2,48)
self.state[c] = (self.state[b] + self.state[c] + m3) % self.mod
def compress(self, block):
mini_blocks = [int(block[64*i:64*i+64], 2) for i in range(9)]
for _ in range(self.rounds):
self.R(0, 3, 6, mini_blocks[0],mini_blocks[1],mini_blocks[2])
self.R(1, 4, 7, mini_blocks[3],mini_blocks[4],mini_blocks[5])
self.R(2, 5, 8, mini_blocks[6],mini_blocks[7],mini_blocks[8])
def hash(self, m):
bm = bin(bytes_to_long(m))[2:]
l = len(bm) % 0x7ff
bm = bm + '0'*((576-len(bm))%576) + '0'*564 + '1' + bin(l)[2:].rjust(11, '0')
blocks = [bm[576*i:576*i+576] for i in range(len(bm)//576)]
for b in blocks:
self.compress(b)
h = [self.state[i]^self.state[i+3]^self.state[i+6] for i in range(3)]
return ''.join(hex(n)[2:].ljust(16, 'f') for n in h).encode()
Basically the message is splitted in blocks of length 576 bits (padded with 0’s if necessay ) and another block with the length of the message is appended at the end, then each block is passed to the compress function that updates the internal state. The final hash is calculated from the internal state.
The idea is to find a block b' different from b but that satisfies compress(b') = compress(b), so that we can create a second message different from the first, but that updates the inernal state in the same way and therefore has the same hash.
The exploit
Since rotl(x, 16) and rotr(x, 48) are actually the same we can simplify the function R like so (and we need to double the number of rounds):
def R(self, a, b, c, m1, m2, m3):
self.state[a] = (self.state[a] + self.state[b] + m1) % self.mod
self.state[b] = rotl(self.state[b]^self.state[c]^m2,16)
self.state[c] = (self.state[b] + self.state[c] + m3) % self.mod
We can observe that a change in m1 has effect ONLY on state[a], in particular if we call 2*rounds times the function R the state[a] will change like so: newState[a] = ( something_that_dosent_depend_on_m1 + 2*rounds*m1 ) % mod.
Since gcd(2*rounds, mod) = 2 there exists another value m1' different from m1 that satisfies 2*rounds*m1' = 2*rounds*m1 (mod n). In particular that value is m1' = ( m1 + mod/2 ) % mod. ( in this case is the same as flipping the most significant bit: m1' = m1 ^ (1<<63))
Putting everything together
So we want to modify the value of either mini_blocks[0], mini_blocks[3], mini_blocks[6] as described above. If we study how the message is splitted into mini_blocks we see that mini_blocks[0] corresponds to the first 64 bits of the message, that means that the most significant bit will always be one, and it also means that if we flip it we will obtain a new message that is shorter than the original, no good. Thats not a big deal, we can flip the first bit of mini_blocks[3].
Since each block is 64 bits long we’ll have to flip the 193-th bit of the message (counting from one), that is easy enough and can be done for example like so:
def gencoll(plain):
plain = bytes_to_long(plain)
coll = plain ^ (1<<(plain.bit_length() - 64*3 - 1))
return long_to_bytes(coll)