Re: scrypt time-memory tradeoff

[Solar Designer <solar@openwall.com>]

On Thu, Jun 30, 2011 at 05:48:01PM -0700, Colin Percival wrote:
> The design of scrypt puts a lower bound on the area-time product -- you can
> use less memory and more CPU time, but the ratios stay within a constant
> factor of each other, so for the worst-case attacker (ASICs) the cost per
> password attempted stays the same.

This doesn't appear to be exactly the case.

SMix consists of two loops, which are roughly of equal cost.  Suppose we
want to halve our memory needs (area).  The first one of two loops will
simply store every other computed value.  The second loop will have a
50% probability that a V_j is present in the half-size table.  When V_j
is not present, the extra cost is recomputing V_j from j-1's.

With full V table, we invoke BlockMix N*2 times.  With a half-size V
table, we invoke BlockMix on average 5 times per 4 loop iterations:
2 times per 2 iterations for the first loop, and 3 times per 2
iterations for the second loop.  We invoke it a total of around N*2.5
times.

Thus, we have halved our memory needs (circuit area) and paid for this
by only a 25% increase in processing time.

Now, if we want to reduce our memory needs a lot more, the situation is
a lot better (for the defender).  Yet for relatively low reduction in
memory needs - like 2x or 4x - the trade-off favors the attacker.  So an
attacker with an ASIC will want to use this, and will reduce the cost.

Am I missing something?  If not, does this possibly affect the dollar
costs presented in the scrypt paper?  Should the dollar cost estimates
for scrypt be multiplied by 0.5*1.25 = 0.625 (that is, reduced to 62.5%
of what the paper says)?

Alexander