[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAK9dnSz=4fMYiucag5d81hRtdvBB0MfZp2PF2wJxOWC6q+-CMw@mail.gmail.com>
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.
