Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 18 Nov 2012 03:07:54 -0800
From: Colin Percival <>
To: Solar Designer <>
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 | | 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.