Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 13 Jan 2014 10:41:01 +0400
From: Solar Designer <solar@...nwall.com>
To: crypt-dev@...ts.openwall.com
Subject: Re: lyra

On Sat, Jan 11, 2014 at 11:22:54AM +0400, Solar Designer wrote:
> 2. The claimed higher than scrypt's memory usage for same running time
> would be very nice.  Whether it is actually achieved, I am not sure.
> Where would it come from?  scrypt spends half its time on filling
> memory, and it uses Salsa20/8 for that.  Is it claimed that BLAKE2 is
> somehow a lot faster than Salsa20/8?  I'd expect these to be roughly
> similar speed.  Maybe the speedup the authors observed was due to
> implementation detail (comparison against less-than-optimal scrypt
> implementation and build) rather than due to the design of Lyra.

The paper http://eprint.iacr.org/2014/030.pdf says on page 21 that
scrypt's -nosse was compared against Lyra, because there was no
SSE2-enabled implementation of Lyra.  This does sound like a fair
comparison (although a comparison of two SSE2-enabled versions would be
of more practical relevance).  The result is unexpected (by me) and not
explained (by paper authors), though.  Why would non-vectorized BLAKE2
(12 rounds?) perform so much faster than non-vectorized Salsa20/8?
I think more testing is needed to figure out what went wrong with this
test (leading to a weird conclusion). ;-)

> 5. It appears that higher T, as required for Lyra's TMTO resistance,

Actually, Lyra might (and probably does) have some TMTO resistance
relative to scrypt even at T=1.  It looks similar to scrypt with Anthony
Ferrara's write into V added - an approach I posted about in here
earlier.  (I say "might" rather than "does" only because I haven't
figured out and considered all of Lyra's peculiarities yet.)

In fact, this results in the parallelized variant of Lyra introduced on
page 15 having lower area-time than escrypt with p>1 (Lyra gives each
thread its own read-write region, whereas escrypt quickly moves on to
having all threads read from the same shared region).  It's the same KDF
design tradeoff I posted about in here recently, and Lyra resolved it in
favor of lower area-time with higher TMTO resistance, whereas in escrypt
we mostly choose higher area-time with lower TMTO resistance instead.

> would have an undesirable side-effect of reducing Lyra's memory usage.
> In fact, from that same summary table the "Sequential (Default)" memory
> usage for scrypt is O(Rs), but for Lyra it's only O(Rl*C), which means
> O(Rs/T*C).  The area-time cost of attacks decreases accordingly.
> I think this is not an acceptable tradeoff in KDF design; it's no good
> to pay with so much lower memory usage merely for higher TMTO resistance.

I still think so, but I'd like to add that with low T (lower than what
Lyra authors recommend), it's not that bad.  With low T, we can estimate
memory usage as Rs/2 for scrypt and Rs/(T+1) for Lyra (for same running
time), so e.g. for T=2, Lyra's is 2/3 of scrypt's.  This reduction in
memory usage is not great (unless the defender doesn't want to use more
memory anyway), but it is within consideration.  At T=3, Lyra's memory
usage is 1/2 of scrypt's, which I think is usually undesirable despite
of the TMTO resistance benefits - again, unless the defender doesn't
want to use more memory anyway.

T=5 recommended in the Lyra paper feels excessive and non-optimal.  It
is based on the benchmark against scrypt (both for non-optimal builds)
rather than on what would optimally increase attack costs on Lyra.

To summarize, Lyra may be OK in this respect at T=1 and T=2, and at
higher T in the special case when we want a long running time and
deliberately don't want to use more memory (accept having much lower
area-time cost of attacks than we could have for same running time).

Alexander

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