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] [day] [month] [year] [list]
Date: Wed, 26 Mar 2014 10:20:02 +0100
From: Christian Forler <>
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,

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

Powered by blists - more mailing lists