Re: [SECURITY] Re: PATCH: rm -rf and readdir bug in coreutils-6.7

[Mikulas Patocka]

On Wed, 20 Dec 2006, Jim Meyering wrote:

> Mikulas Patocka <address@hidden> wrote:
> > BTW. looking at the code leads me to another observation --- all those
> > security checks against 'rm'-vs-'mv' race break apart if the attacker is
>
> Thank you for bringing this up.  However, note that such systems are not
> POSIX-compliant, since (as you must well know) POSIX requires unique inode
> numbers.  There are several places in the coreutils where this requirement
> is assumed, mainly for security and directory-cycle detection, but also
> for the relatively new --preserve-root option.  Relaxing it would not be
> trivial.  It's just that I'm not (yet?) convinced doing so is desirable.
>
> > able to create directories with colliding inode number (which can happen
> > on 64-bit filesystems that can store more than 2^32 files --- for example
> > NFS v3, OCFS or my SPADFS filesystem)
>
> Can you do this in practice?

On SpadFS it is rather trivial to force inode number collision (but 
unlikely in normal operation) --- the filesystem can allocate inodes 
anywhere, minimum inode size is 64 bytes. So 64*2^32 is 256Gib and on 
devices larger than that you may get a collision. Manufacturing inode with 
given number is rather easy --- you fill up the whole filesystem with some 
files. You delete one file and create inode --- it must be allocated in 
original file's place (because there is no free space anywhere else). If 
it doesn't have requested number, you create the file again, delete 
different file and create inode at its place --- because the files will be 
created mostly linearly, you can use binary search to manufacture an inode 
at given location.

> If so, what are the system and resource requirements?
> Does one have to create 2^32 files (or something approaching that number)
> in order to get the first inode number collision?
> If you can, please answer separately for each file system
> type that is susceptible.
>
> Even assuming all of this is feasible, I imagine it would be very
> expensive (probabilistically) to get an exploitable collision.
> Of course, that is no reason not to avoid the vulnerability.

With the above-described binary search it is straight. I don't know if 
it's possible on other filesystems.

> > Imagine this:
> > user creates directory /home/user/foo with i_ino colliding with home
> > user creates directory /home/user/foo/boo with i_ino colliding with user
> > user creates directory /home/user/foo/boo/bla with a lot of content
> > user persuades the root to delete /home/user/foo
> > while deleting, he moves /home/user/foo/boo/bla to /home/user/bla
> > --- rm will then carelessly remove all home directories.
>
> Haven't you omitted (assumed?) another prerequisite for such an exploit:
> a 32-bit ino_t type?  Don't most progressive kernels expose a 64-bit ino_t?
> ...for some definition of "progressive" :-) -- I presume this isn't
> an issue with them.

They have 32-bit ino_t but 64-bit stat64.st_ino
(stat64 has unsigned long long st_ino) --- although kernel has the 
deficiency that it can pass only 32-bit values to it --- BTW. can you 
accept that fact that sizeof(st_ino) > sizeof(ino_t) in coreutils?
(although it violates standard).

> > Utilities like rm, cp or mv shouldn't probably execute open("..") or
> > chdir("..") at all. The best implementation would be walk the whole path
> > from initial file again
>
> Surely you don't mean to imply that the _best_ implementation involves
> traversing a potentially deep hierarchy *twice*!?

If you keep cache for 3 open DIRs, you only walk the whole path for each 
subtree of depth 3 --- and operations in that subtree overweight the 
walking by several orders. You probably save by keeping DIRs open more 
than you lose by walking the path.

> > when finished processing directory and keep cache
> > of about 3 to 5 open handles to directories up to initial directory, so
> > that walking the whole path can be avoided for most common cases (for
> > performance reasons).
>
> That is precisely what is now done by tools (du, chmod, chgrp, chown)
> that use gnulib's fts.c.
>
> > Another possibility to fix it (without rewriting the whole algorithm)
> > would be to compare not only st_ino and st_dev but also st_uid and st_gid
> > in macro SAME_INODE --- this way the user cannot arrange directories to
> > delete other user's files. Although I'm still not sure it this is 100% safe.
>
> If necessary, this might be a good short-term fix, but it'd come at a
> small cost: currently, only st_dev and st_ino are stored on rm's internal
> stack.  It could double the footprint of that stack -- not that it's big.
> More importantly, changing SAME_INODE to reference members other than
> st_dev and st_ino would affect many tools that store only dev/ino members
> rather than a full 'struct stat'.

It prevents one user from deleting someone else's files but I'm not sure 
if it will work in configuration where there are interleaved 
world-writable directories owned by different users. But it may be a 
simple hotfix.

Mikulas