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] [thread-next>] [day] [month] [year] [list]

Message-ID: <1756682424.20140410102704@gmail.com>
Date: Thu, 10 Apr 2014 10:27:04 +0200
From: Krisztián Pintér <pinterkr@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Gambit review

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.

> Because Gambit XORs over memory, the reality of pebbling Gambit may be
> quite a bit harder.

i suspect, based on my earlier attempts of analysis, that lack of
xoring lowers the memory footprint by a constant factor. that is, you
can achieve the same time using c*m memory instead of m, where c is a
constant like 0.7 or something, i don't have an exact value.

> 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.