phc-discussions - Re: [PHC] Transforming hash to different cost setting

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: <20140322220213.GA25541@openwall.com>
Date: Sun, 23 Mar 2014 02:02:13 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Transforming hash to different cost setting

On Sat, Mar 22, 2014 at 05:00:41PM -0400, Bill Cox wrote:
> On Sat, Mar 22, 2014 at 8:53 AM, Solar Designer <solar@...nwall.com> wrote:
> > On Sat, Mar 22, 2014 at 08:39:21AM -0400, Bill Cox wrote:
> >> I use Christian's solution for this.  It loses up to 2X in terms of
> >> time*memory security, so users would not use this up-front.
> >
> > Actually, up to 3x - that is, Catena's area-time cost to attacker
> > converges to 1/3 of what's optimal, after many upgrades.  With
> > (acceptably) higher granularity of upgrades, we can improve this to 3/5
> > of optimal.  (I posted these numbers in here a few months ago.)
[...]

> I know the answer will make me feel dumb, but if area-time is
> approximated as peak memory usage * time, and we fill memory at a
> constant speed (as in TwoCats - doing one read and write all the time
> while filling memory), then why would it be worse than 2X lower peak
> memory * time?  For a given runtime, instead of filling 2GiB, I could
> fill 1MiB, 2MiB, 4MiB... 1GiB.  The time is the same and the peak
> memory usage is half.

Just don't approximate area-time as "peak memory usage * time" for the
whole upgraded hash, because its memory usage drops back to zero on each
upgrade, whereas a never-upgraded hash's memory usage is monotonically
non-decreasing.  We need to compare the area below those "curves", but
they're of different shape, so we can't make conclusions on how the area
differs by looking only at the peak.

Here are the numbers:

http://thread.gmane.org/gmane.comp.security.phc/504/focus=639

Alexander