phc-discussions - OT: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

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

Message-ID: <00c001cf2a1e$cb36b7a0$61a426e0$@acm.org>
Date: Fri, 14 Feb 2014 23:23:13 -0800
From: "Dennis E. Hamilton" <dennis.hamilton@....org>
To: <discussions@...sword-hashing.net>
Cc: "'Bill Cox'" <waywardgeek@...il.com>
Subject: OT: [PHC] multiply-hardening (Re: NoelKDF ready for submission)

This may be completely off in the weeds, but it crossed my mind and I have to ask.

When creating multiplications of word-sized (W-bit) operands, if you produce a 2W-width product, does it work in your scenario to XOR the two product halves together in getting a new W-bit result?

 - Dennis

-----Original Message-----
From: Dennis E. Hamilton [mailto:dennis.hamilton@....org] 
Sent: Thursday, February 13, 2014 18:33
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?

[ ... ]