Date: Tue, 31 Dec 2013 15:58:48 +0100 From: Christian Forler <christian.forler@...-weimar.de> To: crypt-dev@...ts.openwall.com Subject: Re: Password Scrambling On 29.12.2013 21:38, Stephen Touset wrote: >>>> Doesn't the standard "store every 1/sqrt(n)th value and >>>> recompute the rest using parallel cores" attack using a >>>> parallel computer break this? >> >>> What's the current understanding on this? I think the attack >>> does work against Catena, although I only skimmed over the paper. >>> Does this mean some of the proofs in the paper are flawed? >> >> Yes, the attack is working, but it does not invalidate any of our >> security proofs. > > I believe this is because your security proofs only prove that Catena > is a memory-hard algorithm and *not* a sequentially memory-had > function. Your proof (at least as of the time I read it) involved a > pebble game, but not with a ruleset extended to reflect multiple > cores. > > Correct? Yes, Catena is *NOT* sequentially memory-hard. It is quite easy to extend our results of our pebble-game proof to reflect multiple cores. Let c the number of cores, then we can compute the multiple core TMTO using c cores be the following equation: (1/c S^a) * (c T) = N^b. For example, Considering the current eprint-version of Catena, we have a=1 b=2, and therefore (1/c * S) (cT) = N^2. For an adversary with c=N^1/2 cores and S=N^1/2 pebbles we have T = N^1.5. This TMTO is quite good for the adversary. Therefore, we redesigned Catena. The PHC submission will have a much worse TMTO. Best regards, Christian Download attachment "signature.asc" of type "application/pgp-signature" (552 bytes)
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.