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: <CALW8-7+Lo-KbM2YKLsOY6nZkj=1YdYdhm2ockRzBYswS6OGF3Q@mail.gmail.com>
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