phc-discussions - Re: Tortuga issues

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]

Date: Thu, 3 Apr 2014 23:30:56 +0000 (UTC)
From: Teath Sch <teathsch@...lcity.com>
To: discussions@...sword-hashing.net
Subject: Re: Tortuga issues

Bill Cox <waywardgeek@...> writes:

> 
> I wonder if it would make sense to combine threads about different
> hashing schemes somehow...
> 
> Tortuga fails on both windows and Linux for > 1MiB m_cost, due to
> allocating hashing memory on the stack.  The algorithm relies on a
> sponge construction called "Turtle".  I'm not sure if this is a
> documented sponge construction or a new one, but the mixing looked
> iffy to me (is that scientific enough?), so I generated random data
> with it bash it using:
> 
> for i in `seq 400000`; do ./test 256 1 1 $i s; done > foo
> 
> I added a print statement to test.c to print every 4 bytes of output
> as an unsigned int.  This generated over 23MiB before I killed it,
> which I fed into the dieharder tests.  It failed the first test, the
> birthday test.
> 
> What this means is that with t_cost == 1, and m_cost == 1, the output
> hash for different passwords is not very random at all.  It's possible
> the error is in my code to print the data, but I think I got it right.
>  I would recommend that the author generate output hashes for many
> input passwords and verify that they pass some statistical tests for
> randomness, such as the dieharder tests.  There may be some simple bug
> in his code causing this result.
> 
> I think I'm going to have to do this test on all 24.  Is someone
> working to create a standard test for each PHS function?  It would be
> simple to call that for each entry and test the resulting hashes for
> basic randomness.
> 
> Bill
> 
> 

I deeply appreciate the input.

This sponge construction is part of Tortuga.  Turtle is the keyed 
permutation used in the sponge.  Turtle is referenced in the design 
document.

I was noticing problems with dieharder yesterday as well, so you beat me to 
it. :)

Some low parameters will cause the implied capacity of the sponge function 
to be way too low, so it needs some fixing.

Another problem with Tortuga is that it doesn't properly implement the 
"hermetic sponge" strategy.  This means that because the permutation is 
distinguishable from a random oracle, it doesn't inherit the security 
guarantees.

I think it is fixable with "tweaks".  I need a way to make the permutation 
even only half the time, which could be a challenge, but I'm hopeful.  Any 
suggestions for how to accomplish this would be greatly appreciated.  I know 
one way, but it's probably too awkward.

As far as the stack memory thing.. For now, I'm just going to make the 
reference implementation throw an error for high m_cost.  I think that it is 
appropriate at this stage.

Teath