crypt-dev - Re: scrypt time-memory tradeoff

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 18 Nov 2012 15:19:57 +0400
From: Solar Designer <solar@...nwall.com>
To: Colin Percival <cperciva@...snap.com>
Cc: scrypt@...snap.com, crypt-dev@...ts.openwall.com
Subject: Re: scrypt time-memory tradeoff

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