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: 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