Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 09 Sep 2012 17:52:12 -0700
From: Colin Percival <cperciva@...snap.com>
To: crypt-dev@...ts.openwall.com
CC: Solar Designer <solar@...nwall.com>
Subject: Re: using scrypt for user authentication

On 09/02/12 08:13, Solar Designer wrote:
> On Tue, Aug 07, 2012 at 10:54:36AM +0200, Pavel Kankovsky wrote:
>> The paper claims the cost of scrypt with (N, r, p) = (2^14, 8, 1) is 
>> approximately 35 times higher than the cost of bcrypt with cost = 11

... if you're building ASICs to crack passwords.

> We got a curious real-world data point due to Litecoin using scrypt with
> (2^10, 1, 1), which corresponds to 128 KiB.  I guess the (misguided?)
> intent was to use L2 cache instead of RAM.

Yes, that definitely qualifies as "misguided".

> IIRC, scrypt was designed
> not to bump into RAM bandwidth on typical computers anyway

Correct.

> Thus, we can see that scrypt with improper settings can be worse
> than bcrypt for a very realistic attack.  (For attacks with ASICs,
> things may be different, but attacks with GPUs are relevant too.)

This doesn't surprise me at all.  The idea behind the design of scrypt
is to make the memory-time product the deciding factor in cost -- and
to stay far away from other bottlenecks on modern hardware (e.g., L1
cache bandwidth) so that we can use as much RAM as possible.

In some ways -- available parallelism and RAM:compute die area ratio --
GPUs fall somewhere between CPU and ASIC, but on "random access to small
amounts of RAM" I'm not at all surprised to find that they are further
in the "CPU" direction than CPUs themselves.

> Overall, I think scrypt at 1 MiB is not a good replacement for bcrypt
> currently.  We need bigger settings.

I agree.

> (And if we go for much bigger
> settings, this may imply a need to limit concurrency when scrypt is used
> on authentication servers.)

What sort of authentication servers are you running where you only have
1 MB of RAM per CPU core?

> We might also want to have a tradeoff-defeating variation of scrypt, as
> Anthony Ferrara suggested or otherwise.  It appears that this would make
> scrypt maybe a factor of 2 more resistant to attacks with current GPUs
> at Litecoin's low settings and perhaps a lot more at bigger settings
> (where the total GPU card's RAM size is more easily hit if the tradeoff
> is not used in an attack).  Maybe this property should be configurable
> (a Boolean parameter, to be encoded along with the resulting encrypted
> data or password hash).

This seems like an attempt to patch over the problem of "scrypt not being
used as intended".

-- 
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

Your e-mail address:

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.