lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Wed, 22 Jan 2014 07:43:53 0500 From: Bill Cox <waywardgeek@...il.com> To: discussions@...swordhashing.net Subject: Re: [PHC] Modified pseudorandom distribution in NoelKDF On Tue, Jan 21, 2014 at 11:36 AM, Bill Cox <waywardgeek@...il.com> wrote: > I've tried many combinations, including random placement, weighted > random (more pebbles based on incoming edge density), weighted even > spacing, covering nodes pointed to by edges below a certain length, > and covering nodes with multiple edges pointing at them. I've also > tried combinations of evenly spaced with these other schemes. Nothing > seems to improve over evenly spaced so far. I tuned a pebbling combination consisting of:  evenly distributed pebbles  pebbles on nodes with more incoming edges  pebbles on nodes pointed to by short edges I also lowered memory size to 1,000,000 locations, which may still be on the high side. The penalty increases more than linearly, so larger is better for the defender. I found the following is close to an optimal combination of pebbles that add up to 25% against my randomcubed graph:  1 pebble every 12 locations  pebble every node pointed to by >= 3 edges  pebble every node pointed to by an edge <= 680 length This reduced the 25% coverage attack to 24.5X penalty for a 1% cheat killer pass. I did the same for the sliding window. I increased the minimum edge length to pebble a node to 22,500 to keep it at 25.0% pebble coverage, and the penalty dropped to 0.88X for my 1% pass. A 100% pass would have a penalty of 88X. Also, a 20% pass (pebble every 16 instead of 12, and edge length <= 10,000) gets 10X penalty for 1%, or 1000X penalty for 100% coverage. It still looks pretty good to me, though the cubed distribution seems stronger in defense. I'm thinking about what improvements can be made to an attacker's optimal pebble placement. He can put more pebbles early in memory, cover pebbles with more incoming nodes, block short edges by pebbling their source or destinations, and evenly or randomly distribute some pebbles. Maybe he could take into account some aspects of 2 or more pebbles in sequence, like incoming edges, and edge lengths, but I'm running out of features to consider in an attack. These graphs are pretty uniform everywhere, they're too fat to attack with full cuts, and partial cuts of short edges isn't enough. So, I think I've proven computationally that an attacker with a pebble placement function that looks like this fails: P(position % N == 0, degree, inlengths, outlengths, rand()) What I mean is the attacker only takes into account the position information for uniform distribution purposes, and he can choose N. He can take the incoming degree into account, as well as incoming and outgoing edge lengths. He can also do something random. This is a pretty large space of variables, but I've optimized the OR of these combinations manually, and found what appear to be global minimums. I am convinced no pebble function of this form can be written that is more effective against the randcubed distribution than a 24X penalty for 25% pebble coverage, when testing only a random 1% of memory (or 2,400X for testing it all). What other sorts of inputs to the pebble placement function could help an attacker? Bill
Powered by blists  more mailing lists