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: Sun, 26 Jan 2014 00:43:33 0500 From: Bill Cox <waywardgeek@...il.com> To: discussions@...swordhashing.net Subject: Re: [PHC] Initial (nonproofread) NeolKDF paper On Sat, Jan 25, 2014 at 11:53 PM, Dennis E. Hamilton <dennis.hamilton@....org> wrote: > Kibbitzing for a moment: > > If you don't know what the low order bit is, xor of an odd value doesn't guarantee that the result is odd. > > The multiplication is kind of a congruential PRNG step modulo whatever the multiplier word size is. My experience is that you need both terms of the multiplication to be odd to work well to avoid the poisoning effects of lots of trailing zeros in either multiplication operand. (How that fits with regard to reversibility is not something I've thought about.) > > Now the problem is that the product is always odd. I posit this can be cured by shifting the derived product right one bit. This means you always have a 0 leading bit unless there is enough of the full product to shift a bit in from the higherorder "word" of the full product result. > > I have no idea whether this satisfies the constraints of the situation and whether it mucks with the "randomness." It is just why you may want to force at least one, maybe both, numbers to odd going into the multiplication. > >  Dennis In this case, I'm concerned about not leaking away entropy too fast. Even SHA512 leaks entropy, just too little to measure, since multiple inputs hash to the same output. I'm using the inner loop hash function: value = value*(mem[prevAddr++]  3) + mem[randAddr++] The idea hear is that I'd prefer to compute a permutation of value every iteration, similar to what AES does. With permutations, no entropy is lost. If mem[prevAddr] and mem[randAddr] were replaced with a PRNG stream derived only from the password and salt, then this would be a true permutation, and it would be entirely reversible. Being reversible is undesirable, as it gives attackers trying to perform a timememory tradeoff more options for recalculating missing data. For this to work well and not lose significant entropy, mem[prevAddr] needs to be highly scrambled relative to value. With a default page size of 4096, I think it will be plenty scrambled, since the last time mem[prevAddr] impacted value was 4096 iterations prior. Page sizes of 256 passed the dieharder tests, indicated even 256 is far enough away. Originally, I had swapped prevAddr and randAddr, because randAddr is on average many times further back in the hashing history, with even more mixing relative to value. Alexander pointed out that by ever reading the LSB of mem[randAddr], because I was ORing it with 1, allows an attacker to use a 31 bit memory rather than 32 bits. That's why I had to put them in this order. In any case, the same rule applies to mem[randAddr]. If it is correlated with value, we lose entropy fast. A final reason for the OR, is that I am uncomfortable without it. It's the only nonlinear operation in the hash function, and the only one that makes me confident that there is no way to mathematically compute mem[i] without first computing mem[0 .. i1]. I can't say I've seen any interesting closed form solutions to recurrence relations involving all three operators. Thanks for the discussion! I think I'll add some of this stuff to the paper. I guess I just put that hash function in there, and left it as "Here it is!" Duh... Bill
Powered by blists  more mailing lists