phc-discussions - Re: [PHC] 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-prev] [day] [month] [year] [list]

Message-ID: <53329BC2.2070904@uni-weimar.de>
Date: Wed, 26 Mar 2014 10:20:02 +0100
From: Christian Forler <christian.forler@...-weimar.de>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Catena conjecture correction

On 13.03.2014 13:05, Bill Cox wrote:
> 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.

You are right. Thanks a lot for pointing out this error.

We will fix it for the submission. :-)

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

First of all, your observation is fully in tune with our Lemma 2.

Here we state that T >= G^3 / 128S^2. For S=G/4 we have
T >= G/8. With S= G/16 you should be closet to 16 then 8. :-)

The predicted penalty of 2^3 is more are rule of thumb it is asymptotic
and ignores constants. More precise would be the following formulation:
"penalty of about 2^L, depending on the choice of G and S."

BTW I had no time to take a look at SkinnyCat, yet. Currently, I am
super busy with other research and teaching stuff.

Best regards,
Christian

Download attachment "signature.asc" of type "application/pgp-signature" (535 bytes)