Received-SPF: pass (google.com: domain of linux-ext4-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
MIME-Version: 1.0
References: <CAF1vpkgPAy3FJ9mN22OVQ41jQAYoRdoCdqzYwRYYPXD4uucdpg@mail.gmail.com>
 <3A493D20-568A-4D63-A575-5DEEBFAAF41A@dilger.ca> <CAF1vpkigHMdKphnNjDm7=rR6TTxViHGGHi3bb64rsHG7KbqYzQ@mail.gmail.com>
 <CAF1vpkhwSOfGfErUUrp0YU5hSt58TtykTECiJXTcgqDtG0WVVg@mail.gmail.com> <YWSck57bsX/LqAKr@mit.edu>
In-Reply-To: <YWSck57bsX/LqAKr@mit.edu>
From:   Avi Deitcher <avi@deitcher.net>
Date:   Mon, 11 Oct 2021 19:58:00 -0700
Message-ID: <CAF1vpkiKx3jArgjNBrid9-MSHBweGsFL0zu0UgDX_dq_hrkUgw@mail.gmail.com>
Subject: Re: algorithm for half-md4 used in htree directories
To:     "Theodore Ts'o" <tytso@mit.edu>
Cc:     linux-ext4@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

Aha. I missed that the seed is injected into buf before passing it
into half_md4_transform. I was looking at it as just the empty buffer
before the first iteration of the loop (or, in my case, since I was
testing with a 6 char filename, the only iteration).

I will repeat my experiment with that and see if I can tease it out.

Thanks, Ted!

On Mon, Oct 11, 2021 at 1:20 PM Theodore Ts'o <tytso@mit.edu> wrote:
>
> On Mon, Oct 11, 2021 at 08:30:36AM -0700, Avi Deitcher wrote:
> > Does someone know how this is constructed and used?
> >
> > On Mon, Oct 4, 2021 at 12:57 AM Avi Deitcher <avi@deitcher.net> wrote:
> > >
> > > Hi Andreas,
> > >
> > > I had looked in __ext4fs_dirhash(). Yes, it does reference the seed -
> > > and create a default if none is there at the filesystem level - but it
> > > doesn't appear to use it, in that function. hinfo is populated in the
> > > function - hash, minor-hash, seed - but it never uses the seed to
> > > manipulate the hash.
>
> The seed is used to initialize the buf array, so long as the seed is
> not all zero's.  If it is all zeros, then the default seed is used
> instead (right above this bit of code:
>
>         if (hinfo->seed) {
>                 for (i = 0; i < 4; i++) {
>                         if (hinfo->seed[i]) {
>                                 memcpy(buf, hinfo->seed, sizeof(buf));
>                                 break;
>                         }
>                 }
>         }
>
> The legacy hash doesn't use the seed, yes.  But for the other hash
> types (hash_version), they mix the filename (in different ways
> depending on the hash type.  For example, for half md4:
>
>         case DX_HASH_HALF_MD4:
>                 p = name;
>                 while (len > 0) {
>                         (*str2hashbuf)(p, len, in, 8);
>                         half_md4_transform(buf, in);
>                                            ^^^
>                         len -= 32;
>                         p += 32;
>                 }
>                 minor_hash = buf[2];
>                 hash = buf[1];
>                 break;
>
> When the hash seed is different, that means the initial state of the
> buf array will different, and this influences the resulting hash.
>
> Cheers,
>
>                                         - Ted


-- 
Avi Deitcher
avi@deitcher.net
Follow me http://twitter.com/avideitcher
Read me http://blog.atomicinc.com