Message-ID: <20140412081514.GA17165@openwall.com>
Date: Sat, 12 Apr 2014 12:15:14 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Geeks like us can't write...

On Sat, Apr 12, 2014 at 12:28:33AM -0400, Bill Cox wrote:
> My favorite author in this competition is Solar Designer.  I just love
> his code.  It's that simple.  I'm also a big fan of  Samuel Neves
> code, but he didn't submit an entry, though many of us are using his
> Blake2 implementation.  I read all the authors' papers.  The best
> paper, IMO, may be Catena.
> 
> Here's the sad part.  In the PHC, to varying degrees, good code is
> anti-correlated with good writing.  I may not be able to write a good
> paper, but I can tell when I'm reading one.  I can also tell when I'm
> reading inspired code.

While I have no problem accepting the "can't write" criticism, I think
in case of yescrypt the poor quality of the paper is largely caused by
me allocating a disproportionate amount of time to design and code, and
very little to writing the paper.  I could do it the other way around,
but I felt it'd be worse to need to make invasive changes to design and
code after making the initial submission than merely to want to describe
the existing design better.  I've been meaning to take care of the
latter after having met the formal requirements for the submission -
thus, in revisions to be made after the submission deadline - but
various work has distracted me from that so far.  (Of course, ideally I
should have allocated time way before the deadline.)

> My wife is a writer.  She married me anyway :-)  I hear her complain
> all the time that her interns or other writers "buried the lead",
> which is when we don't put the most interesting stuff at the top to
> help those of us who are too lazy to read papers carefully.
> 
> Solar Designer, as well as several of the more amazing coders, buried
> the lead.  I want to fill in the "Strengths" section of the wiki for
> Yescrypt, and I thought just taking a quick peek at his paper would
> help me with the bullet points.  Nope!  The Catena paper made whole
> chapter headings out of bullet-point strengths, but Yescrypt buries
> the goodness in the details.

Yeah.  Basically, I focused on meeting the formal requirements for the
submission, which primarily required the specification (in the case of
yescrypt, it's how it differs from scrypt).  What I think I should do,
if/when I do find time, is re-arrange the text such that I start with a
list of bullet points, then proceed with specification, and then proceed
with analysis.  Right now, I have specification intermixed with bits of
analysis, and as you noted there are no bullet points.  (I also need to
add specification of pwxform.)

> Anyway, without a list of bullet points for Yescrypt to copy (like I
> did for Catena) I'm having to do what I suck at: write them myself!

Sorry about that!

> So, what are the most impressive strengths of Yescript, since Solar
> Designer didn't list them at the top of his paper?  I'm thinking:
> 
> - Most full featured and flexible entry in the PHC

Yes, although some other entries have their unique/exotic features that
are not in yescrypt.  I am thinking of Makwa and PolyPassHash.

BTW, I couldn't have included a bullet point like that before seeing a
full set of other entries.

> - Script upwards compatible

"Scrypt".  Yes.

> - Highly tuned, and very fast

Maybe "Highly tunable, and very efficient"?

> - Suitable for a variety of applications and platforms

This overlaps with "full featured and flexible".

I also like to call yescrypt "scalable", in the sense that it provides
adequate security over a wider range of memory cost settings than many
other password hashing schemes do.  In particular, it's stronger than
scrypt at low memory cost settings, and it allows for higher memory cost
settings than bcrypt does.  Similar comparisons may be made against many
PHC entries as well.

> Broad array of tunable defenses (needs it's own list):
> - High external RAM usage, high DRAM bandwidth, high cache bandwidth,
> any one of which can limit an attacker
> - Tested and proven Bcrypt-like GPU defense, even while busting out of
> cache into main memory
> - Compute time hardened with serial multiplication chains
> - Optimised a wide range of CPUs from older AMD to the latest Intel Haswell
> - ROM optimized for improved authentication server performance and defense

Right.

Regarding the "wide range of CPUs", I have to note that (un)fortunately
the current compile-time defaults for pwxform are tuned for fairly
recent CPUs, which means Bulldozer or better, and Sandy Bridge or better.
On e.g. a Pentium 3, these same defaults result in yescrypt losing to
bcrypt in terms of GPU defense.  But the code is scalable down, with the
bcrypt-like anti-GPU defense intact, even for a Pentium 3 - with
different compile-time settings, which I need to make runtime tunable
via the flags.  (Pentium 3 itself might not be relevant these days, but
unfortunately SIMD-less builds are.  This is where bcrypt may win.)

> So, I'm afraid my effort at listing "Strengths" bullets is going to
> fall short.  Several outstanding coders in this competition have a
> similar problem.

I fully agree that it's better when the authors themselves write good
descriptions.

I appreciate your help with this!

Alexander

Powered by blists - more mailing lists