phc-discussions - Re: [PHC] Gambit review

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CAOLP8p6xj==LrZegch91yfVsiE24U+h4tu+2Rh1JRMs_Rm5Abw@mail.gmail.com>
Date: Thu, 10 Apr 2014 07:51:34 -0400
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Gambit review

On Thu, Apr 10, 2014 at 4:27 AM, Krisztián Pintér <pinterkr@...il.com> wrote:
>
> Bill Cox (at Wednesday, April 9, 2014, 11:18:25 AM):
>
>> In short, the modified approximation is easy to pebble (exactly zero
>> recomputations) down to 1/8th pebbles (relative to a 4-row graph
>> size), and then my code fails completely to find any pebbling solution
>> for even 1 fewer pebbles.  I was not able to pebble any sized graph I
>> tried with 1/8th - 1 pebbles
>
>> recomputation weakness I haven't found, then it is *very* strong
>> against TMTO's below the 1/8th memory mark, very likely the strongest
>> cache-timing resistant entry in the PHC at the 1/8th mark.  All of the
>
> i'y very grateful for your efforts. these results are reassuring. this
> is a very crucial point for gambit, since i don't have a proof. i do
> have a rationale, but it is more in the "educated voodoo magic"
> category than anything else.

Honestly, I had concerns about the simple backwards skipping pattern
before this test.  It's simplicity lends itself to analysis and there
might have been some clever devastating pebbling attack against it.

However, my pebbling algorithm is well optimized to avoid
recomputations.  That's the one thing it does well.  I've seen it come
up with clever pebbling of graphs I thought were more secure.  If
recomputation free pebbling were possible below the 1/8th mark, I
think it would have figured out how.

>> Catena uses a faster hash function (Blake2b).
>
> please bear in mind that there is the (real!) possibility to use
> reduced round keccak. keccak authors have a paper on that, but i was
> unable to find it. when i find it, i will include this in the pdf as a
> footnote. without any actual knowledge, i suspect we can get a speedup
> of 2x - 6x.
>
> granted, the same thing probably can be done with catena, which as of
> now uses a probably unnecessarily strong internal hash.

I remain a fan of reduced-round algorithms.  For servers trying to
keep authentication below 10ms or so, reduced rounds might allow more
cache to be filled, increasing security.

Bill