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