Message-ID: <20150325055646.GA7127@openwall.com>
Date: Wed, 25 Mar 2015 08:56:46 +0300
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Overview of PHC Candidates and Garbage-Collector Attacks

Hi Jakob et al.,

On Wed, Oct 29, 2014 at 06:38:26PM +0100, Jakob Wenzel wrote:
> under the following link you can find an overview of all PHC
> candidates which are not yet withdrawn:
> 
> https://eprint.iacr.org/2014/881.pdf

I notice that the "19 Feb 2015" revision of this report still talks
about yescrypt v0.  FYI, yescrypt v1 contains tweaks to make it less
susceptible to garbage collector attacks.  Specifically:

In YESCRYPT_RW mode, when the requested memory usage is at least 16 MB
(per thread if applicable) and N / p is at least 256 (which it almost
always should be), a 64 times smaller instance of yescrypt (and with
forced t=0) is computed first and its result replaces the input password
for further computation.  This means that when invoked with t=0, a fast
hash of the plaintext password has to remain in memory only during
roughly 1/65th of the total running time, after which point only a
weaker yescrypt hash has to remain in memory.  (For higher t, the fast
hash may be replaced relatively even sooner.)  For example, when invoked
for KDF use with the target memory usage of 1 GB, initially a 16 MB hash
is computed.  Also, it is intended that the full-sized yescrypt hash
computation will naturally overwrite the pwxform S-boxes and the initial
smaller portion of the V array.  (This isn't fully taken advantage of in
the current submission package yet, where I minimized diffs from the
previous revision instead.  I intend to correct this in the next update.
That's just an implementation detail not affecting the hash values.)

I think this ~1.5% performance cost (or even less with higher t) is
acceptable for the added garbage collector attack resistance.  I am less
comfortable with the complexity cost, though, and especially with the
semi-arbitrary threshold for enabling this feature.  Unfortunately,
there has to be a threshold like this, or the alternative would have
been to disallow too-small yescrypt calls where N/64 would be too small
to make any sense.  I opted for having the threshold rather than for
adding artificial limitations on what yescrypt parameters are possible.

Additionally, g > 0 results in similar behavior to what I described
above, but with 4x size growth (not 64x) for each of g iterations.
Since with g > 0 each step uses at least the supplied N or higher (never
smaller), there's no threshold needed.  Moreover, this functionality
(and its effect on GC attacks) is available in YESCRYPT_WORM mode as well.

I chose to restrict the initial 1/64 step to YESCRYPT_RW mode for
multiple reasons, including consistency with this mode's naming and ease
of addition of YESCRYPT_WORM functionality without YESCRYPT_RW support
on top of existing scrypt implementations - yes, this is something I'd
expect to be happening.  Those YESCRYPT_WORM hashes will avoid the HMAC
"collisions", will support t > 0 and server relief and upgrades, yet
will require only minimal code additions on top of scrypt to implement.

(I need to update the submission package to reflect the above in the
specification document.)

To summarize, if I understand your definitions correctly, yescrypt v1 is
GC and WGC attack resistant when (g > 0) OR (YESCRYPT_RW flag is set
AND per-thread memory >= 16 MiB AND N / p >= 256).

Thanks,

Alexander

Powered by blists - more mailing lists