lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Wed, 13 Aug 2014 16:37:59 +0800
From: Ben Harris <ben@...rr.is>
To: discussions@...swordhashing.net
Subject: Re: [PHC] Tradeoff cryptanalysis of password hashing schemes
My [relatively limited] understanding of Catena's inability to show
q^lambda is related to the bit reversal. Bit reversal is chosen for (and
the proof relies on) nodes adjacent in layer N being far apart in layer
N1. Your approach exploits the fact that nodes adjacent in layer N are
adjacent in layer N2. This means the "exponential explosion" expected in
Catena only appears for one layer resulting in q^1.
Perhaps a circular rotation would be a better fit, while still providing
the inplace implementation of bit reversal? For lambda=4 and N=2^20 a
rotation by 4 bits would spread things out. (I haven't actually looked at
the graph this would produce yet  I need a cool graph visualising tool).
Hi Ben,
indeed k has to be large enough to be efficient.
Your calculations are correct. In fact, you will also have to add 2^3 hash
calls that actually compute the vertices in the interval to the 3.5x2^6 in
precomputations (I will add this to the slides).
However, the penalty is computed for the entire Catena. You spend
2^3 hashes to get 2^3 vertices at level 0  penalty 1
(0.5x2^6+2^3) to get 2^3 vertices at level 1  penalty 5
(1.5x2^6+2^3) at level 2  penalty 13
(2.5x2^6+2^3) at level 3  penalty 21
(3.5x2^6+2^3) at level 4  penalty 29
Average penalty is (1+5+13+21+29)/5 = 13.8
To get 13.1 I used a more efficient method for levels 1 and 2, which does
not do precomputations. Instead, I moved forward stored points at level X1
after they had been used at level X. This gives the penalty 3.375 for level
1 and 11.25 for level 2, so in total you have around 13.1 .
Dmitry
On Thu, Aug 7, 2014 at 5:15 PM, Ben Harris <ben@...rr.is> wrote:
> I'll have to test your pebbling scheme for Catena  but an initial comment
> on the time comparisons.
>
> Catena with lambda=4 and n=20 takes 2^20 storage and 5x2^20 hashes.
> Presentation takes Lx2^(nk) storage. So at k=1 you are using more memory,
> and k=2 you are using the same. Need k=3 to use 1/2 the memory.
> At k=3 you need 3.5x2^6 to get 2^3 vertices, so 3.5*2^6*2^(203) to get
> all the vertices for the final row. So 3.5x2^23 to get the last row.
>
> Catena will take 2^20 to get the final row, so that is a slowdown of
> 3.5x2^3 = 28x. You only have 13.1x slowdown?
>
>
> On 7 August 2014 17:15, Ben Harris <ben@...rr.is> wrote:
>
>> Thanks Dimitry,
>>
>> Page 26 just needs to be updated then  it says "Consider vertices
>> [AB0]... where each letter has k bits" suggesting that A and B are k bits
>> each  not that C is k bits.
>>
>>
>> On 7 August 2014 17:10, Dmitry Khovratovich <khovratovich@...il.com>
>> wrote:
>>
>>> Hi Ben,
>>>
>>> the following points are important:
>>>  A, C, *, 0 are all kbit values. k<n/3, and for the attack being
>>> efficient k>2.
>>>  [**0] takes 2^(nk) storage per level as you store everything that
>>> ends with k zeros.
>>>
>>> The example in presentation has A = C = 1, and B=2. Such small
>>> values are for the ease of understanding, but not for the efficiency. I
>>> attach the picture in the higher resolution. The red indices are those
>>> precomputed for the next level.
>>>
>>> Best regards,
>>> Dmitry
>>>
>>>
>>> On Thu, Aug 7, 2014 at 1:19 AM, Ben Harris <ben@...rr.is> wrote:
>>>
>>>> Just getting my head around the Catena one.
>>>>
>>>> Storing [**0] takes 2^2k storage per level? (presentation says 2^(nk))
>>>> And the [*B*] takes 2^(nk) storage
>>>> So L*2^2k + 2^(nk) storage all up.
>>>>
>>>> Computing each [*B*] at level 0 takes 2^(n2k) operations from each 2^k
>>>> [*B0]. total 2^(nk) 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^(nk) = 2^(41) = 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://lyrakdf.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 06Aug14 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 timememory 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: thirdparty 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.
>>>>> >
>>>>>
>>>>
>>>>
>>>
>>>
>>> 
>>> Best regards,
>>> Dmitry Khovratovich
>>>
>>
>>
>

Best regards,
Dmitry Khovratovich
Content of type "text/html" skipped
Powered by blists  more mailing lists