
Date: Tue, 31 Dec 2013 15:58:48 +0100
From: Christian Forler <christian.forler@...weimar.de>
To: cryptdev@...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 memoryhard algorithm and *not* a sequentially memoryhad
> 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 memoryhard.
It is quite easy to extend our results of our pebblegame 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 eprintversion 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/pgpsignature" (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.