Message-ID: <20141021135704.GA10425@openwall.com>
Date: Tue, 21 Oct 2014 17:57:04 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] simplifying yescrypt

On Mon, Oct 20, 2014 at 11:47:15PM -0400, Bill Cox wrote:
> Not coincidentally, the Lyra2 team and I realized you had some great
> advice on the forum, and acted on it.

I think you are (unintentionally) exaggerating my influence on Lyra2.
Maybe we'll see it in a future revision of Lyra (as there's been some
talk on adding multiply hardening chains), but I don't feel I influenced
Lyra2 much.  I've been advocating use of lower values for the T
parameter than what Lyra designers recommended, and I felt (and
explained why) the logic behind recommending high T was flawed, but it's
been a configurable parameter from the start.

> Lyra2 is simpler, but when it has multi-threading, some TMTO defense
> for it, better compute-time hardening, and maybe improved GPU defense,
> it will increase from it's moderate complexity to high complexity.
> You simply can't compete in all those security dimensions at the same
> time otherwise.

Yes, that's my opinion too.

> On 10/20/2014 09:58 PM, Solar Designer wrote:
> > Here's what I'd change in -lite:
> > 
> > - Drop support for (ye)scrypt's p parameter.
[...]
> 
> Sounds good.
> 
> > - Maybe: drop support for classic scrypt hashes. (Have only native
> > yescrypt hashes supported in -lite.)
> 
> Yes, in Yescrypt-lite, please drop backwards compatibility with Scrypt.
> 
> > - Maybe: drop support for a ROM.
> 
> Yes, in Yescrypt-lite, please drop ROM support.

Thanks for commenting on this.

> I am tempted to suggest also aproviding an Yescrypt-anorexic.  In my
> "SkinnyCat" algorithm, I deleted multiplication chain hardening,
> multi-threading for taking advantage of all those CPU cores,
> small-memory reads for GPU defense, the t_cost parameter (of which I
> remain not much of a fan), variable lanes, long input parameters, the
> init-update-finalize API, variable block sizes for cache tuning, and
> the early memory overwriting TwoCats does to provide basic protection
> in case memory gets written to swap or hibernated to disk.
> 
> The result, in my biased opinion, is simple, elegant, and fast.
> However, there's no way I'd use it in an application like TrueCrypt!
> 
> However, there are *many* applications where I feel something that
> simple is warranted.

Is the full TwoCats able to compute all SkinnyCat hashes?  I guess not?

I dislike the idea of having a cut-down yescrypt that is not a strict
subset of the full yescrypt in terms of compatibility of hashes, unless
I were to abandon the full yescrypt at the same time (which I'm not).
My proposed yescrypt-lite is strictly a subset of full yescrypt.

> I am sure that this principle can be applied to Yescrypt.  All you
> have to do is eliminate everything but the part you love so much about
> the algorithm, you'd be sad to see it go.  What would you keep if you
> had to keep it under 200 lines of code?  I personally would like to
> see the parallel-wide-transform in a simple piece of code that
> highlights it.  That t_cost == 0 behavior is what I'd personally keep.
>  The hybrid architecture with the partial second loop is cool.  I'd
> also keep the PBKDF2-SHA256 fix you invented.  It might bust a bit
> beyond 200 lines :-)

The above description sounds like it's my proposed yescrypt-lite, except
that I was planning on keeping t configurable (there's very little
complexity associated with that).

Note that even if I keep only a pwxform-using mode, I can't fully drop
Salsa, because I use it to mix the lanes together.  Well, I could use
SHA-256 in its place, not to have two crypto primitives, but efficiency
would suffer somewhat, needing higher values of r to repair that (and
thus not depending on low latency RAM as much, which may benefit some
attackers).  It's unlikely I'd switch to SHA-256 in that place in full
yescrypt, because it can afford to have Salsa (complexity wise) and
needs Salsa for the scrypt compatibility mode.  So using SHA-256 in
there in -lite would make -lite incompatible, or would require that I
introduce special -lite compatible mode (with SHA-256 instead of Salsa)
in the full yescrypt, which would be counter-productive as it relates to
simplifying yescrypt (sure -lite would become simpler, but the full
yescrypt would become even more complex).

