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
| ||
|
Message-ID: <20150401170726.GA14667@openwall.com> Date: Wed, 1 Apr 2015 20:07:26 +0300 From: Solar Designer <solar@...nwall.com> To: discussions@...sword-hashing.net Subject: Re: [PHC] Compute time hardness On Wed, Apr 01, 2015 at 06:36:32PM +0300, Solar Designer wrote: > On Wed, Apr 01, 2015 at 08:20:29AM -0700, Bill Cox wrote: > > Alexander's technique of counting sequential operations, and giving > > multiply more weight seems reasonable to me, though he's once again > > under-cutting himself by only claiming a multiply is worth 3 additions. > > Use 8 and you'll be closer to reality, IMO. > > I agree. All we know is it's somewhere between 3 and 32. OK, it's obviously not 32. If we count only gate delays, then it's easy to see that we need one set of 1024 parallel 1-bit ANDs for the partial products, and then 5 sequential groups of (equivalents of) 32-bit ADDs. So that's a total of 1 AND + 5 ADD. But there might be wire delays greater than those in a circuit with a more regular structure. In fact, I found a patent (expiring soon) that appears to focus on optimizing the structure and it gives "a propagation delay of only 7.5 full adders" for a 32x32 multiplier (and 10.5 for 58x58, 11.5 for 61x61). It isn't entirely clear (at least without actually reading and understanding the whole thing, which I did not) what exactly they mean by a "full adder" here (same bit width as the multiplier's operands? something else?) BTW, when computing the 1024 partial product bits, we'd be putting quite some load on the multiplier's inputs (have to input each to 32 gates at once). Perhaps this requires buffers, and perhaps they add delays too. So Bill's guess of 8 sounds about right. Alexander
Powered by blists - more mailing lists