Re: Scrypt questions

[Solar Designer <solar@openwall.com>]

Barry,

Browsing the list archive for scrypt, I realized that no one replied to
your questions.  I'll do so now.

On Sat, Dec 15, 2012 at 12:34:03PM -0500, Barry Steyn wrote:
> *Question 1*
> 
> > Regaring the C scrypt implementation, after the decrypt call regenerates
> > the key and compares it against the hmac, it will reject everything right
> > there if your password is wrong - but if it's right, it'll proceed to *
> > also* decrypt the data package.
> 
> Is the above statement correct? If so, this is doing a lot of extra work
> the attacker won't have to perform - they don't even have to derive 64
> bytes, just the 32 needed to check the signature. Therefore should one
> ignore the decrypt implementation in the C implementation?

The statement is correct.  If you intend to reuse the scrypt KDF for
some other purpose, of course you should not include the AES decryption
code from the scrypt tarball.  It is not part of the scrypt KDF.

> *Question 2*
> 
> > the decrypt utility's "max time" limitation is wrong for password hashing
> > - each time decrypt is called, it estimates your system's speed, and does
> > some "guessing" as to whether it can calculate the key within max time -
> > which is *more* overhead your attacker doesn't have to do, but also means
> > it could start rejecting passwords under heavy load.
> 
> Can someone with knowledge please comment on the above quote? This is a
> serious problem if passwords are rejected under heavy load.

Similarly to the above, this is part of the scrypt file encryption
program, not part of the scrypt KDF.  You won't have that code if you
reuse the scrypt KDF somewhere else.

> *Question 3
> *I realise that it is a security flaw for key derivation functions to work
> quickly, but that must also be balanced with an acceptable throughput for
> any application that it will be used for. Does someone have any stats for
> the throughput of scrypt? And could it conceivably be used for a large
> company (lets think Google or Amazon) without it slowing down the
> authentication process too much?

My opinion is that scrypt as-is is not a good enough fit for password
hashing - it's not obviously better than bcrypt at high throughput (1000
per second or more) on current server hardware.  Its memory usage
becomes lower than it was designed for.  However, it is possible to
build a password hashing scheme based on concepts from scrypt and more,
that would be suitable for use at large companies like those you
mention.  Here are some of my thoughts on how this may be done:

http://www.openwall.com/presentations/ZeroNights2012-New-In-Password-Hashing/

... and this also has "stats for the throughput of scrypt" that you
asked for. :-)

(No, I am not suggesting that you revise scrypt on your own.)

Alexander