Codegate CTF Preliminary 2015 - pirate_danbi writeup

This blogpost describes how we from StratumAuhuur solved the pirate_danbi challenge in the Codegate 2015 Preliminary CTF.

Overview

The binary is a simple server started via inetd. After startup it generates two strings containing the IP-address of the client to be used as filenames for storing a bz2 compressed file and the extracted bz2 file in /tmp. It also reads an 8 byte long key file from disk.

After basic initialization it reads 3 bytes from stdin which denote an action to be performed and a length of data to be worked with in big endian.

while ( 2 )
{
  memset(buf, 0, 0xAuLL);
  fread(buf, 3uLL, 1uLL, stdin);
  v5 = buf[0];
  size = ((unsigned __int8)buf[1] << 8) + (unsigned __int8)buf[2];
  sanitize_filesize(size);
  memset(s, 0, 0x2801uLL);
  fread(s, (unsigned int)size, 1uLL, stdin);
...

sanitize_filesize() just checks if the length of the data to be read exceeds the buffer size of 0x2800 bytes and exits if this is the case.

If the check passes, the desired action is performed by switching over v5 and calling the appropriate function:

if ( (unsigned __int8)v5 <= 8u )
{
  switch ( v5 )
  {
    case 1uLL:
      sanitize_cryptdata_filesize(size);
      decrypt_auth_string((char *)&key, s, size);
      nop();
      continue;
    case 2uLL:
      open_bz2file(s, size);
      continue;
    case 3uLL:
      extract_bz2();
      continue;
    case 4uLL:
      compare_or_exit();
      continue;
    case 5uLL:
      execute_stuff();
      continue;
    case 6uLL:
      print_banner();
      continue;
    case 7uLL:
      print_version();
      continue;
    case 8uLL:
      exec_print_last();
      continue;
    case 0uLL:
      goto exit;
  }
}
  • Action 1 takes a buffer of data and decrypts it with the key read during the initialization phase and stores the result in a global variable which we called magic_string. More on that later.
  • Action 2 opens the supplied data as a bz2 file for extraction. It does this by writing the received data to a file in /tmp and then opening it using libbz2.
  • Action 3 unpacks the file opened in step two to another file in /tmp. The caveat is that this action is only performed if a flag was set during the authentication phase in action 1.
  • Action 4 then compares the decrypted payload from action 1 in the magic_string-variable with a fixed string YO_DANBI_CREW_IN_THE_HOUSE. with a memcmp. If the decrypted data matches this string, a flag is set which is used in action 5.
  • Action 5 executes the file which was unpacked in action 3 using system() with sh.
  • All other actions just print a banner, a version info or call last on the machine and return the output. We found no real use for these actions.

Now the goal seems to be to authenticate, upload a file, unpack it and let the unpacked file be executed. So, we need to execute steps 1 to 5 with the correct payloads. But to unpack the bz2-file and execute the unpacked file, certain conditions have to be met during authentication. Let’s have a detailed look at the decrypt_auth_string-function:

void __fastcall decrypt_auth_string(char *key, char *buf, unsigned int size)
{
  __int64 v3; // rax@19
  unsigned int v4; // [sp+Ch] [bp-64h]@1
  char paddingbyte; // [sp+2Ah] [bp-46h]@2
  unsigned int k; // [sp+2Ch] [bp-44h]@12
  signed int i; // [sp+30h] [bp-40h]@1
  signed int j; // [sp+30h] [bp-40h]@7
  unsigned int l; // [sp+30h] [bp-40h]@13
  signed int v10; // [sp+34h] [bp-3Ch]@1
  signed int v11; // [sp+34h] [bp-3Ch]@7
  char s[16]; // [sp+40h] [bp-30h]@1
  char paddingblock[9]; // [sp+50h] [bp-20h]@1
  __int64 v14; // [sp+68h] [bp-8h]@1

  v4 = size;
  v14 = *MK_FP(__FS__, 40LL);
  v10 = 0;
  should_extract = 0;
  memset(s, 0, 9uLL);
  memset(paddingblock, 0, 9uLL);
  memcpy(s, &buf[v4 - 8], 8uLL);
  for ( i = 7; i != -1; --i )
  {
    paddingbyte = key[i] ^ s[i];
    if ( !v10 && !paddingbyte )
      goto out;
    paddingblock[i] = paddingbyte;
    v10 = 1;
  }
  if ( paddingblock[7] <= 8u ) { v11 = 0; for ( j = 7; 7 - (unsigned __int8)paddingblock[7] != j; --j ) { if ( paddingblock[j] != paddingblock[7] ) v11 = 1; } should_extract = v11 != 1; for ( k = 0; (v4 >> 3) - 1 > k; ++k )
    {
      for ( l = 0; l <= 7; ++l )
      {
        magic_string[(signed __int64)(signed int)(8 * k + l)] = buf[8 * k + l + 8] ^ buf[8 * k + l];
        magic_string[(signed __int64)(signed int)(8 * k + l)] += key[l];
      }
    }
    memcpy(&magic_string[(unsigned __int64)(8 * k)], paddingblock, 8uLL);
  }
out:
  v3 = *MK_FP(__FS__, 40LL) ^ v14;
}

Lines 20 and 21 just clear some buffers. Line 22 then copies the last 8 bytes from the supplied cryptodata into the buffer s.

Then the function loops in lines 23 to 30 over all these 8 bytes in reverse order and xors it with the key. It asserts, that the last byte in this last block is not 0 and copies all the xored bytes into the paddingblock-array. As you might have guessed, this part of the functions searches in the last block for padding bytes. The block-length is obviously 8 bytes and the used padding seems to be PKCS7. That means, if you don’t need padding, you would append another block with 8 bytes each containing a value of 8. Hence the check for a non-zero value in the last byte. This case cannot occour.

After the extraction of the padding bytes, the function checks in line 31 whether the last byte in the padding is smaller or equal 8 as this is our block-length and thereby our maximal padding. If this is the case, it checks if the last n bytes are equal. If not, it sets a flag in v11 which denotes an invalid padding. After the loop, the global flag should_extract is assigned to true if the padding was correct, otherwise false (lines 34-39).

Now after that, the real decryption of the payload takes place (lines 40-48). The outer loop iterates over all 8-byte long chunks in the payload except the last one. The inner loop then iterates over every byte in that chunk. For each byte, the current byte is xored with a byte of the next chunk. After that, the key at the current position is added to the xored byte. In a last step, the last block which contains the padding is copied to the end of the decrypted data.

I later found out, that this is a CBC encryption (even though it actually decrypts stuff). Instead of AES, the encryption-function here is the addition of the key-byte.

Owning it

After staring at the binary for a while and looking for the usual overflows or out-of-bound reads which could leak something, we found nothing. We then finally started to reverse the authentication function to get an idea how to authenticate. We didn’t know exactly what it was doing, so we took a pen and a paper and wrote everything down. We knew, that we needed to get the key, but we didn’t know how. We tried to create a system of equations to somehow get the key out of the target string and the conditions of the padding (at that time we didn’t know that it was padding). Nothing worked out of course, because we had too much variables. We just need to get the key somehow.

Another team member then had the idea to to perform a timing attack on the padding-check, because it executes a tiny bit longer if the padding is correct compared to when it isn’t because it performs more work. We implemented a timing attack which sends a 16 byte long string to the authentication function which contained a bunch of garbage and the last byte which we wanted to guess. So in the end we created a string with a padding of 1. If the byte we chose was correct, the complete lower part of the decryption would have been executed, otherwise not. Because we knew what we sent and what the function expected, we would have gotten the last byte of the key by xoring the byte which caused the decryption to take longer with 1. We sent a few thousand of these strings each to average the jitter a bit and to make the program take more time in the loop to be able to detect timing differences. Unfortunately the data was unusable because the timing differences were just too small.

Then we remembered, that the should_extract-flag was set if the padding was correct. So instead of just measuring the timing of the loop checking the padding, we uploaded a bz2-file to unpack, authenticate with our fake-data guessing a key byte by using the padding and then issue a few hundred unpacking commands of a large textfile. Now we had some timing to measure: If the padding was correct, it would extract the file, otherwise it wouldn’t.

So, we started with a padding of 1 until we got the last byte of the key. Then we repeated the same procedure with a padding of 2 which used the last two bytes. For the last byte, we already had the correct key, so we just xored it with our key-byte and tried all 256 combinations for the 2nd last byte until we got a timing difference again which means the padding was correct, which in turn means the 2nd last byte was xored with the correct 2nd last key byte. And so on… This is called a padding oracle attack.

After we got the key, we just needed to encrypt the string YO_DANBI_CREW_IN_THE_HOUSE. by ourselves, authenticate with it, upload a bz2-file containing a script, unpack it and execute it.

You can get the exploit here.