Date: Sun, 30 Sep 2012 15:25:16 +0400 From: Solar Designer <solar@...nwall.com> To: Colin Percival <cperciva@...snap.com> Cc: crypt-dev@...ts.openwall.com Subject: Re: using scrypt for user authentication Colin, On Mon, Sep 10, 2012 at 03:55:22AM -0700, Colin Percival wrote: > I said 16 MB because that's what you end up using given the parameters > (N, r, p) = (2^14, 8, 1) which I mentioned in my paper as being good for > 100 ms of KDF computation. Obviously that can be adjusted, but you can't > use more than 16 MB of RAM unless you spend longer than 100 ms (or have a > faster CPU than what I had in my laptop 3 years ago -- I'm guessing that > we're at 32 MB of RAM for 100 ms by now). 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. 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. Trying to see how much further we can go by replacing Salsa20/8 with something else (or simply reducing the number of rounds), I tried placing a "return 0;" at the start of salsa20_8(). With this, I am able to fit 64 MB in 100 ms. Not that much of a change. :-( This is on an older server, though (Xeon E5420's, and memory bandwidth corresponding to that epoch). I'll re-test on a newer one. If the desired duration is 1 ms, scrypt is unreasonable to use at all - at those settings, it's weaker than bcrypt. Do you have thoughts on a possible revision of scrypt to allow it to use more memory at these low durations? I think it should be possible to have a memory-hard function that would let us use hundreds of MB at 100 ms and a few MB at 1 ms, on currently typical server hardware (memory bandwidth of ~5 to 10 GB/sec). Scalability will be poor, though (that is, if we run multiple instances on the different CPU cores, they'll compete for the memory bandwidth as we'd have to approach it closely even in just one instance). Could something like Elias Yarrkov's zen32(), but adjusted to access entire cache lines, be it? What do you think of it? I guess you've seen the postings on the cryptography list. For those who haven't, we're talking about the KDF portion of http://cipherdev.org/dhbitty.html Thanks, Alexander
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.