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, 9 Feb 2014 09:04:53 0500 From: Bill Cox <waywardgeek@...il.com> To: discussions@...swordhashing.net Subject: Fwd: [PHC] multiplyhardening (Re: NoelKDF ready for submission) Gary thought a reply to the list might make sense... I don't know how many readers we have that would benefit, but in any case, here's my response to Gary's request for an explanation of the multiply by a constant stuff I wrote:  Forwarded message  From: Bill Cox <waywardgeek@...il.com> Date: Sun, Feb 9, 2014 at 8:59 AM Subject: Re: [PHC] multiplyhardening (Re: NoelKDF ready for submission) To: "Gary W. Hvizdak" <gary.hvizdak@....rr.com> That last part is about the complexity of multiplication with a constant as one operand vs two variables. We build multipliers in silicon much the way you do it by hand, with rows of partial products that we then add together to get a result. The partial products are either 0 or the upper value shifted left some distance, since we only multiply by 0 or 1. Adding the partial products together is easily done with "carry save adders", which are just adders with and AND gate on one input, so that we either add 0 or the value shifted by some distance. This would normally take 32 32bit carrysave adders to do a 32x32 multiply. Some genius figured out that you can build a subtractor just as easily as an adder, and that with an XOR gate on the input, you can build an adder/subtractor that can do either. With clever encoding of one operand, called "Booth encoding", you can do a 32x32 multiply with only 16 adder/subtractors, cutting the area almost in half while making it faster. With one operand as a constant, we can precompute the optimal way to have the nonconstant operand shifted and added/subtracted. For example, any multiply by a constant with only 2 bits set to 1 can be implemented with a single adder. For example 12*a = (8 + 4)*a = 8*a + 4*a = (a << 3) + (a << 2). If I want to compute 15*a, I can do it as 15*a = (16  1)*a = 16*a  a = (a << 4)  a. Shifting in hardware is free. You just move the wires. So, multiplication by 15 takes one subtractor. You don't have to do poweroftwo decomposition of a constant. We do that because shifting is free. For example, to compute 13*a we can first compute 3*a = (a << 1) + a. We then can compute (163)*a = (a << 4)  3*a. This requires an adder and a subtractor. In general, if we can find a way to add and subtract and shift numbers starting with 1 that add up to a constant, we only need the number of adder/subtractors used to build a multiplier by that constant. That's why it's an interesting problem to find the minimum number required for any given constant. I wrote a quick inefficient hack to do it. Samual pointed out a standard program used to do it that runs much faster. In any case, multiplication by a constant is too fast in custom hardware compared to multiplying two variables, so I'm not switching to the hash function Alexander suggested. Bill
Powered by blists  more mailing lists