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: <CAF1vpkgE3XopWRqzFqdyCWg0hQB9FtEhbWmz1t=HZPE+WNEQ3A@mail.gmail.com>
In-Reply-To: <CAF1vpkgE3XopWRqzFqdyCWg0hQB9FtEhbWmz1t=HZPE+WNEQ3A@mail.gmail.com>
From:   Avi Deitcher <avi@deitcher.net>
Date:   Sun, 3 Oct 2021 15:47:01 +0300
Message-ID: <CAF1vpkgPAy3FJ9mN22OVQ41jQAYoRdoCdqzYwRYYPXD4uucdpg@mail.gmail.com>
Subject: Re: algorithm for half-md4 used in htree directories
To:     linux-ext4@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

I can narrow down the question further. In my live sample, one of the
entries in the tree is for a directory named "dir155".

If I run "dx_hash dir155", I get:

# debugfs -R "dx_hash dir155" /var/lib/file.img
debugfs 1.46.2 (28-Feb-2021)
Hash of dir155 is 0x16279534 (minor 0x0)

If I look in the tree with "htree_dump", I get:

# debugfs -R "htree_dump /testdir" /var/lib/file.img
debugfs 1.46.2 (28-Feb-2021)
....
Entry #0: Hash 0x00000000, block 1
Reading directory block 1, phys 6459
168 0x00d11d98-b9b6b16b (16) dir155   332 0x009edafe-77de7d72 (16) dir319

That hash for dir155 does not match what dx_hash gave. If I try to
take the code from fs/ext4/hash.c and build a small program to
calculate the hash, I get:

$ ./md4 dir155
MD4: d90278a1 25182ac7 a02e56be c3f30f04
hash: 0x25182ac6
minor: 0xa02e56be

Clearly that isn't what is in the tree. What basic am I missing?

On Fri, Oct 1, 2021 at 2:49 PM Avi Deitcher <avi@deitcher.net> wrote:
>
> Hi,
>
> I have been trying to understand the algorithm used for the "half-md4"
> in htree-structured directories. Going through the code (and trying
> not to get into reverse engineering), it looks like it is part of md4
> but not entirely? Yet any subset I take doesn't quite line up with
> what I see in an actual sample.
>
> What is the algorithm it is using to turn an entry of, e.g., "file125"
> into the appropriate hash. I did run a live sample, and try to get
> some form of correlation between the actual md4 hash (16 bytes) of the
> above to the actual entry (4 bytes) shown by debugfs, without much
> luck.
>
> What basic thing am I missing?
>
> Separately, how does the seed play into it?
>
> Thanks
> Avi


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