linux-ext4 - Re: algorithm for half-md4 used in htree directories

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAF1vpkidOGm0OmRac+OqaXcnJptn1O22OLHXJZoPfEbhxb3Ttw@mail.gmail.com>
Date:   Tue, 12 Oct 2021 19:20:26 -0700
From:   Avi Deitcher <avi@...tcher.net>
To:     "Theodore Ts'o" <tytso@....edu>
Cc:     linux-ext4@...r.kernel.org
Subject: Re: algorithm for half-md4 used in htree directories

Yep, right here
https://git.kernel.org/pub/scm/fs/ext2/e2fsprogs.git/tree/lib/ext2fs/dirhash.c

Hey, that's your name on it, Ted!

I am close, must be messing it up somehow. I literally copied the
majority of that (actually, some slight variant, but basically the
same) into a standalone main.c, removed any library dependencies by
copying those in so I can get a standalone, and I still am not quite
getting it. Maybe I am messing up the seed?

dump2fs of the superblock shows:

Default directory hash:   half_md4
Directory Hash Seed:      d64563bc-ea93-4aaf-a943-4657711ed153

and debugfs of the hash tree shows:

Root node dump:
         Reserved zero: 0
         Hash Version: 1
         Info length: 8
         Indirect levels: 1
         Flags: 0
Number of entries (count): 2
Number of entries (limit): 123
Checksum: 0x49f0afdc
Entry #0: Hash 0x00000000, block 124
Entry #1: Hash 0x78b6e3b8, block 128

Entry #0: Hash 0x00000000, block 124
Number of entries (count): 113
Number of entries (limit): 126
Checksum: 0x78407270
Entry #0: Hash 0x00000000, block 1
Entry #1: Hash 0x00f48688, block 193
...

So it has the hash version correct (I also gdb-ed through my little
program. Maybe I am getting the u32 order wrong in the seed? Or the
endianness?

I should just create a gist with this, shouldn't I?

On Tue, Oct 12, 2021 at 10:30 AM Theodore Ts'o <tytso@....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@...tcher.net
Follow me http://twitter.com/avideitcher
Read me http://blog.atomicinc.com