Message-ID: <CAMtf1Hs_w5-hgdvkMYdKDWnpw-N3PTB6QesgHgi6CQmT8ruDkg@mail.gmail.com>
Date: Thu, 7 Aug 2014 16:19:46 +0800
From: Ben Harris <ben@...rr.is>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Tradeoff cryptanalysis of password hashing schemes

Just getting my head around the Catena one.

Storing [**0] takes 2^2k storage per level? (presentation says 2^(n-k))
And the [*B*] takes 2^(n-k) storage
So L*2^2k + 2^(n-k) storage all up.

Computing each [*B*] at level 0 takes 2^(n-2k) operations from each 2^k
[*B0]. total 2^(n-k) operations? (presentation says 2^2k)
Computing each [*^B*] at level 1 is more complicated because we don't
always have what we need.

At level 1, for the A = 1, B = 1, and len(C) = 2 (the example in the
presentation). For the 2^(n-k) = 2^(4-1) = 8 [*^B*] we have
[00 1 0] - h( h([00 0 0] + [1 0 00]) + [0 1 00]) = 2 hashes
[00 1 1] - h([00 1 0] + [1 1 00]) - 1 hash
[01 1 0] - h([01 0 1] + [0 1 10]) - but [01 0 1] is h([01 0 0] + [1 0 10])
and I don't have [1 0 10] it takes 2 hashes from [1 0 00]
[01 1 1] - 1 hash from previous
[10 1 0] - h([10 0 1] + [0 1 10]) -  again, I don't have [10 0 1]?
[10 1 1] - 1 hash from previous
[11 1 0] - again, we are missing something
[11 1 1] - 1 hash from previous

These missing dependencies become exponential at level 2+.

So there are three bits I'm getting a bit stuck on:
  - Storage per level
  - Operations for level 0
  - Missing dependencies at level 1

Maybe I'm just misreading the slides and needed to see the talk?


On 7 August 2014 05:10, Marcos Simplicio <mjunior@...c.usp.br> wrote:

> Hi, all.
>
> Very interesting analysis! We noticed the same attack venue described in
> slide 47 for Lyra2 some time ago, so we provided and evaluated a simple
> fix in the version provided in our website (http://lyra-kdf.net/, see
> section 5.1.2.3 of the specification). I'm not sure how the tradeoffs
> table is affected by this fix, but the costs are likely to grow (at
> least that was my impression by crossing your results with our
> preliminary analysis).
>
> BTW, the document in our website is being continuously updated as new
> tests are performed, so we expect to introduce this and possibly other
> tweaks in the corresponding phase of the PHC. We are still evaluating
> the "possible extensions" mentioned in the original submission, for
> example.
>
> BR,
>
> Marcos.
>
> On 06-Aug-14 14:31, Dmitry Khovratovich wrote:
> > Hi all,
> >
> > here is the link to the slides of the talk I have just given at
> > PasswordsCon'14. It investigates time-memory tradeoffs for PHC candidates
> > Catena, Lyra2, and Argon, and estimates the energy cost per password on
> an
> > optimal ASIC implementation with full or reduced memory.
> >
> > https://www.cryptolux.org/images/5/57/Tradeoffs.pdf
> >
> > Additional comment: It is a standard practice in the crypto community to
> > give explicit security claims for the recommended parameter sets so that
> > cryptanalysts could easily identify the primary targets. Many PHC
> > candidates do not follow this rule by not only missing these claims but
> > also concealing the recommended parameters. As a result, cryptanalysts
> like
> > me spend valuable time attacking wrong sets or spreading the attention
> over
> > multiple targets.
> >
> > Remember: third-party cryptanalysis increases the confidence in your
> > design, not decreases it (unless it is badly broken). Analysis of a
> 5%-part
> > of your submission (one of 20 possible parameter sets) is little better
> > than no analysis at all. It is also worth mentioning that to make fair
> > comparison of candidates, benchmarks and performance discussion in
> general
> > should cover recommended parameter sets only.
> >
>

Content of type "text/html" skipped

Powered by blists - more mailing lists