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> <CAF1vpkiKx3jArgjNBrid9-MSHBweGsFL0zu0UgDX_dq_hrkUgw@mail.gmail.com>
 <YWXGRgfxJZMe9iut@mit.edu>
In-Reply-To: <YWXGRgfxJZMe9iut@mit.edu>
From:   Avi Deitcher <avi@deitcher.net>
Date:   Fri, 15 Oct 2021 11:43:07 -0700
Message-ID: <CAF1vpkggQpYrg7Z2VVK69pPBo0rSjDUsm8nB8dyES27cmDEf2g@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

I am absolutely stumped. I tried the seed as four u32 as is on disk
(i.e. big-endian); four u32 little-endian; one long little-endian
array of bytes (I have no idea why that would make sense, but worth
trying); zeroed out so it gets the default. No one gives a consistent
solution.

As far as I can tell: hash tells you which intermediate block to look
in, minor hash tells you which leaf block to look in, and then you
scan. So it is pretty easy to see in what range the minor and major
hash should be, but no luck.

I put up a gist with debugfs and source and output.
https://gist.github.com/deitch/53b01a90635449e7674babfe7e7dd002

Anyone who feels like a look-see, I would much appreciate it (and if
they figure it out, owe a beer if ever in the same city).

On Tue, Oct 12, 2021 at 10:30 AM Theodore Ts'o <tytso@mit.edu> wrote:
>
> On Mon, Oct 11, 2021 at 07:58:00PM -0700, Avi Deitcher wrote:
> > 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.
>
> BTW, if you are looking for a userspace implementation of the hash,
> it's available in libext2fs in e2fsprogs.
>
> Cheers,
>
>                                         - Ted


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