[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20120930112516.GA12111@openwall.com>
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.
