phc-discussions - Re: [PHC] Compute time hardness

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: <CAOLP8p4ckw9GADdEp_d7GGHCNPym5=DaXAvPhM+A-N2k3iB+Fg@mail.gmail.com>
Date: Wed, 1 Apr 2015 08:20:29 -0700
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Compute time hardness

On Wed, Apr 1, 2015 at 6:23 AM, Gregory Maxwell <gmaxwell@...il.com> wrote:

> On Wed, Apr 1, 2015 at 1:08 PM, Solar Designer <solar@...nwall.com> wrote:
> > yescrypt's claimed area-time product at t_cost = 0 is
> > lower, at (1/3+1/3)/(1/2+1/3) = 80% of what's theoretically possible for
> > its running time (e.g., of what TwoCats tried to achieve).
>
> Speaking of what TwoCats tried to achieve...
>
> Has anyone done any estimates of the compute-time hardness of the
> various finalists at various setting levels?  E.g. what is the cost
> for attacker with infinite memory area and bandwidth? (sorry if I've
> missed a thread; just point me to it if I have)
>

This is pretty difficult to guestimate, since we don't seem to have any
highly experienced deep submicron IC designers involved on this list.
Maybe we should try to rope one in from Intel, AMD, or NVDIA?

We see good evidence that a multiply is at least 3X more computationally
expensive.  If it we not, Intel would have a lower latency multiplier.
Most of the delay around an ADD operation is in moving the data around, not
doing addition, so there's an additional speed factor we are not sure of.
I think it will be pretty high, like 8X or 16X compared to a 32x32 -> 64
multiply.

Alexander's technique of counting sequential operations, and giving
multiply more weight seems reasonable to me, though he's once again
under-cutting himself by only claiming a multiply is worth 3 additions.
Use 8 and you'll be closer to reality, IMO.

The algorithms also need careful analysis to be  sure an attacker can't
start computing the next operation before the previous one is done, or at
least take into account the potential speedup.  A chain of additions, for
example, let's you propagate the low bits very fast compared to the high
bits.  I feel good about both the reduced Blake2b round and Yescrypt's
PWXFORM round here.

Bill

Content of type "text/html" skipped