phc-discussions - Re: [PHC] Scrypt can have highest time*average memory cost

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: <20140328210136.GA29271@openwall.com>
Date: Sat, 29 Mar 2014 01:01:36 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Scrypt can have highest time*average memory cost

On Thu, Mar 06, 2014 at 09:06:37AM -0500, Bill Cox wrote:
> I have been using time*cost as my basic measure of memory-hard KDF
> performance, but up to now I've only used peak memory usage rather
> than average.  Scrypt writes memory in the first loop, then reads
> memory in an unpredictable fashion in the second, while I read and
> write at the same time until memory is full.  It turns out that the
> Scrypt technique can achieve a higher average time*memory cost for the
> entire run, by 50%, even if both ways result in the same peak memory
> usage.
> 
> Peak memory usage is a very important number, but if an attacker is
> using a multi-CPU system with a very large shared memory, then he
> probably cares more about average memory than peak.

You're normalizing for defender's peak memory usage, then looking at
average memory usage.  That's one way to do it, yes.

However, what if we normalize for defender's time per hash computed?
When we do that, it turns out that scrypt reaches its highest normalized
AT cost at 2*N (just the way it's defined), but yescrypt (yes, that's
the new name) reaches the highest normalized AT cost (1.5 that of
scrypt) at 4/3*N (and it drops to 4/3 of scrypt's at 2*N), and other
schemes where the entire arena is randomly accessed while being filled
(no sliding-power-of-2) potentially/theoretically reach the highest
normalized AT cost (twice that of scrypt!) at N (no need for SMix's
second loop at all, then - it only hurts this potential/theoretical
highest normalized AT cost).

When I say potential/theoretical, I mean that in those cases (unlike in
current yescrypt) other factors appear, which may negatively affect the
AT cost to real-world attackers: non-uniform distribution of accesses
(allowing for potentially beneficial use of 2+ types of memory with
different access speed or/and area or/and dollar cost), maybe slightly
fewer different memory locations being read.  I previously wrote about
those issues.  There are a few other considerations as well, including
peak memory usage cost to defender (which the defender must provide
capacity for, including for the worst case of highest concurrency and
most unfortunate (de)sync).

I did not realize the potential improvement was as high as 2/1.5 = 4/3,
though.  I thought it was 1.5 / (4/3) = 9/8 based on AT cost seen at 2*N
time (same as scrypt's), not having analyzed whether and how the
maximums may have moved (I did that now).  I was willing to trade this
9/8 potential improvement for the greater certainty that the
sliding-power-of-2 approach provides.  Perhaps this is still a good
tradeoff even with 4/3, but it's not as good as I had thought.  Anyway,
I am sticking with the sliding-power-of-2 approach for now, and will
revise/recommend 4/3*N as the default running time (achieving the 1.5
normalized AT cost maximum vs. scrypt's).  This is actually good news to
me (higher than I had thought normalized AT cost is reached, and at a
lower running time).

scrypt
t       AT      AT/t    ATnorm
1.00    0.00    0.000   0.000
1.05    0.05    0.048   0.181
1.10    0.10    0.091   0.331
...
1.90    0.90    0.474   0.997
1.95    0.95    0.487   0.999
2.00    1.00    0.500   1.000 <==
2.05    1.05    0.512   0.999
2.10    1.10    0.524   0.998

pow2
t       AT      AT/t    ATnorm
1.00    0.33    0.333   1.333
1.05    0.38    0.365   1.391
1.10    0.43    0.394   1.433
...
1.25    0.58    0.467   1.493
1.30    0.63    0.487   1.499
1.35    0.68    0.506   1.500 <==
1.40    0.73    0.524   1.497
1.45    0.78    0.540   1.490
...
1.90    1.23    0.649   1.367
1.95    1.28    0.658   1.350
2.00    1.33    0.667   1.333
2.05    1.38    0.675   1.317
2.10    1.43    0.683   1.300

wrap or mod
t       AT      AT/t    ATnorm
1.00    0.50    0.500   2.000 <==
1.05    0.55    0.524   1.995
1.10    0.60    0.545   1.983
...
1.90    1.40    0.737   1.551
1.95    1.45    0.744   1.525
2.00    1.50    0.750   1.500
2.05    1.55    0.756   1.475
2.10    1.60    0.762   1.451

Alexander