[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <52C2DBA8.2030008@uni-weimar.de>
Date: Tue, 31 Dec 2013 15:58:48 +0100
From: Christian Forler <christian.forler@...-weimar.de>
To: crypt-dev@...ts.openwall.com
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,
Christian
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.
