From: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
To: George Spelvin <linux@sciencehorizons.net>,
ak@linux.intel.com, davem@davemloft.net, David.Laight@aculab.com,
ebiggers3@gmail.com, hannes@stressinduktion.org, Jason@zx2c4.com,
kernel-hardening@lists.openwall.com,
linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org,
luto@amacapital.net, netdev@vger.kernel.org, tom@herbertland.com,
torvalds@linux-foundation.org, tytso@mit.edu,
vegard.nossum@gmail.com
Cc: djb@cr.yp.to
Subject: Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Date: Fri, 16 Dec 2016 08:08:57 +0000 [thread overview]
Message-ID: <CAGiyFdd6_LVzUUfFcaqMyub1c2WPvWUzAQDCH+Aza-_t6mvmXg@mail.gmail.com> (raw)
In-Reply-To: <20161216034618.28276.qmail@ns.sciencehorizons.net>
[-- Attachment #1: Type: text/plain, Size: 4380 bytes --]
Here's a tentative HalfSipHash:
https://github.com/veorq/SipHash/blob/halfsiphash/halfsiphash.c
Haven't computed the cycle count nor measured its speed.
On Fri, Dec 16, 2016 at 4:46 AM George Spelvin <linux@sciencehorizons.net>
wrote:
> Jean-Philippe Aumasson wrote:
> > If a halved version of SipHash can bring significant performance boost
> > (with 32b words instead of 64b words) with an acceptable security level
> > (64-bit enough?) then we may design such a version.
>
> It would be fairly significant, a 2x speed benefit on a lot of 32-bit
> machines.
>
> First is the fact that a 64-bit SipHash round on a generic 32-bit machine
> requires not twice as many instructions, but more than three.
>
> Consider the core SipHash quarter-round operation:
> a += b;
> b = rotate_left(b, k)
> b ^= a
>
> The add and xor are equivalent between 32- and 64-bit rounds; twice the
> instructions do twice the work. (There's a dependency via the carry
> bit between the two halves of the add, but it ends up not being on the
> critical path even in a superscalar implementation.)
>
> The problem is the rotates. Although some particularly nice code is
> possible on 32-bit ARM due to its support for shift-and-xor operations,
> on a generic 32-bit CPU the rotate grows to 6 instructions with a 2-cycle
> dependency chain (more in practice because barrel shifters are large and
> even quad-issue CPUs can't do 4 shifts per cycle):
>
> temp_lo = b_lo >> (32-k)
> temp_hi = b_hi >> (32-k)
> b_lo <<= k
> b_hi <<= k
> b_lo ^= temp_hi
> b_hi ^= temp_lo
>
> The resultant instruction counts and (assuming wide issue)
> latencies are:
>
> 64-bit SipHash "Half" SipHash
> Inst. Latency Inst. Latency
> 10 3 3 2 Quarter round
> 40 6 12 4 Full round
> 80 12 24 8 Two rounds
> 82 13 26 9 Mix in one word
> 82 13 52 18 Mix in 64 bits
> 166 26 61 18 Four round finalization + final XOR
> 248 39 113 36 Hash 64 bits
> 330 52 165 54 Hash 128 bits
> 412 65 217 72 Hash 192 bits
>
> While the ideal latencies are actually better for the 64-bit algorithm,
> that requires an unrealistic 6+-wide superscalar implementation that's
> more than twice as wide as the 64-bit code requires (which is already
> optimized for quad-issue). For a 1- or 2-wide processor, the instruction
> counts dominate, and not only does the 64-bit algorithm take 60% more
> time to mix in the same number of bytes, but the finalization rounds
> bring the ratio to 2:1 for small inputs.
>
> (And I haven't included the possible savings if the input size is an odd
> number of 32-bit words, such as networking applications which include
> the source/dest port numbers.)
>
>
> Notes on particular processors:
> - x86 can do a 64-bit rotate in 3 instructions and 2 cycles using
> the SHLD/SHRD instructions instead:
> movl %b_hi, %temp
> shldl $k, %b_lo, %b_hi
> shldl $k, %temp, %b_lo
> ... but as I mentioned the problem is registers. SipHash needs 8 32-bit
> words plus at least one temporary, and 32-bit x86 has only 7 available.
> (And compilers can rarely manage to keep more than 6 of them busy.)
> - 64-bit SipHash is particularly efficient on 32-bit ARM due to its
> support for shift-and-op instructions. The 64-bit shift and following
> xor can be done in 4 instructions. So the only benefit is from the
> reduced finalization.
> - Double-width adds cost a little more on CPUs like MIPS and RISC-V without
> condition codes.
> - Certain particularly crappy uClinux processors with slow shifts
> (68000, anyone?) really suffer from extra shifts.
>
> One *weakly* requested feature: It might simplify some programming
> interfaces if we could use the same key for multiple hash tables with a
> 1-word "tweak" (e.g. pointer to the hash table, so it could be assumed
> non-zero if that helped) to make distinct functions. That would let us
> more safely use a global key for multiple small hash tables without the
> need to add code to generate and store key material for each place that
> an unkeyed hash is replaced.
>
[-- Attachment #2: Type: text/html, Size: 6883 bytes --]
next prev parent reply other threads:[~2016-12-16 8:08 UTC|newest]
Thread overview: 92+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-12-15 20:29 [PATCH v5 0/4] The SipHash Patchset Jason A. Donenfeld
2016-12-15 20:30 ` [PATCH v5 1/4] siphash: add cryptographically secure PRF Jason A. Donenfeld
2016-12-15 22:42 ` George Spelvin
2016-12-15 23:00 ` Jean-Philippe Aumasson
2016-12-15 23:28 ` George Spelvin
2016-12-16 17:06 ` David Laight
2016-12-16 17:09 ` Jason A. Donenfeld
2016-12-16 3:46 ` George Spelvin
2016-12-16 8:08 ` Jean-Philippe Aumasson [this message]
2016-12-16 12:39 ` Jason A. Donenfeld
2016-12-16 13:22 ` Jean-Philippe Aumasson
2016-12-16 15:51 ` Jason A. Donenfeld
2016-12-16 17:36 ` George Spelvin
2016-12-16 18:00 ` Jason A. Donenfeld
2016-12-16 20:17 ` George Spelvin
2016-12-16 20:43 ` Theodore Ts'o
2016-12-16 22:13 ` George Spelvin
2016-12-16 22:15 ` Andy Lutomirski
2016-12-16 22:18 ` Jason A. Donenfeld
2016-12-16 23:44 ` George Spelvin
2016-12-17 1:39 ` Jason A. Donenfeld
2016-12-17 2:15 ` George Spelvin
2016-12-17 15:41 ` Theodore Ts'o
2016-12-17 16:14 ` Jeffrey Walton
2016-12-19 17:21 ` [kernel-hardening] " Jason A. Donenfeld
2016-12-17 12:42 ` George Spelvin
2016-12-16 20:39 ` Jason A. Donenfeld
2016-12-16 19:47 ` Tom Herbert
2016-12-16 20:41 ` George Spelvin
2016-12-16 20:57 ` Tom Herbert
2016-12-16 20:44 ` Daniel Micay
2016-12-16 21:09 ` [kernel-hardening] " Jason A. Donenfeld
2016-12-17 15:21 ` George Spelvin
2016-12-19 14:14 ` David Laight
2016-12-19 18:10 ` George Spelvin
2016-12-19 20:18 ` Jean-Philippe Aumasson
2016-12-16 2:14 ` kbuild test robot
2016-12-17 14:55 ` Jeffrey Walton
2016-12-19 17:08 ` Jason A. Donenfeld
2016-12-19 17:19 ` Jean-Philippe Aumasson
2016-12-15 20:30 ` [PATCH v5 2/4] siphash: add Nu{32,64} helpers Jason A. Donenfeld
2016-12-16 10:39 ` David Laight
2016-12-16 15:44 ` George Spelvin
2016-12-15 20:30 ` [PATCH v5 3/4] secure_seq: use SipHash in place of MD5 Jason A. Donenfeld
2016-12-16 9:59 ` David Laight
2016-12-16 15:57 ` Jason A. Donenfeld
2016-12-15 20:30 ` [PATCH v5 4/4] random: " Jason A. Donenfeld
2016-12-16 3:03 ` [PATCH v6 0/5] The SipHash Patchset Jason A. Donenfeld
2016-12-16 3:03 ` [PATCH v6 1/5] siphash: add cryptographically secure PRF Jason A. Donenfeld
2016-12-16 3:03 ` [PATCH v6 2/5] secure_seq: use SipHash in place of MD5 Jason A. Donenfeld
2016-12-16 3:03 ` [PATCH v6 3/5] random: " Jason A. Donenfeld
2016-12-16 21:31 ` Andy Lutomirski
2016-12-16 3:03 ` [PATCH v6 4/5] md5: remove from lib and only live in crypto Jason A. Donenfeld
2016-12-16 3:03 ` [PATCH v6 5/5] syncookies: use SipHash in place of SHA1 Jason A. Donenfeld
2016-12-21 23:02 ` [PATCH v7 0/6] The SipHash Patchset Jason A. Donenfeld
2016-12-21 23:02 ` [PATCH v7 1/6] siphash: add cryptographically secure PRF Jason A. Donenfeld
2016-12-22 1:40 ` Stephen Hemminger
2016-12-21 23:02 ` [PATCH v7 2/6] secure_seq: use SipHash in place of MD5 Jason A. Donenfeld
2016-12-21 23:02 ` [PATCH v7 3/6] random: " Jason A. Donenfeld
2016-12-21 23:13 ` Jason A. Donenfeld
2016-12-21 23:42 ` Andy Lutomirski
2016-12-22 2:07 ` Hannes Frederic Sowa
2016-12-22 2:09 ` Andy Lutomirski
2016-12-22 2:49 ` Jason A. Donenfeld
2016-12-22 3:12 ` Jason A. Donenfeld
2016-12-22 5:41 ` Theodore Ts'o
2016-12-22 6:03 ` [kernel-hardening] " Jason A. Donenfeld
2016-12-22 15:58 ` Theodore Ts'o
2016-12-22 16:16 ` Jason A. Donenfeld
2016-12-22 16:30 ` [kernel-hardening] " Theodore Ts'o
2016-12-22 16:36 ` Jason A. Donenfeld
2016-12-22 12:47 ` Hannes Frederic Sowa
2016-12-22 13:10 ` [kernel-hardening] " Jason A. Donenfeld
2016-12-22 15:05 ` Hannes Frederic Sowa
2016-12-22 15:12 ` Jason A. Donenfeld
2016-12-22 15:29 ` Jason A. Donenfeld
2016-12-22 15:33 ` Hannes Frederic Sowa
2016-12-22 15:41 ` [kernel-hardening] " Jason A. Donenfeld
2016-12-22 15:51 ` Hannes Frederic Sowa
2016-12-22 15:53 ` [kernel-hardening] " Jason A. Donenfeld
2016-12-22 15:54 ` Theodore Ts'o
2016-12-22 18:08 ` [kernel-hardening] " Hannes Frederic Sowa
2016-12-22 18:13 ` Jason A. Donenfeld
2016-12-22 19:50 ` [kernel-hardening] " Theodore Ts'o
2016-12-22 2:31 ` Jason A. Donenfeld
2016-12-21 23:02 ` [PATCH v7 4/6] md5: remove from lib and only live in crypto Jason A. Donenfeld
2016-12-21 23:02 ` [PATCH v7 5/6] syncookies: use SipHash in place of SHA1 Jason A. Donenfeld
2016-12-21 23:02 ` [PATCH v7 6/6] siphash: implement HalfSipHash1-3 for hash tables Jason A. Donenfeld
2016-12-22 0:46 ` Andi Kleen
2016-12-16 20:43 [PATCH v5 1/4] siphash: add cryptographically secure PRF Jason A. Donenfeld
2016-12-16 20:49 Jason A. Donenfeld
2016-12-16 21:25 ` George Spelvin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAGiyFdd6_LVzUUfFcaqMyub1c2WPvWUzAQDCH+Aza-_t6mvmXg@mail.gmail.com \
--to=jeanphilippe.aumasson@gmail.com \
--cc=David.Laight@aculab.com \
--cc=Jason@zx2c4.com \
--cc=ak@linux.intel.com \
--cc=davem@davemloft.net \
--cc=djb@cr.yp.to \
--cc=ebiggers3@gmail.com \
--cc=hannes@stressinduktion.org \
--cc=kernel-hardening@lists.openwall.com \
--cc=linux-crypto@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@sciencehorizons.net \
--cc=luto@amacapital.net \
--cc=netdev@vger.kernel.org \
--cc=tom@herbertland.com \
--cc=torvalds@linux-foundation.org \
--cc=tytso@mit.edu \
--cc=vegard.nossum@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).