Message-ID: <20150213220211.GA12585@openwall.com>
Date: Sat, 14 Feb 2015 01:02:11 +0300
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Tradeoff cryptanalysis of Catena, Lyra2, and generic memory-hard functions

On Fri, Feb 13, 2015 at 11:36:58AM -0800, Bill Cox wrote:
> Interesting analysis.

Yes, and helpful!

> Also, while Lyra2 uses one Blake2
> reduced round (a good choice, IMO), Yescrypt uses 6 of it's new round
> function.  When using Yescrypt in production, I can easily change 1 line
> and improve it's performance greatly for single-threaded applications.
> Lyra2 is already using only one round, and I will not have that flexibility.

In the tweaked yescrypt submission, I describe yescrypt's pwxform rounds
count as one of the "tunable parameters (currently compile-time)",
called PWXrounds.  (FWIW, I recently performed testing that the current
tweaked yescrypt meets my randomness tests of the V array even with
PWXrounds = 1.  As well as with 1000000, to take another extreme.)  I am
hoping that, unless there are objections, we'll provide a runtime way to
tune and encode these parameters (perhaps with some limitations on the
possible values, to reduce complexity of optimized implementations) in
an extended API.

> In your generic attack, for TMTO > 1/2, for each new value computed, a
> significant percentage of all prior values must be recomputed, leading to a
> computation effort proportional to N^2, where N is the number of original
> computations without a TMTO.

If I am reading this right, there's an overall memory*computation
reduction when using 1/2 of memory (meaning this attack is likely of
practical value to GPU implementations), almost no change for 1/3, and
an overall increase for memory reduction to below 1/3.  And given
excessive computing resources, it is possible to do much better due to
the much slower increase in depth penalty.

> I like that your Table 6 does not claim
> improved memory*time based on tree depth, and instead simply reports both
> recomputations and depth.

I like this too.  It is useful to be able to consider these separately.

> However, Table 6 is heavily dependent on N,
> which is not stated.  For very large N, even the 1/3 TMTO attack will have
> very high recomputations.  Maybe state N?

My understanding is that the algorithm on the previous page roughly
corresponds to yescrypt's SMix1, so N = T.  (yescrypt's SMix2, which is
where t comes into play, is different in that its writes are random
rather than sequential.)  I guess g() is assumed to provide r_i
uniformly distributed in the range 0 to i-1, with no specific pattern.

When analyzing yescrypt in this way, it should be taken into
consideration that its Wrap() function is different: it provides uniform
distribution over a (moderately smaller) moving (and growing) window
instead.  In my simulation (see extra/sim-at-output.txt, loop1_pow2), it
hit 56.78% different elements vs. simple uniform random (modulo
division) hitting 50.00%, and the highest number of hits per element is
twice lower.  Maybe this will make yescrypt's SMix1 more resistant to
TMTO, especially relative to its lower claimed pre-TMTO area-time cost
of N^2 / 3 (this is what I use for deciding on SMix2's iteration count
at t = 0).

And of course SMix2 will add to that (probably a lot).

In extra/sim-tmto.c, I include a TMTO attack on SMix2's random
read-writes (at p = 1), but it assumes scrypt's original SMix first loop
rather than yescrypt's SMix1 above.  (OTOH, as specified it corresponds
to t = 2 rather than t = 0.  I forgot to include a newer revision of
that program adjusted for t = 0.)  It would be helpful to come up with
TMTO attacks on the full yescrypt's SMix1 and SMix2 combined, and put
the results in some table.  Naturally, it is expected that together
SMix1 and SMix2 will work better than individually.

Thanks,

Alexander

Powered by blists - more mailing lists