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!