xfs_metadump in never ending loop

xfs_metadump in never ending loop

[Arkadiusz Miskiewicz]

 
generate_obfuscated_name() in metadump.c can go into
never ending loop for some file names. Reproducer below.

Can someone look into it? Thanks.

#include <stdlib.h>
#include <dirent.h>

typedef unsigned char               uchar_t;
typedef     __uint32_t      xfs_dahash_t;

#define is_invalid_char(c)      ((c) == '/' || (c) == '\0')
#define rol32(x,y)              (((x) << (y)) | ((x) >> (32 - (y))))

static inline uchar_t
random_filename_char(void)
{
        uchar_t                 c;

        do {
                c = random() % 127 + 1;
        } while (c == '/');
        return c;
}

int main() {
	int namelen = 5, i, dup;
	xfs_dahash_t hash = 978052928;
	xfs_dahash_t newhash;
	uchar_t *name = "R\323\257NE\002\320\000";
	uchar_t newname[NAME_MAX];

        do {
                dup = 0;
                newname[0] = '/';

                for (;;) {
                        /* if the first char is a "/", preserve it */
                        i = (name[0] == '/');

                        for (newhash = 0; i < namelen - 5; i++) {
                                newname[i] = random_filename_char();
                                newhash = newname[i] ^ rol32(newhash, 7);
                        }
                        newhash = rol32(newhash, 3) ^ hash;
                        if (name[0] != '/' || namelen > 5) {
                                newname[namelen - 5] = (newhash >> 28) |
                                                (random_filename_char() & 0xf0);
                                if (is_invalid_char(newname[namelen - 5]))
                                        continue;
                        }
                        newname[namelen - 4] = (newhash >> 21) & 0x7f;
                        if (is_invalid_char(newname[namelen - 4]))
                                continue;
                        newname[namelen - 3] = (newhash >> 14) & 0x7f;
                        if (is_invalid_char(newname[namelen - 3]))
                                continue;
                        newname[namelen - 2] = (newhash >> 7) & 0x7f;
                        if (is_invalid_char(newname[namelen - 2]))
                                continue;
                        newname[namelen - 1] = ((newhash >> 0) ^
                                        (newname[namelen - 5] >> 4)) & 0x7f;
                        if (is_invalid_char(newname[namelen - 1]))
                                continue;
                        break;
                }
	} while (dup);
}

-- 
Arkadiusz Miśkiewicz        PLD/Linux Team
arekm / maven.pl            http://ftp.pld-linux.org/

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: xfs_metadump in never ending loop

[Alex Elder]

On Fri, 2010-10-01 at 21:36 +0200, Arkadiusz Miskiewicz wrote:
> generate_obfuscated_name() in metadump.c can go into
> never ending loop for some file names. Reproducer below.

The reason it hangs is that the algorithm for computing
a name with the same hash value as the name is stuck with
a portion of the hash whose only possible result includes
the string "/" in it.

The hash for the file "R\323\257NE" is 0x3ab4b3740.

One step in the algorithm is this:
        newname[namelen - 3] = (newhash >> 14) & 0x7f;
        if (is_invalid_char(newname[namelen - 3]))
                continue;

But the result of that is 0x2f, which is the '/'
character, which is illegal.  So this algorithm
will try again indefinitely, never finding a file
name with a matching hash.

I am looking into this a bit more.  Will report back
later, probably tomorrow.

					-Alex

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: xfs_metadump in never ending loop

[Alex Elder]

On Sun, 2010-10-03 at 18:57 -0500, Alex Elder wrote:
> On Fri, 2010-10-01 at 21:36 +0200, Arkadiusz Miskiewicz wrote:
> > generate_obfuscated_name() in metadump.c can go into
> > never ending loop for some file names. Reproducer below.
> 
> The reason it hangs is that the algorithm for computing
> a name with the same hash value as the name is stuck with
> a portion of the hash whose only possible result includes
> the string "/" in it.

I understand this problem, and have a solution.  But
before sending out the code I want to write up an
explanation of the problem, including the effect of
the hash and why the existing algorithm has problems.

Stay tuned.

					-Alex

> The hash for the file "R\323\257NE" is 0x3ab4b3740.
> 
> One step in the algorithm is this:
>         newname[namelen - 3] = (newhash >> 14) & 0x7f;
>         if (is_invalid_char(newname[namelen - 3]))
>                 continue;
> 
> But the result of that is 0x2f, which is the '/'
> character, which is illegal.  So this algorithm
> will try again indefinitely, never finding a file
> name with a matching hash.
> 
> I am looking into this a bit more.  Will report back
> later, probably tomorrow.
> 
> 					-Alex
> 
> _______________________________________________
> xfs mailing list
> xfs@oss.sgi.com
> http://oss.sgi.com/mailman/listinfo/xfs



_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs