phc-discussions - Re: [PHC] An argument for Catena-2

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]

Date: Mon, 27 Jan 2014 11:51:16 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] An argument for Catena-2

On Mon, Jan 27, 2014 at 8:34 AM, Dmitry Khovratovich
<khovratovich@...il.com> wrote:
> Hi Bill,
>
> it seems that your 10X estimate is a bit pessimistic. If you have only half
> of memory available, you can split it in half and store every 4th point
> (v_i) from the first two rows in memory.

Very cool analysis!  You are correct.  My 10X estimate was high.

I've tested your pebbling strategy and verified it, with 1 caveat: you
need an additional 3 free pebbles to be able to pebble the graph.  For
your example, we place 4 fixed pebbles, but we only have 4.  you need
3 more for the pebbling to be possible.

When I use G/2 + 3 pebbles, I can verify the pebbling time for larger
sizes.  For G == 2048, I pebble the graph using 1027 pebbles with a
2.6X penalty.

When I add the sub-Catena-7 graph in the first row, using your
strategy, I can pebble the graph with 1034 pebbles (I need 7 more for
the first row) with a penalty of 12.2X.  Using a Catena-3 sub-graph in
the first row, I get 5.1X.

Switching up to Catena-3, instead of a pebble every 4, we have to drop
to a pebble every 6 in the first three rows, and use a total of G/2 +
4 pebbles.  For G == 8192, using 1028 pebbles, I get a total compute
effort that is 9.4X higher than when I have 2048 pebbles.

Adding a Catena-3 sub-graph in the first node takes it up to 49X.  For
a Catena-8 graph, on a smaller (so it would run faster) graph of G ==
1024, and 143 pebbles, I needed 728X more pebble placements.

It seems to me that the sub-Catena graph may be needed after all.

Bill