## Sunday, May 18, 2014

### DEF CON Quals 2014, 100lines writeup

It's not broken, you just need more RAM.

100lines was a task for 2 points by Jymbolia at the DEF CON Qualifiers. The file was a 64-bit ELF executable.

After some reversing the clue we received from the task description becomes clear. At 0x400D1A the program tries to malloc 264289788888064 bytes, which is roughly 240 terabytes. We have to optimize the program to use less memory.

The key function to optimize was getByte, which calls loop after malloc. loop writes random data into the allocated buffer and when it's finished, getByte returns the value at the passed index. Let's look at loop a bit more closely. After decompiling and a lot of modifications by hand, we get something like this:

```void loop(ulong count, char* seed, char* big_buff) {

count_max = count - 32;
counter_1 = 0;
while (counter_1 < count_max) {

res1 = calc4(seed, counter_1);
counter_2 = 0;
while (counter_2 < count_max) {

res2 = calc4(seed, counter_2);

res = res1 ^ res2;
ptr = (count_max * counter_1 + counter_2) * 4;

big_buff[ptr + 0] = (res >> 24) & 0xff;
big_buff[ptr + 1] = (res >> 16) & 0xff;
big_buff[ptr + 2] = (res >> 8) & 0xff;
big_buff[ptr + 3] = (res >> 0) & 0xff;

counter_2++;
}
counter_1++;
}
}```

calc4 calls calc 4 times with (0, 1, 2, 3) as the third paramter and adds the results using bitwise or. Since nobody else writes to the allocated buffer, this is rather easy to reverse. The seed itself is also created by the loop function, using an array of random numbers called random_pad. This is only ~16MB, so we decided to dump this from gdb and use this for our solution. It was also useful to verify that our reversed loop function works correctly.

To reverse the loop function, we need to reverse calc first. Here is the hand decompiled C code, converted to Python.

```def calc4(buf, arg2):

res = 0
for arg3 in range(4):
res |= calc(buf, arg2, arg3)

return res

def calc(buf, arg2, arg3):
shift = arg2 >> 3
w = arg2 & 7

v1 = ord(buf[shift + arg3])
esi = v1 << w

v2 = ord(buf[shift + arg3 + 1])
edx = v2 >> (8 - w)

eax = (esi | edx) & 0xff
eax = eax << [24, 16, 8, 0][arg3]

return eax```

Here is the reversed loop function that returns any element of the hypothetical buffer without allocating and computing its content.

```def unloop(id):

i = id / 4
j = id % 4
count1 = i / count_max
count2 = i % count_max

result = calc4(seed, count1) ^ calc4(seed, count2)
return (result >> [24, 16, 8, 0][j]) & 0xff```

After being able to simulate getByte, we have to take care of some extra things. When we look at the main function, we can see that it takes one character from the user at a time, calls getByte, does some extra stuff and then compares the two. If we correctly guess enough characters from the first 8, we get to the second stage. Here is the decompiled function that runs after getByte on the resulting character:

```def fix(x):
eax = x
ecx = x
edx = x

eax = eax * 3
eax = eax << 5
eax = eax + ecx
eax = eax >> 8

ecx = ecx - eax
ecx = ecx >> 2
eax = eax + ecx
eax = eax >> 6
ecx = 0x5d
eax = eax * ecx
edx = edx - eax
eax = edx & 0xff
eax = eax + 0x20

return eax & 0xff```

Yeah, I was pretty tired here, and my initial implementation had a bug, so I took the assembly and converted it to Python.

After some debugging, every component was finally working, and we got to the second part. The program replied with a bunch of hex-encoded bytes and exited. If we look at the disassembly, we can see that the flag is read into a buffer, and the xor encrypted using the getByte[OTP[i]] values as the key. Since we had already reversed the getByte function, and we knew the OTP values, this was trivial to decrypt.

```# We got these after running the first part of the solution
otp = [...]
flag = [...]

print ''.join([chr(unloop(o) ^ f) for o, f in zip(otp, flag)])```

Here is the full script for the first part of the challenge: https://gist.github.com/balidani/92912e5f79695f983fc1

Here is the script for the second part, with valid flag and OTP values: https://gist.github.com/balidani/91326787a8900b3a2c2d

If anybody wants to recreate the ~16MB seed file used in the scripts, just run this script: https://gist.github.com/balidani/e8212c3142c28238db6e

Thanks to all of the DEF CON guys for the Quals, it was lots of fun!