ebctf 2013: MD5 COLLIDING

by comawill

The Task

1
2
3
4
5
6
7
8
9

Please upload 5 Windows console executable files with the same MD5 but with different printed outputs (file type: MS Windows, PE32 executable, console)

The output for the files should be:

File1: All Eindbazen are wearing wooden shoes
File2: All Eindbazen live in a windmill
File3: All Eindbazen grow their own tulips
File4: All Eindbazen smoke weed all day
File5: All Eindbazen are cheap bastards

The Plan

We need…

  1. a win32 binary which is able to produce all of the 5 different outputs
  2. a way to create multiple files with the same MD5 (they checked for that, simply uploading the same file 5 times didn’t work)
  3. a way to decide when to produce which output

The Solution

After some googling we found the tool fastcoll which generates MD5 collisions really fast (a CMake file to create the fastcoll binary is added at the end of this writeup). With fastcoll we were able to create multiple binaries with the same MD5 due to the fact that adding the “same” block to a MD5 calculation will lead to the same MD5. Also it’s no problem to add some additional data at the end of a (win32) binary. 

1
2

MD5(file + col1_a + col2_a) == MD5(file + col1_a + col2_b) == MD5(file + col1_b + col2_a) ==
MD5(file + col1_b + col2_b)

To test the online-checking of the server, we decided to create a binary which connects back to one of our machines and sends us the filename. Surprisingly there were a lot of connections, much more than the 5 we expected (from the number of binaries we uploaded). Seems that this was a prevention against lucky guessing by executing the binary multiple times. But more interesting was the fact that each name of the executed binary looked like ${randomdata}.${nr_of_binary} (There were more deterministic parts in the random part, but I din’t write them down during the CTF). So we changed the binary to print the specific output depending on the last char of the filename.

Uploaded the binaries, and voila got the flag.

The Code

binary code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <stdio.h>
#include <string.h>
// gcc -Wall -o bin400.exe bin400.c
int main(int argc, char *argv[])
{
	char c = argv[0][strlen(argv[0])-1];
	if(c == '1')
		printf("All Eindbazen are wearing wooden shoes");
	else if(c == '2')
		printf("All Eindbazen live in a windmill");
	else if(c == '3')
		printf("All Eindbazen grow their own tulips");
	else if(c == '4')
		printf("All Eindbazen smoke weed all day");
	else
		printf("All Eindbazen are cheap bastards");

	return 1;
}

collision generator

generate.sh
1
2
3
4
5
6
7

#!/bin/sh
./fastcoll bin400.exe -o bin400_1.exe bin400_2.exe
./fastcoll bin400_1.exe -o bin400_1_1.exe bin400_1_2.exe
./fastcoll bin400_1_1.exe -o bin400_1_1_1.exe bin400_1_1_2.exe
./genfiles.py
md5sum out/*.exe
sha1sum out/*.exe
genfiles.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#!/usr/bin/env python

base = open("bin400.exe").read()

file_1 = open("bin400_1.exe").read()
coll_1 = file_1[len(base):]
file_2 = open("bin400_2.exe").read()
coll_2 = file_2[len(base):]

file_1_1 = open("bin400_1_1.exe").read()
coll_1_1 = file_1_1[len(file_1):]
file_1_2 = open("bin400_1_2.exe").read()
coll_1_2 = file_1_2[len(file_2):]

file_1_1_1 = open("bin400_1_1_1.exe").read()
file_1_1_2 = open("bin400_1_1_2.exe").read()
coll_1_1_1 = file_1_1_1[len(file_1_1):]
coll_1_1_2 = file_1_1_2[len(file_1_2):]


def w(fn, data):
	f = open("out/" + fn, "w")
	f.write(data)
	f.close()

w("file1.exe", base + coll_1 + coll_1_1 + coll_1_1_1)
w("file2.exe", base + coll_1 + coll_1_1 + coll_1_1_2)
w("file3.exe", base + coll_1 + coll_1_2 + coll_1_1_1)
w("file4.exe", base + coll_1 + coll_1_2 + coll_1_1_2)
w("file5.exe", base + coll_2 + coll_1_1 + coll_1_1_1)
fastcoll CMakeFiles.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

project(fastcoll)
cmake_minimum_required(VERSION 2.6.2)
set(fastcoll_SOURCES
	block0.cpp
	block1.cpp
	block1stevens00.cpp
	block1stevens01.cpp
	block1stevens10.cpp
	block1stevens11.cpp
	block1wang.cpp
	main.cpp
	main.hpp
	md5.cpp)
add_executable(fastcoll ${fastcoll_SOURCES})
target_link_libraries(fastcoll boost_system-mt boost_filesystem-mt boost_program_options-mt)