
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