From: "George Spelvin" <linux@sciencehorizons.net>
To: 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,
linux@sciencehorizons.net, 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, jeanphilippe.aumasson@gmail.com
Subject: Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Date: 15 Dec 2016 17:42:24 -0500 [thread overview]
Message-ID: <20161215224224.21447.qmail@ns.sciencehorizons.net> (raw)
In-Reply-To: <20161215203003.31989-2-Jason@zx2c4.com>
> While SipHash is extremely fast for a cryptographically secure function,
> it is likely a tiny bit slower than the insecure jhash, and so replacements
> will be evaluated on a case-by-case basis based on whether or not the
> difference in speed is negligible and whether or not the current jhash usage
> poses a real security risk.
To quantify that, jhash is 27 instructions per 12 bytes of input, with a
dependency path length of 13 instructions. (24/12 in __jash_mix, plus
3/1 for adding the input to the state.) The final add + __jhash_final
is 24 instructions with a path length of 15, which is close enough for
this handwaving. Call it 18n instructions and 8n cycles for 8n bytes.
SipHash (on a 64-bit machine) is 14 instructions with a dependency path
length of 4 *per round*. Two rounds per 8 bytes, plus plus two adds
and one cycle per input word, plus four rounds to finish makes 30n+46
instructions and 9n+16 cycles for 8n bytes.
So *if* you have a 64-bit 4-way superscalar machine, it's not that much
slower once it gets going, but the four-round finalization is quite
noticeable for short inputs.
For typical kernel input lengths "within a factor of 2" is
probably more accurate than "a tiny bit".
You lose a factor of 2 if you machine is 2-way or non-superscalar,
and a second factor of 2 if it's a 32-bit machine.
I mention this because there are a lot of home routers and other netwoek
appliances running Linux on 32-bit ARM and MIPS processors. For those,
it's a factor of *eight*, which is a lot more than "a tiny bit".
The real killer is if you don't have enough registers; SipHash performs
horribly on i386 because it uses more state than i386 has registers.
(If i386 performance is desired, you might ask Jean-Philippe for some
rotate constants for a 32-bit variant with 64 bits of key. Note that
SipHash's security proof requires that key length + input length is
strictly less than the state size, so for a 4x32-bit variant, while
you could stretch the key length a little, you'd have a hard limit at
95 bits.)
A second point, the final XOR in SipHash is either a (very minor) design
mistake, or an opportunity for optimization, depending on how you look
at it. Look at the end of the function:
>+ SIPROUND;
>+ SIPROUND;
>+ return (v0 ^ v1) ^ (v2 ^ v3);
Expanding that out, you get:
+ v0 += v1; v1 = rol64(v1, 13); v1 ^= v0; v0 = rol64(v0, 32);
+ v2 += v3; v3 = rol64(v3, 16); v3 ^= v2;
+ v0 += v3; v3 = rol64(v3, 21); v3 ^= v0;
+ v2 += v1; v1 = rol64(v1, 17); v1 ^= v2; v2 = rol64(v2, 32);
+ return v0 ^ v1 ^ v2 ^ v3;
Since the final XOR includes both v0 and v3, it's undoing the "v3 ^= v0"
two lines earlier, so the value of v0 doesn't matter after its XOR into
v1 on line one.
The final SIPROUND and return can then be optimized to
+ v0 += v1; v1 = rol64(v1, 13); v1 ^= v0;
+ v2 += v3; v3 = rol64(v3, 16); v3 ^= v2;
+ v3 = rol64(v3, 21);
+ v2 += v1; v1 = rol64(v1, 17); v1 ^= v2; v2 = rol64(v2, 32);
+ return v1 ^ v2 ^ v3;
A 32-bit implementation could further tweak the 4 instructions of
v1 ^= v2; v2 = rol64(v2, 32); v1 ^= v2;
gcc 6.2.1 -O3 compiles it to basically:
v1.low ^= v2.low;
v1.high ^= v2.high;
v1.low ^= v2.high;
v1.high ^= v2.low;
but it could be written as:
v2.low ^= v2.high;
v1.low ^= v2.low;
v1.high ^= v2.low;
Alternatively, if it's for private use only (key not shared with other
systems), a slightly stronger variant would "return v1 ^ v3;".
(The final swap of v2 is dead code, but a compiler can spot that easily.)
next prev parent reply other threads:[~2016-12-15 22:42 UTC|newest]
Thread overview: 82+ 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 [this message]
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-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 ` [kernel-hardening] " Theodore Ts'o
2016-12-22 6:03 ` Jason A. Donenfeld
2016-12-22 15:58 ` Theodore Ts'o
2016-12-22 16:16 ` Jason A. Donenfeld
2016-12-22 16:30 ` Theodore Ts'o
2016-12-22 16:36 ` Jason A. Donenfeld
2016-12-22 12:47 ` Hannes Frederic Sowa
2016-12-22 13:10 ` 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 ` Jason A. Donenfeld
2016-12-22 15:51 ` Hannes Frederic Sowa
2016-12-22 15:53 ` Jason A. Donenfeld
2016-12-22 15:54 ` Theodore Ts'o
2016-12-22 18:08 ` Hannes Frederic Sowa
2016-12-22 18:13 ` Jason A. Donenfeld
2016-12-22 19:50 ` 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
[not found] <CAGiyFdfmiCMyHvAg=5sGh8KjBBrF0Wb4Qf=JLzJqUAx4yFSS3Q@mail.gmail.com>
2016-12-15 23:28 ` [PATCH v5 1/4] siphash: add cryptographically secure PRF George Spelvin
2016-12-16 17:06 ` David Laight
2016-12-16 17:09 ` Jason A. Donenfeld
2016-12-16 3:46 ` George Spelvin
[not found] ` <CAGiyFdd6_LVzUUfFcaqMyub1c2WPvWUzAQDCH+Aza-_t6mvmXg@mail.gmail.com>
2016-12-16 12: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-17 15:21 ` George Spelvin
2016-12-19 14:14 ` David Laight
2016-12-19 18:10 ` George Spelvin
[not found] ` <CAGiyFddB_HT3H2yhYQ5rprYZ487rJ4iCaH9uPJQD57hiPbn9ng@mail.gmail.com>
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 12:42 ` George Spelvin
2016-12-16 20:39 ` Jason A. Donenfeld
2016-12-16 20:43 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=20161215224224.21447.qmail@ns.sciencehorizons.net \
--to=linux@sciencehorizons.net \
--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=jeanphilippe.aumasson@gmail.com \
--cc=kernel-hardening@lists.openwall.com \
--cc=linux-crypto@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--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).