Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 3 Sep 2013 20:00:58 +0200
From: CodesInChaos <>
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
> (

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.