phc-discussions - Re: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

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 for Android: free password hash cracker in your pocket

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

Message-ID: <CAOLP8p6RtfB7H1Fgna8o5KKN_7GSUd=ZCW2_2TK=m=9ZeSMkcw@mail.gmail.com>
Date: Thu, 13 Feb 2014 09:44:13 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

On Wed, Feb 12, 2014 at 11:16 AM, Solar Designer <solar@...nwall.com> wrote:
> BTW, you might not need the "| 3" when you do 32x32->64.  Your rationale
> for the "| 3" was to preserve entropy, but 32x32->64 is lossless (in
> fact, it's reversible, which might allow for attacks - you might need
> something else instead of the "| 3", perhaps after the multiply, to make
> it one-way).
>
> Alexander

In the version of this I tested, I make "value" (horrible name...)
64-bit, so the cast to 32-bit is not reversible, so there's no problem
there.  However, without the "| 3", I see that most of the LSBs after
1B iterations of the hash loop are 0.  The problem is that the upper
bits have no way of impacting the lower bits, so whenever value is odd
and we multiply by an even, that LSB of value never again impacts the
LSB of future values of value.  Maybe I should rename value to v?

Instead of "| 3", I tried using (value >> 32), which on a 32-bit
architecture costs nothing, and may be free on a 64-bit CPU.  It takes
a few hours to run all the dieharder tests, but it failed the
marsaglia_tsang_gcd test, but so far has passed everything else,
though the scores for sts_monobit and sts_serial look suspiciously
improbable.  Still, passing the dieharder tests is not a worthy goal.
I just need to preserve entropy.

If we can live with this level of non-randomness, this hash function
is the best I've tested to date.  I can hash 4GB with it using 2
threads in the same time the current NoelKDF hash function hashes 2GB.
 It's simply better in every respect.

I'll go ahead and do 1,000,000 runs with this and test the last
64-bits for collisions (no 64-bit collisions should occur, and there
should be around 100-130 collisions in the lower 32-bits and in the
upper 32-bits).  I think this has will pass this test.  I'll post the
results when I have them.  It looks like my NoelKDF hash function may
not survive the day...

Bill