Date: Sun, 18 Nov 2012 03:07:54 -0800 From: Colin Percival <cperciva@...snap.com> To: Solar Designer <solar@...nwall.com> CC: scrypt@...snap.com, crypt-dev@...ts.openwall.com Subject: Re: scrypt time-memory tradeoff 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
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.