[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <7dbf5c363a10d8c9a01064ff4c0f4748.squirrel@webmail.larc.usp.br>
Date: Tue, 14 Jan 2014 12:49:39 -0200 (BRDT)
From: "Marcos Simplicio" <mjunior@...c.usp.br>
To: crypt-dev@...ts.openwall.com
Cc: "Leonardo Almeida" <leocalm@...il.com>,
"eandrade@...c.usp.br" <eandrade@...c.usp.br>
Subject: Re: lyra
Hi there.
I saw the discussion below and thought I could offer some pointers on
Lyra's design (please see http://eprint.iacr.org/2014/030 or the official
publication at http://link.springer.com/journal/13389 for all details).
>> 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.
Please let us know if you find any flaw in our security claims! :-)
>
> 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 reason is that we adopt an Alred-like approach, using 1-round Blake2b
instead of 10-round Blake2b. Since we are interested in diffusion rather
than cryptographic resistance to inversion or collisions, this seems to be
a good approach for KDFs. After all, the attacker has no control over the
inputs provided to the hash... We are open to other people's opinions on
the matter, though :)
>
> 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.
I'm not sure whether this solves your point or not, but the TMTO
resistance is configurable/optional: T is fully configurable; if you want
the same memory usage with a lower T, but wants to raise the processing
time, just use 2-round Blake2b (or higher).
>
> 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.
Normalization is indeed a complicating factor when comparing KDFs, and we
are working on make ours clearer. At first sight (but I haven't check all
details), we actually have something like Rl/C = Rs/r. Maybe I'm wrong by
a constant factor, but I'm pretty sure there is no T in this equation
because T has nothing to do with memory usage...
> 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.
I'm not sure I followed your reasoning correctly, but I can assure that
this O(Rs/T*C) is incorrect, since a higher T will always (1) leads to a
higher memory usage in attacks and (2) does not influence the memory usage
for legitimate users (only processing time). An attacker can either store
sponge states (which increase in number with T, until it reaches T*R) or
store nothing and simply recompute sponge states when they are required
(which places T at the exponent, leading to the Rl^{T+1} processing cost).
> 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.
>
Indeed... This comparison is missing and may be leading to the confusion
seen in items 5. and 6... We will make sure to work on that in new
versions of the manuscript...
> 8. Other TMTO-discouraging changes relative to scrypt had been proposed.
> It'd be nice to see how Lyra compares (not trivial to do).
>
Probably such comparisons will be part of PHC discussions, but since there
are so many ideas an contestants (some of them still unknown), this will
require a task-force rather than a single team :)
> 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).
Well, the problem with insecure primitives is that they are (or should?)
likely to be discontinued in future releases of crypto libraries. Hence,
depending on them is not the best policy. In the article this is much
clearer that in the presentation (I hope this removes the impression of
FUD, especially because scrypt's security claims do not depend on
Salsa20/8...)
And we never claimed that SHA-1 is used in scrypt, but in PBKDF only. ;)
>
> 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.
