revising scrypt for password hashing (was: scrypt Internet Draft)

[Solar Designer <solar@openwall.com>]

Brian,

I intend to mostly keep this topic - deviating from scrypt proper - to
Openwall's crypt-dev list.  I think the main scrypt list is mainly for
discussion of scrypt proper (unless Colin suggests otherwise).  However,
since you asked in here, I'll reply in here this time:

On Tue, Mar 26, 2013 at 08:57:41PM +0000, Brian Matthews (brmatthe) wrote:
> >I currently don't intend to use scrypt as-is for password hashing
> 
> Could you expand on this? What do you plan on doing in addition to scrypt,
> or plan to change in scrypt?

I plan to experiment with revisions of scrypt, which may end up being
very different from scrypt after a number of changes are made, with the
similarity being in reuse of some concepts from scrypt.  At this time,
though, I am still building on the scrypt codebase to make a
compatibility-preserving subset of my code changes suitable for
inclusion in scrypt proper and/or for use by users of scrypt proper, and
to simplify testing (I can disable my incompatible changes, and with all
of them disabled I get the original scrypt KDF, which passes validation
by test vectors).

What's wrong with scrypt:
http://www.openwall.com/presentations/Passwords12-The-Future-Of-Hashing/mgp00049.html
(see other nearby slides for more info)

Password Hashing Competition:
https://password-hashing.net

To me, scrypt is a very important milestone that introduced new
concepts, but at low durations it's not good enough to be used directly.

Here's what I may change relative to scrypt:

- Optionally defeat the time-memory tradeoff.  I am considering multiple
ways to do it.  So far, I've implemented Anthony Ferrara's idea, which
makes the tradeoff significantly less attractive to attackers, but I
think we can do better.

- Add optional use of a large ROM (intermixed with uses of a smaller RAM).
See my ZeroNights 2012 slides:
http://www.openwall.com/presentations/ZeroNights2012-New-In-Password-Hashing/

- Add more/configurable instruction-level parallelism.
scrypt's Salsa20 may have about 3x less parallelism than is needed to
fully use a modern CPU core, as suggested by a Litecoin miner's current
3x interleave of this code.  In scrypt, having excessive parallelism is
bad, though - which is why it needs to be either configurable or still
limited to the current CPUs' needs.

- Replace Salsa20.

A conservative replacement (it's conservative only in the context of
major changes I am considering) would be ChaCha20, which would make use
of SSSE3 shuffles (more complete use of modern CPUs, hence slower
attacks with some pre-existing non-CPU devices).

Another replacement I am considering is sort of "wide Blowfish" - an
extension of Blowfish to SIMD vectors - which may be shown as being
about as fast to compute as normal Blowfish (key setup) in bcrypt, but
no quicker to attack than bcrypt (including on GPUs and specialized
devices).  An important aspect would be that we'd show that this scrypt
revision is definitely not weaker than bcrypt, even at low memory
settings and with pre-existing devices (rather than ASICs), which can't
always be said of the current scrypt.  Other important aspects may be
scalability to arbitrarily wide SIMD vectors (Salsa20 is limited to
128-bit, whereas CPUs with efficient 256-bit SIMD are about to hit the
market) and making good use of efficient random access to small amounts
of data (smaller than cache line size) in CPUs' L1 data cache.  It's the
latter property of CPUs' that bcrypt benefits from, and this is why
GPU-based attacks on bcrypt are limited to using GPUs' local memory
(which is not large enough to fully use their computing resources).

Some of the above may result in too much increase in code complexity, so
I'd hope to have a more limited implementation with only those of the
above changes that have better benefit/complexity ratios than others.
For an obvious example, support for ROM on SSD (or any external device
needing prefetch) is to be left out from the implementation that I'd
propose for inclusion in a libc's crypt(3).

By the way, are you by any chance asking this question in context of
repairing/replacing Cisco's type 4 password hash?  If so, I recommend
that you use bcrypt for now, and plan to switch to one of PHC selected
password hashing schemes in 2015.

Alexander