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.