Date: Tue, 3 Sep 2013 20:00:58 +0200 From: CodesInChaos <codesinchaos@...il.com> To: crypt-dev@...ts.openwall.com Subject: Re: Password Scrambling On 9/2/2013 9:58 AM, Christian Forler wrote: > Nevertheless, we came up with Catena, a new memory-hard > password scrambler based on the bit reversal function. A detailed > description of our scheme is available on eprint > (http://eprint.iacr.org/2013/525). 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? In phase 1 you output values in the order 1 to n. In phase 2 you iterate the values in some other, but fixed order. Now an attacker uses two different machines for those two phases: Phase 1: run phase 1 normally, but only store every 1/sqrt(n) th value in the natural order of phase 2 for storage. This step runs in time n and needs memory sqrt(n) for a total cost of n^1.5. Phase 2: iterate in the standard phase 2 order. You can recompute elements you didn't store in time sqrt(n), but since you can use sqrt(n) parallel cores and memory access is predictable, those elements are available instantly when the 1 sequential iterator needs them. Runs in time n and needs sqrt(n) space. Total cost is n^1.5. But that contradicts your security claim (and proof) that space*time is n^2 on a parallel random access machine i.e. that the function is sequentially memory? Why doesn't this attack work? Content of type "text/html" skipped
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.