phc-discussions - Re: [PHC] How about memory*time comparisons?

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]

Message-ID: <20150403183117.GA27455@openwall.com>
Date: Fri, 3 Apr 2015 21:31:17 +0300
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] How about memory*time comparisons?

On Fri, Apr 03, 2015 at 08:18:35AM -0700, Bill Cox wrote:
> I see a lot of discussion about TMTO, cache timing resistance, and lately a
> good discussion on compute time hardness, which is excellent.
> 
> However, I worry that we're not focusing enough on the most obvious and
> important metric: memory*time.  I still have not seen a chart showing
> memory*time defense.

Isn't it the same as a memory vs. time chart at each scheme's lowest
supported t_cost?  e.g. look at 1 second and see how much memory each
scheme uses by that point.  This will be numerically the same as
memory*time.

I am simplifying a little bit, since average and not peak memory usage
matters for some attacks.  But overall it's about right.

> The right way to measure memory*time is with t_cost at the minimum secure
> value.  For Yescrypt, that's with t_cost == 0

Right.

> and 2 rounds rather than 6
> for the single-thread case, and more rounds for the multi-thread case.
> You're supposed to choose the rounds to gain compute time hardness
> _without_ losing memory*time defense.

I'm not so sure.  While I could give up some compute time hardness if
others do the same and that's required to be competitive, I am unhappy
about giving up bcrypt-like GPU-unfriendliness, which goes along with
yescrypt's pwxform too.  Of course, other fast PHC finalists probably
don't have as much of bcrypt-like GPU-unfriendliness, or they'd run
slower, so arguably dropping it is needed to be competitive.  But I
dislike dropping it just for the sake of competition.

As I've shown in the other message, with proper multi-threaded use of
yescrypt the cost of PWXrounds = 6 in reduction of (defensive)
memory*time (which supposedly correlates with attack's) is just 10%.

This is one of the reasons why I'm unhappy that the charts so far only
go up to 4 threads max.

> Plots showing memory vs time with
> higher t_cost seems wrong and misleading to me.

Yes, to me too.  They have their specialized uses, such as recently to
compare yescrypt's and Lyra2+BlaMka's compute hardness, but we should
not forget that for actual use the lowest supported t_cost is recommended.

> The same goes for plots
> where the number of rounds was chosen to be too low.

You mean lower than necessary to maintain highest memory*time?

Alexander