
MessageID: <CAK9dnSz=4fMYiucag5d81hRtdvBB0MfZp2PF2wJxOWC6q+CMw@mail.gmail.com>
Date: Tue, 3 Sep 2013 20:00:58 +0200
From: CodesInChaos <codesinchaos@...il.com>
To: cryptdev@...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 memoryhard
> 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.