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. A vulnerability in the product has been found - the vulnerability allows local attackers to gain elevated privileges (on RedHat systems, sguid slocate).
When SLocate decodes an invalid database specified by a local user (thanks to the -d command line option), slocate dies with a segmentation violation.
Example:
$ 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)
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 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.
Technical analysis:
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;
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.
Exploit:
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:
/* 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
*/
