[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20140113064101.GA14424@openwall.com>
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
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
