phc-discussions - Re: [PHC] scripting memory (not so) high

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: Fri, 10 Jan 2014 19:06:22 -0600 (CST)
From: Steve Thomas <steve@...tu.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] scripting memory (not so) high

> On January 10, 2014 at 6:28 AM Solar Designer <solar@...nwall.com> wrote:
> On Fri, Jan 10, 2014 at 06:19:21AM -0600, Steve Thomas wrote:
> > I was aiming for least amount of calls to hash functions while keeping it
> > memory-hard. I guess I forgot make sure about the last part :).
>
> Yes, these two were my goals too.

Just thought of this, you can increase the cost of memory cheating.

This forces doing two blocks of SHA512 with the equivalent of only 8.5 w[] for
free (for the attacker) at a cost of 7.7% to you:
        $v .= $x = hash('sha512', '12345' . $x . $x, TRUE);

Two blocks reduced by 4.5 w[], cost 9.3%:
        $v .= $x = hash('sha512', '12345' . $x . $x . '1' . $x, TRUE);

Three blocks reduced by 8.5 w[], cost 15%:
        $v .= $x = hash('sha512', '12345' . $x . $x . '1' . $x . $x, TRUE);

* Note that currently it's one block reduced by 5 w[]. You need to calculate 64
of these w[] and that each round (80) costs more than calculating w[]. Worst
case, saving 8.5 w[] calculations only saves 6% of the block's calculations.
Hmm when I say it like that the second one does not make sense.
** I'm not counting the three additions in calculating w[]. I'm thinking of
GPUs,
but with FPGAs/ASICs this would probably be the opposite.
If you wanted to do more just keep adding '1' . $x . $x to the end. This will
only
work 7 times ('12345' . $x . $x . str_repeat('1' . $x . $x, 7)) then an attacker
can
reuse some parts of w[] and not have the cost of shifting.

'12345' is in there so the attacker needs to shift $x by an amount not divisible
by 4 bytes. I chose 5 bytes instead of 1 because if you did '1' . $x . $x then
the
last block only has 8 bits of unknown which is small enough to precalculate.
I also wanted at least 32 bits just to take that out of the picture.
Content of type "text/html" skipped