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.