Re: scrypt time-memory tradeoff

[Colin Percival <cperciva@tarsnap.com>]

On 11/16/12 17:20, Solar Designer wrote:
> 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.

Note the words "constant factor". ;-)

> 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)?

This is correct, and gives you asymptotically a 2x reduction in area-time
cost during the second phase.  Which falls within the definition of "constant
factor", and was taken into account in the cost estimates in the paper.

-- 
Colin Percival
Security Officer Emeritus, FreeBSD | The power to serve
Founder, Tarsnap | www.tarsnap.com | Online backups for the truly paranoid