> ROM in memory seems like the way I'd want to use Yescrypt, if I were
> doing an authentication server.  ROM on SSD is cool, but I think you
> can drop the frequency mask.

OK.  Thanks.

> I think providing a simple "classic" API, and a simple Yescrypt basic
> API would be good.  I saw Catena had a simple API (the one I'd most
> likely use in real life), and called it the "naive" API.  It is naive,
> but we can't expect our users to be knowledgeable about all the issues
> involved in password hashing.  Even providing both a t_cost and m_cost
> parameter is asking too much from users.  We need a "don't make me
> think too hard" API.
> 
> At the same time, is there any reason not to reveal more interesting
> parameters in an "extended" API?

Yes, there is: supporting too many combinations of parameter/flag
settings complicates reviews, testing, benchmarking.  It may result in
or expose more bugs, too.

> > (On the other hand, I need to add a new flag for enabling cache
> > timing resistance.  So get rid of separation between the existing
> > flags, and add that new flag.)
> 
> If you are adding a cache timing resistant loop, I'd like to see it in
> the first loop (or some portion of it) in Yescrypt mode by default.
> If it weakens password security when an attacker does not have
> cache-timing data by too much, then I'd say just drop the feature
> entirely.  There is a reason we do unpredictable password derived
> addressing.  It makes password hashes more secure.  How much
> complexity to add and how much weakening vs traditional GPU farm
> attacks you can tolerate is a tough trade-off.

Your opinion on this makes sense to me.  I'll consider avoiding that
extra flag.

> > - Without scrypt compatibility (as in -lite) and when in native
> > mode, I can replace Salsa with ChaCha.  If a given build lacks
> > scrypt compatibility (would be true for -lite), this would probably
> > make it slightly simpler by eliminating the need for 32-bit word
> > shuffling associated with interfacing with Salsa.  The drawback is
> > that full yescrypt would become more complicated, requiring both
> > Salsa (for scrypt compatibility) and ChaCha.  This is why I stayed
> > with Salsa only so far.

> Doesn't the PWX loop dominate runtime?

Normally, it does.

> Assuming this is the case, I'd say keep Salsa.

OK.  Note that I am considering replacing it with ChaCha primarily not
for performance reasons, but to simplify the code in -lite (avoiding the
shuffling), although this would have a complexity cost for the full
yescrypt (need Salsa for scrypt compat, and then would also need ChaCha
for native yescrypt).  Perhaps it's not such a great idea, as it has
similar complexity drawback to using SHA-256 in that place in -lite.

> I do wish that could be in a library,

I think it can be in a library.  In fact, at some point PHP had Salsa*
support, bundled in the PHP tree.  Unfortunately, it saw no users and
was dropped before anyone thought of its relevance to scrypt.  I did not
look closely into whether that support was in fact usable for scrypt.

> the way Bcrypt calls Blowfish.

No.  bcrypt actually cannot be implemented on top of standard Blowfish
(or we would be implementing bcrypt e.g. for older PHP already, which
has Blowfish but not bcrypt builtin).  This is why Steve introduced
battcrypt in this competition.

> There's no point complicating a memory-hard password
> hashing algorithm by dumping code for a cryptographic hashing
> primitive into the heart of it.  Was it the 8-rounds that required a
> custom implementation?

No, 8 rounds is actually one of the standard choices, albeit a not very
common one (it's the lowest one of them).  This is actually a reason why
I am somewhat uncomfortable about your (earlier) suggestions to use
lower Salsa round counts.

Unfortunately, there may be issues with crypto libraries not exporting
the Salsa20 core on its own, and only providing stream encryption.  The
nonce can get in the way, but perhaps there's a way around that (pretend
we're encrypting a non-initial portion of the data stream, which is
something the API is likely to support).  This is worth looking into,
but I am not spending my time on it now.

Alexander

Powered by blists - more mailing lists