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, 20 Jan 2014 15:56:13 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Modified pseudo-random distribution in NoelKDF

On Mon, Jan 20, 2014 at 9:01 AM, Solar Designer <solar@...nwall.com> wrote:
> Do you have specific numbers for the original approach above, and what
> would be high enough (in your opinion)?

I would like to hurt a guy using only 1/4 of the memory enough that
his attack is not practical.  I also want to not spend much time in
the second loop forcing an attacker to show memory locations, so I'd
like to read only 1% of the blocks.  A guy using only 1/8th should be
deep into impractical TMTO territory.

For my original scheme, the recalculation penalty for 1/4th of
10,000,000 memory locations covered with evenly spaced pebbles was
only 3.8X.  That was too low.  For 1/8th, it was a decent 282X.

> My sliding window approach has a similar effect, but I think yours is
> more aggressive.  Have you tried estimating the TMTO resistance of my
> sliding window approach?  That would be very helpful.

The average recalculation for 10,000,000 nodes covered by evenly
spaced pebbles covering 1/8th of memory is 2.4% of the graph.  That's
a 2421X recalculation, which is very good.  Remember, I only make him
recalculate 1% of the blocks, so the test cost me only 1% of my
runtime.  In your case, where you read as much memory as you write, an
attacker might see a 242,100X penalty.

For pebbles every 4 locations, it drops to 24.7X recalculation
penalty, which isn't bad, especially if I give you the 100X for
reading as much as you wrote, which would be 2,470X.  I got to 130X
using the cubed distribution, so maybe 6 times more recomputations for
using the cubed distribution, but I read 100X less, so you're attacker
will actually to see 19X higher penalty than me.

Bill

Powered by blists - more mailing lists