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: Thu, 2 Apr 2015 09:21:35 +0200
From: Dmitry Khovratovich <khovratovich@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Compute time hardness

On Wed, Apr 1, 2015 at 11:21 PM, Solar Designer <solar@...nwall.com> wrote:
>
>> But anyway, as 32-bit multiplication is equivalent to a sum of 16 (average) addends, it can not be more than 4x slower given sufficient area (which we have).
>
> What are you averaging here?  I think we shouldn't.  I think it's 32.

16 average non-zero addends. Very likely that no more than 24. So 4 or
5x extra depth assuming no other optimizations. However, it is clear
that the least significant bits of the final sum can be computed using
only LSBs of intermediate sums, which makes the delay even smaller.

>
> So I think it's 1 AND + 5 ADD.  And we shouldn't ignore that feeding
> each input bit to 32 ANDs probably requires buffers.

We can assume that every bit has 32 copies, the area is still negligible.

>
> In that PhD thesis you referenced above, see page 136 (page 151 in PDF).
> It shows the summation network corresponds to 49% of total delay in
> their chosen multiplier.  In fact, it says: "The delay effects of the
> other pieces of a multiplier are at least as important as the summation
> network in determining the final performance."

That's for the particular (Booth-3) multiplier scheme, not for a naive
one where you only have a binary tree of additions.


-- 
Best regards,
Dmitry Khovratovich

Powered by blists - more mailing lists