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

Powered by blists - more mailing lists