[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <50A8C18A.2010405@tarsnap.com>
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.
