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: Thu, 13 Feb 2014 18:33:10 -0800
From: "Dennis E. Hamilton" <dennis.hamilton@....org>
To: <discussions@...sword-hashing.net>
Subject: RE: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

I think I commented on this before.  It applies in the design of PRNGs that use products modulo a word size too.  

To keep the lower-order bits of progressive multiplications from being poisoned by growing sequences of 0s, it is necessary to force both multiplication operands to be odd.  That appears to be the only simple cure.  This effectively removes a bit from the possible period/product-space but one way to deal with that is keep the seed (for PRNG) odd but shift the low order bit out of the delivered result.  (If the product is double width, you can shift in an additional bit before delivering the single-width result, or simply deliver only positive single-word values (rather than a full [unsigned] word).  

This is a hack.  I have no idea how it impacts pseudo-randomness.  I used it in one place to suppress even-valued seed choices by forcing them to be odd when initializing a common PRNG.  I am not talking about cryptographically-acceptable PRNGs.

In the case of two pseudo-random inputs to a multiplication, I think forcing them both odd is some help.  I have no idea whether "|3" is better than "|1" for this purpose, but I suggest that both operands should be assured odd by some means.

 - Dennis 

-----Original Message-----
From: Bill Cox [mailto:waywardgeek@...il.com] 
Sent: Thursday, February 13, 2014 06:44
To: discussions@...sword-hashing.net
Subject: Re: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

[ ... ]

In the version of this I tested, I make "value" (horrible name...)
64-bit, so the cast to 32-bit is not reversible, so there's no problem
there.  However, without the "| 3", I see that most of the LSBs after
1B iterations of the hash loop are 0.  The problem is that the upper
bits have no way of impacting the lower bits, so whenever value is odd
and we multiply by an even, that LSB of value never again impacts the
LSB of future values of value.  Maybe I should rename value to v?

[ ... ]

Powered by blists - more mailing lists