Re: optimized/specialized/revised scrypt implementations

[Solar Designer <solar@openwall.com>]

On Sun, Nov 18, 2012 at 03:10:05AM -0800, Colin Percival wrote:
> On 11/16/12 17:40, Solar Designer wrote:
> > One curious aspect is that it includes a version with 3x interleave
> > (3 instances of scrypt are computed with inter-mixed instructions for
> > greater instruction-level parallelism).  This confirms my gut feeling
> > that Salsa20 core does not contain sufficient parallelism for some
> > current CPUs.
> 
> BTW, taking advantage of CPU parallelism is useful, but not if it also
> allows attackers to take advantage of more parallelism.

Yes, you mention this in the paper - that Salsa20 was chosen for it not
possessing excessive parallelism.  I agree that this is a design
consideration for sequential memory-hard KDFs.  [ In other/older KDFs,
it was not - the more parallelism, the better, because the attacker has
plenty of parallelism anyway and almost no memory cost per instance. ]

I think that we could have a revision of scrypt with tunable low-level
parallelism.  (The existing "p" parameter is not the same.)  Fully
optimized implementations would have to be specialized for certain
values of this extra parameter (and refuse to work or fallback to
generic code for other values).

> One of the topics
> I'm going to address in my passwords'12 talk is the choice of building
> blocks for scrypt... I'll post my slides here once I've written them.

Sounds great.

Alexander