Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Tue, 31 Dec 2013 15:58:48 +0100
From: Christian Forler <>
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,

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.