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:

Screenshot 2016-06-05 11.21.01

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:

Skärmavbild 2016-06-05 kl. 16.31.19

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
mask = 2**bits - 1
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
   return eax & mask
  
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)
   s.add(eax == hashdata[i])
   block_preimages = []
  
   while s.check() == sat:
       sol = s.model()
       s.add(j != sol[j].as_long())
       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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s