phc-discussions - Re: [PHC] Modified pseudo-random distribution in NoelKDF

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

Message-ID: <CAOLP8p7gMkDrvDDwW3MGbdu_hN+xE-vAQ296mL=dSAsN0YbdKg@mail.gmail.com>
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