phc-discussions - Catena conjecture correction

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

Message-ID: <CAOLP8p5HEcxJR=1U4x=vv_DHRzTpAUhkvE7rbK-ULU8gAgs01A@mail.gmail.com>
Date: Thu, 13 Mar 2014 08:05:22 -0400
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Catena conjecture correction

Now that my code seems stable-ish, I'm looking back into the math
behind pebbling proofs.  I see no error in Catena's, however, the
Catena paper also makes the following conjecture:

    T > G^(L+1)/(S^L)

Where T is the number of pebble moves required, and L is lambda.

I think there is a slight error in the paper two equations before:

    G*(G/2S)^L = G^(L+1)/(2*S^L)

It should be 2^L, not 2.

I verified that Catena-2 can be pebbled with equal spaced pebbles in
rows 1 and 2 with S == G/4 with a recomputation penalty of 8, rather
than the predicted 16.

Bill