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.