phc-discussions - Re: [PHC] Tradeoff cryptanalysis of password hashing schemes

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: <CAOLP8p4z9Sk2Vs82qDWX3pFym1FhQpn50=1JqcdNbKbXc7MJrg@mail.gmail.com>
Date: Fri, 22 Aug 2014 12:21:18 -0400
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Tradeoff cryptanalysis of password hashing schemes

On Fri, Aug 22, 2014 at 11:35 AM, Solar Designer <solar@...nwall.com> wrote:

> On Fri, Aug 22, 2014 at 06:31:24PM +0400, Solar Designer wrote:
> > Suppose you'd optimally attack Catena-3 at 1/32 memory, and Lyra2 and
> > Argon at full memory.  However, if Catena-3 at same defensive memory
> > cost setting is e.g. twice faster than Lyra2 and Argon (an arbitrary
> > number for the sake of illustrating my point), then this may enable a
> > defender to use roughly twice more memory with Catena-3 to achieve the
> > same (maximum affordable) time cost per hash computed.  Once Catena-3 is
> > tuned like that, its non-tradeoff area-time cost probably grows by a
> > factor of 4, meaning that it loses to Lyra2 and Argon only by a factor
> > of 8, not 32 as this could have originally appeared.
>
> I was wrong in "only by a factor of 8, not 32".  For a moment I confused
> 1/32 being the optimal tradeoff point as the attack being 32 times
> cheaper, but it's not as bad as that.
>
> Alexander
>

The paper made several good points, but I have trouble with this part of
their analysis.  They assumed that the power per password guess burned in
memory is proportional to the total amount of memory used, rather than the
number of memory reads and writes.  This is simply not the case.  With the
computation penalty increasing memory accesses, I suspect memory power
would go up, not down, in any TMTO attack against Catena.

I do not believe Catena-3 has a TMTO problem against ASIC attacks.
However, with an ASIC computing 100 Blake2 hashes in parallel pipes at
3GHz, not in any way limited by memory latency when reading from 24MiB of
cache... there is a problem.  The Microsoft presenter stated that 3 orders
of magnitude difference in speed for one password guess between a CPU and
an ASIC would be unrealistic.  He was simply wrong.

Bill

Content of type "text/html" skipped