phc-discussions - Re: [PHC] Compute time hardness

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

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