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  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]
Date: Thu, 10 Apr 2014 07:51:34 -0400
From: Bill Cox <>
Subject: Re: [PHC] Gambit review

On Thu, Apr 10, 2014 at 4:27 AM, Krisztián Pintér <> 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.


Powered by blists - more mailing lists