Re: scrypt time-memory tradeoff

[Solar Designer <solar@openwall.com>]

Colin,

Thanks for replying!  I understand that you're very busy these days.

On Sun, Nov 18, 2012 at 03:07:54AM -0800, Colin Percival wrote:
> 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". ;-)

Fair enough.

> This is correct, and gives you asymptotically a 2x reduction in area-time
> cost during the second phase.

Yes, but that's 4x for scrypt overall.

> Which falls within the definition of "constant
> factor", and was taken into account in the cost estimates in the paper.

Was it?  That's good news.  IIRC, when I tried repeating your cost
calculations ~2 years ago, I managed to arrive at numbers in your paper
without taking this trade-off into account.  So it must be one of: I
made an error back then, I do not recall correctly, or you did not
actually take this into account.  Should we verify those numbers now?

Alexander