[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20140111072254.GA2981@openwall.com>
Date: Sat, 11 Jan 2014 11:22:55 +0400
From: Solar Designer <solar@...nwall.com>
To: crypt-dev@...ts.openwall.com
Subject: Re: lyra
Hi Daniel,
On Tue, Jan 07, 2014 at 06:27:08PM +0100, Daniel Cegie?ka wrote:
> Do you have any opinion on lyra vs scrypt? Lyra is compared to scrypt
> as a safer alternative.
>
> http://lyra-kdf.net/
> http://lyra-leocalm.rhcloud.com/Presentation.pdf
Your question is more appropriate for the PHC discussion list, where
folks are already discussing Lyra. Since the PHC discussion list was
created, I mostly limited my use of the crypt-dev list for recording
ideas/decisions regarding our own KDF / password hashing scheme design.
Yes, there were some recent exceptions to that, but mostly from threads
that were started here before the PHC discussion list was setup.
Since you asked in here anyway, here are some quick comments:
0. Lyra is a very welcome upcoming PHC submission.
1. Disclaimer: I don't fully understand Lyra yet and am not yet
convinced that what's claimed is actually achieved.
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.
3. The claimed TMTO resistance would also be very nice, although it's
arguably even nicer when it's optional (like we have in the current
development escrypt tree), because there are some defender's uses for
scrypt's (deliberate) TMTO-friendliness too.
4. The summary table on slide 28/36 (page 31 in the PDF) gives different
meaning to R for scrypt vs. Lyra. To compare the "Intermediate states"
and "Memory-free" times for scrypt vs. Lyra, they first need to be
normalized for same "Sequential (Default)" running time. Let's use Rs
to refer to scrypt's R, and Rl to Lyra's. We have Rl=Rs/T, so that
O(Rl*T) would match scrypt's O(Rs) (normalization for same running time).
For memory-free running times, this gives us O(Rs^2) for scrypt and
O((Rs/T)^(T+1)) for Lyra. This is still reasonably good for Lyra, but
not as good as the slide makes it appear at first.
5. It appears that higher T, as required for Lyra's TMTO resistance,
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.
6. Including the C multiplier for Lyra, but not the r multiplier for
scrypt may be misleading. There's not really a difference here, but the
table makes it appear as if Lyra had an extra multiplier on the memory
usage.
7. The table somehow does not list "Intermediate states" Memory and Time
for scrypt, even though such states do exist for scrypt, and are
arguably of more practical relevance (for both scrypt and Lyra) than the
extreme memory-free case. It'd be nice to compare those.
8. Other TMTO-discouraging changes relative to scrypt had been proposed.
It'd be nice to see how Lyra compares (not trivial to do).
9. I noticed a few weird things on the slides, such as the GPU attack
example ignoring memory bandwidth, even though they also cite a specific
memory bandwidth figure on a preceding slide. They use 2688 "cores",
6 GB memory, 250 GB/s bandwidth, then imagine a KDF using 0.5 MB in 2 ms
and assume that all 2688 "cores" would compute it at 100% efficiency -
but merely filling the 0.5 MB in 2 ms (not even reading any of that data
back) imposes a limit of 1000 "cores" in full use max (or more "cores"
in less than full use, spending most of their time waiting), since it
needs 250 MB/s/core. This also ignores the high latency of off-chip
memory, and needing to run multiple instances of the KDF per "core" in
order to hide instruction latencies (even without any use of off-chip
memory), but that's sort of OK if they want to arrive at a theoretical
highest possible speed (for a simplified model of the GPU rather than
for the real thing) rather than a realistic speed. And indeed this
assumes no TMTO (which may actually help put more "cores" to use, etc).
(And I put the "cores" in quotes because they are not exactly that,
which may also matter in practice.) OK, I am nitpicking. They're
making their point fine anyway.
10. The claim of (irrelevant) "known vulnerabilities" in SHA-1 and
Salsa20/8 looks like marketing/FUD. I assume that was not intentional.
Better wording would be along the lines of: "some prospective users of
KDFs may not be qualified to determine that SHA-1 and Salsa20/8 are
perfectly OK for such use despite of known attacks, yet may be
concerned; for those users, we chose to use BLAKE2 instead". Even that
would still be weird, though, because those type of users would possibly
be unhappy about BLAKE2 not being NIST-approved. Besides, scrypt uses
SHA-256 and not SHA-1. SHA-256 is NIST-approved and currently among the
recommended algorithms. For scrypt's cryptographic security, it is
sufficient that SHA-256 is secure, whereas scrypt's use of Salsa20/8 is
"non-cryptographic" (its properties are important for scrypt's area-time
cost of attacks, but not for its crypto security per se).
11. Disclaimer: I might have made some errors in the comments above,
too. ;-)
12. The above comments apply to Presentation.pdf with SHA-256 of:
0088c41c99104cd6c0317c3e97ac36ae4e304f07a5255cb6d0da6caf49012663
and modification date of:
/CreationDate (D:20140107172630-02'00')
(I think it might be changing as I am not seeing some of what folks on
the PHC list criticized. This is OK; I just felt the need to refer to a
specific revision for that reason.)
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.
