# BackdoorCTF16 – Collision Course

With 350 points and a description as follows:

In today’s world, hash collisions are becoming more and more popular. That is why, one must rely on standardized hashing techniques, such as bcrypt. However, n00bster shall never learn, and he has implemented his own hash function which he proudly calls foobar. Attached is an implementation of the hash function and a file with which you are supposed to find a collision. He believes that you will not be able to find a collision for the file, especially since he hasn’t even given you the hashing algorithm, but has packaged it as a black box application. Prove to him that he is wrong.

Note: Multiple collisions are possible, but only one of them is a valid flag.
You will realize you’ve gotten it once you do.

The hash is given as follows:

So, we start off by looking at the binary. Using Hopper, we obtain the following pseudo code by decompilation:

```int hash(int input) {
eax = _rotr(input ^ 0x24f50094,
(input ^ 0x24f50094) & 0xf);
eax = _rotl(eax + 0x2219ab34,
eax + 0x2219ab34 & 0xf);
eax = eax * 0x69a2c4fe;
return eax;
}

int main() {
esp = (esp & 0xfffffff0) - 0x20;
puts(0x80486d0);
gets(0x804a060);
stack[2039] = "\nBar:";
puts(stack[2039]);
while (stack[2039] < *(esp + 0x18)) {
stack[2039] = *(stack[2039] +
stack[2039] * 0x4);
*(esp + 0x14) = *(esp + 0x14) ^
hash(stack[2039]);
eax = _rotr(stack[2039], 0x7);
printf("%08lx", stack[2039]);
*(esp + 0x10) = *(esp + 0x10) + 0x1;
}
eax = putchar(0xa);
return eax;
}
```

We sketch the above code as block scheme below:

The first thing to note is that we can find an infinite number of collisions just by appending arbitrary data after 10 blocks. However, this is not interesting to us, but completely defeats the conditions for a safe cryptographic hash function.

This Merkle-Damgård-like structure allows us to solve blocks iteratively, starting from the first. Here is how. Starting from the first block, we can find an input to the function $H$ such that when rotated 7 steps is equal to block 0 (here, denoted $B_0$). Hence, the problem we solve is to find an $x$ such that $H(x) \ll 7 = B_0$. This is a simple thing for Z3. Then, we take the next block and solve for $(H(x) \oplus B_0) \ll 7 = B_1$ and so forth. Implemented in Python/Z3, it may look like the following:

```from z3 import *
import binascii, string, itertools

bits = 32
allowed_chars = string.printable

def convert_to_hex(s):
return ''.join([hex(ord(x))[2:].zfill(2) for x in s[::-1]])

def convert_to_string(h):
return ''.join([chr(int(x, 16)) for x in list(map(''.join, zip(*[iter(hex(h)[2:])]*2)))[::-1]])

def rot(val, steps):
return (val << (bits-steps)) | LShR(val, steps)

def hash_foobar(input):
eax = rot(input ^ 0x24f50094, (input ^ 0x24f50094) & 0xf)
eax = rot(eax + 0x2219ab34, bits - (eax + 0x2219ab34 & 0xf))
eax = eax * 0x69a2c4fe

def break_iteratively(hashdata, i):

if i == 0: prev_block = 0
else: prev_block = hashdata[i-1]

s = Solver()
j = BitVec('current_block', bits)

eax = rot(prev_block ^ hash_foobar(j), 7)
block_preimages = []

while s.check() == sat:
sol = s.model()
block_string = convert_to_string(sol[j].as_long())
if all(c in allowed_chars for c in block_string):
block_preimages.append(block_string)

return block_preimages

known = '9513aaa552e32e2cad6233c4f13a728a5c5b8fc879febfa9cb39d71cf48815e10ef77664050388a3' # this the hash of the file
data = list(map(''.join, zip(*[iter(known)]*8)))
hashdata = [int(x, 16) for x in data]

print '[+] Hash:', ''.join(data)
print '[+] Found potential hashes:\n'
for x in itertools.product(*[break_iteratively(hashdata, i) for i in range(10)]):
print ' * ' + ''.join(x)
```

This code is surprisingly fast, thanks to Z3, and runs in 0.3 seconds. Taking all possible collisions into consideration…

```[+] Hash: 9513aaa552e32e2cad6233c4f13a728a5c5b8fc879febfa9cb39d71cf48815e10ef77664050388a3
[+] Found potential hashes:

* CTFEC0nstra1nts_m4keth_fl4g}
* CTFEC0nstra1nts_m4keth_nl4g}
* CTFEC0nstra1nws_m4keth_fl4g}
* CTFEC0nstra1nws_m4keth_nl4g}
* CTFEC0nstra9nts_m4keth_fl4g}
* CTFEC0nstra9nts_m4keth_nl4g}
* CTFEC0nstra9nws_m4keth_fl4g}
* CTFEC0nstra9nws_m4keth_nl4g}
* CTF{C0nstra1nts_m4keth_fl4g}
* CTF{C0nstra1nts_m4keth_nl4g}
* CTF{C0nstra1nws_m4keth_fl4g}
* CTF{C0nstra1nws_m4keth_nl4g}
* CTF{C0nstra9nts_m4keth_fl4g}
* CTF{C0nstra9nts_m4keth_nl4g}
* CTF{C0nstra9nws_m4keth_fl4g}
* CTF{C0nstra9nws_m4keth_nl4g}
```

…we finally conclude that the flag is the SHA-256 of `C0nstra1nts_m4keth_fl4g`.