phc-discussions - Re: [PHC] A review per day

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] [day] [month] [year] [list]

Date: Mon, 01 Sep 2014 16:52:45 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] A review per day - POMELO

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 09/01/2014 03:39 PM, Bill Cox wrote:
> I'm running the Dieharder tests now on hashes produced by POMELO
> with t_cost = 1 and m_cost = 7 (the author says that t_cost +
> m_cost should be at least 8).  I think t_cost = 1 is the weakest
> hash POMELO does, so that's what I'm using.  It passes the Birthday
> test, as well as several more difficult tests, but my sample data
> is too small to pass them all.  I'm doing an over-night run that I
> think will show that it passes.

POMELO passed the dieharder tests.

I upgraded our test framework to take an output length parameter, and
upgraded POMELO to generate key data of any length less than the state
size.  I ran it with t_cost == 1 and m_cost ==7, which generates 1MiB
of data.  I set the output length to 512KiB, which is the last half of
the state.  I fed these 512MiB hashes into dieharder, which quickly
gave the data a passing grade on all tests.

This is not enough to prove that POMELO produces secure hashes which
cannot be determined to be non-random, and which cannot be reversed.
However, it's nice to pass this hurdle.

Looking at the code, I believe it will produce cryptographically
strong password hashes.  First, it initializes memory with data that
is somewhat random looking, but probably would not pass the dieharder
tests.  Then, it does two more passes in the predictable addressing
loop, XOR-ing somewhat random-looking data into everything twice.
Then, it does another basic randomization pass, then at least two
iterations of the unpredictable loop, which XORs somewhere around 1/4
of all memory into unpredictable locations, in addition to doing the
normal randomization.  It does one more final basic randomization pass
and is done.

That's a minimum of 7 randomization passes, with 4 of them doing
long-range swaps 1/4th of the time.  Memory is XOR-ed over in 6 of the
7 passes.  The DAG for this computation has 7 rows, where 3/4ths of
the elements depend on 4 nearby prior values, and every 1/4th-ish they
also depend on a long-range value.  It's going to be very scrambled by
the end, I think, at least in the second half of the array.

However, I certainly wouldn't want anyone to take my word for it!  I
have to say, POMELO would be easier to sell with a SHA512 in there
somewhere.

Bill
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAEBAgAGBQJUBNyZAAoJEAcQZQdOpZUZ25YP/jTG6mRRrT11akJpbEys/Sm+
wiL+Fr62GrDvk2oglSjFzuBHrk6lXtfgqoFv3bddoVIz7OWuDuz+38CvLnQDuddj
8zQeApuDc6rzErsn0ncHVDrTVDrZX2WKqvg91Zy65GgT+9dDBrcuWJU8OoHgYrWM
G2WQTAsHcM90Wprr+tCFAeiUA4vA0KHPD/QfqQVzkq0+HlwqOHbQyxYsQCNJXU6f
fbBsB83V71+Lk/3TeCncZsVS5C1o7nvO9qr4zb0J+4VE8GYkrsBRWiAChcNCeHPQ
Bq1cQzSPpIJR/5J2iKYRIrCHigeuv1yf+uz4/5HxYgR3ND5hqvNFW/gofbV7pPtr
5ZcsMMaZSsn0s2qLpN4k/IHmmn96JthQgjSdRWSetmEhLmR2WISy5hYk6q8UaTPL
95xKM1J+W0TXlKCmOIZjjQ5I/BbF2hGbpgyuAf1S7OtdDJlDgWNqyacnc9DK5K/v
vKTV8b+aPFooKVBFBhHS3r1MHNZ/zmehWSRC8drlzF6j1I85/6HmtYXhJ9Xm/oxQ
4M/8AJ/F+e3t7eaWDqUmwB1wv5Jz6LwIN+AEIqtfQ3/nLIUGPvCTw/mfcZGm8RqC
+WDzZs3Z2h+Zg0W+pe/FpgfcNiz+verj1edLb3tHsXDppg4g3yRcVXql5B5dBMMM
Rxrr7xFectDd50vDe77R
=m5Gf
-----END PGP SIGNATURE-----