Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <506A01CB.8040000@tarsnap.com>
Date: Mon, 01 Oct 2012 13:49:15 -0700
From: Colin Percival <cperciva@...snap.com>
To: Solar Designer <solar@...nwall.com>
CC: crypt-dev@...ts.openwall.com
Subject: Re: using scrypt for user authentication

On 09/30/12 04:25, Solar Designer wrote:
> You're right about the 16 MB / 32 MB, and I agree that 100 ms is a sane
> time to spend hashing as it relates to user experience with interactive
> logins.  However, based on some back of the envelope calculation I did,
> 100 ms might not be affordable when the number of users is very large
> (millions), logins are frequent (millions per day), and accounts are of
> relatively low value.  I think reasonable values are in the range 1 ms
> to 100 ms.

Here's my back-of-the-envelope calculation:  Assume 100 ms / 32 MB, a 25%
load factor, and we're using EC2 c1.medium instances at $0.165/hour (which
is far more than you'd pay setting up a cluster).  That's 2 cpus * 36000
hashes per cpu-hour * 25% load factor = 18000 hashes per hour, or slightly
under 10 microdollars per hash.  I can't think of any website I enter a
password into more than five times a day -- most are far less than that,
since like most people, I stay cookied on twitter/facebook/etc. -- so I
would cost at most $0.02 per year.

For typical sites, where I stay cookied for weeks at a time, it would be
under $0.001 per year; or even less if they set up their own password hash
cluster instead of renting EC2 instances by the hour.  I'm having trouble
imagining a company which can't afford this.

> Anyhow, even at 100 ms the 32 MB upper limit on what we can use with
> scrypt bothers me.  I want it to be a lot higher.  If we consider the
> memory bandwidth as the hard limiting factor on how much memory we can
> use in 100 ms, it'd be a lot more than 32 MB.

Agreed.  It's possible that I erred too far on the side of caution in using
salsa20/8 in the construction; at Passwords'12 (Oslo, early December) I'm
hoping I'll get a chance to corner Joan Daemen and get some input from him
about this -- I wouldn't be surprised if a reduced-round version of Keccak
turned out to be optimal for this.

> If the desired duration is 1 ms, scrypt is unreasonable to use at all -
> at those settings, it's weaker than bcrypt.

Agreed.

> Do you have thoughts on a possible revision of scrypt to allow it to use
> more memory at these low durations?

I don't want to retroactively redefine scrypt, but that doesn't mean that
we can't discuss a possible replacement for it. :-)

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