SipHash is a 64-bit keyed hash function that is actually a
cryptographically secure PRF, like HMAC. Except SipHash is super fast,
and is meant to be used as a hashtable keyed lookup function.
SipHash isn't just some new trendy hash function. It's been around for a
while, and there really isn't anything that comes remotely close to
being useful in the way SipHash is. With that said, why do we need this?
There are a variety of attacks known as "hashtable poisoning" in which an
attacker forms some data such that the hash of that data will be the
same, and then preceeds to fill up all entries of a hashbucket. This is
a realistic and well-known denial-of-service vector.
Linux developers already seem to be aware that this is an issue, and
various places that use hash tables in, say, a network context, use a
non-cryptographically secure function (usually jhash) and then try to
twiddle with the key on a time basis (or in many cases just do nothing
and hope that nobody notices). While this is an admirable attempt at
solving the problem, it doesn't actually fix it. SipHash fixes it.
(It fixes it in such a sound way that you could even build a stream
cipher out of SipHash that would resist the modern cryptanalysis.)
There are a modicum of places in the kernel that are vulnerable to
hashtable poisoning attacks, either via userspace vectors or network
vectors, and there's not a reliable mechanism inside the kernel at the
moment to fix it. The first step toward fixing these issues is actually
getting a secure primitive into the kernel for developers to use. Then
we can, bit by bit, port things over to it as deemed appropriate.
Dozens of languages are already using this internally for their hash
tables. Some of the BSDs already use this in their kernels. SipHash is
a widely known high-speed solution to a widely known problem, and it's
time we catch-up.
Signed-off-by: Jason A. Donenfeld <[email protected]>
Cc: Jean-Philippe Aumasson <[email protected]>
Cc: Daniel J. Bernstein <[email protected]>
---
include/linux/siphash.h | 18 ++++++
lib/Makefile | 3 +-
lib/siphash.c | 163 ++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 183 insertions(+), 1 deletion(-)
create mode 100644 include/linux/siphash.h
create mode 100644 lib/siphash.c
diff --git a/include/linux/siphash.h b/include/linux/siphash.h
new file mode 100644
index 000000000000..485c2101cc7d
--- /dev/null
+++ b/include/linux/siphash.h
@@ -0,0 +1,18 @@
+/* Copyright (C) 2016 Jason A. Donenfeld <[email protected]>
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#ifndef _LINUX_SIPHASH_H
+#define _LINUX_SIPHASH_H
+
+#include <linux/types.h>
+
+enum siphash24_lengths {
+ SIPHASH24_KEY_LEN = 16
+};
+
+uint64_t siphash24(const uint8_t *data, size_t len, const uint8_t key[SIPHASH24_KEY_LEN]);
+
+#endif /* _LINUX_SIPHASH_H */
diff --git a/lib/Makefile b/lib/Makefile
index 50144a3aeebd..d224337b0d01 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -22,7 +22,8 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
sha1.o chacha20.o md5.o irq_regs.o argv_split.o \
flex_proportions.o ratelimit.o show_mem.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
- earlycpio.o seq_buf.o nmi_backtrace.o nodemask.o win_minmax.o
+ earlycpio.o seq_buf.o siphash.o \
+ nmi_backtrace.o nodemask.o win_minmax.o
lib-$(CONFIG_MMU) += ioremap.o
lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/siphash.c b/lib/siphash.c
new file mode 100644
index 000000000000..022d86f04b9b
--- /dev/null
+++ b/lib/siphash.c
@@ -0,0 +1,163 @@
+/* Copyright (C) 2015-2016 Jason A. Donenfeld <[email protected]>
+ * Copyright (C) 2012-2014 Jean-Philippe Aumasson <[email protected]>
+ * Copyright (C) 2012-2014 Daniel J. Bernstein <[email protected]>
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#include <linux/siphash.h>
+#include <linux/kernel.h>
+#include <linux/string.h>
+
+#define ROTL(x,b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
+#define U8TO64(p) le64_to_cpu(*(__le64 *)(p))
+
+#define SIPROUND \
+ do { \
+ v0 += v1; v1 = ROTL(v1, 13); v1 ^= v0; v0 = ROTL(v0, 32); \
+ v2 += v3; v3 = ROTL(v3, 16); v3 ^= v2; \
+ v0 += v3; v3 = ROTL(v3, 21); v3 ^= v0; \
+ v2 += v1; v1 = ROTL(v1, 17); v1 ^= v2; v2 = ROTL(v2, 32); \
+ } while(0)
+
+__attribute__((optimize("unroll-loops")))
+uint64_t siphash24(const uint8_t *data, size_t len, const uint8_t key[SIPHASH24_KEY_LEN])
+{
+ uint64_t v0 = 0x736f6d6570736575ULL;
+ uint64_t v1 = 0x646f72616e646f6dULL;
+ uint64_t v2 = 0x6c7967656e657261ULL;
+ uint64_t v3 = 0x7465646279746573ULL;
+ uint64_t b;
+ uint64_t k0 = U8TO64(key);
+ uint64_t k1 = U8TO64(key + sizeof(uint64_t));
+ uint64_t m;
+ const uint8_t *end = data + len - (len % sizeof(uint64_t));
+ const uint8_t left = len & (sizeof(uint64_t) - 1);
+ b = ((uint64_t)len) << 56;
+ v3 ^= k1;
+ v2 ^= k0;
+ v1 ^= k1;
+ v0 ^= k0;
+ for (; data != end; data += sizeof(uint64_t)) {
+ m = U8TO64(data);
+ v3 ^= m;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= m;
+ }
+ switch (left) {
+ case 7: b |= ((uint64_t)data[6]) << 48;
+ case 6: b |= ((uint64_t)data[5]) << 40;
+ case 5: b |= ((uint64_t)data[4]) << 32;
+ case 4: b |= ((uint64_t)data[3]) << 24;
+ case 3: b |= ((uint64_t)data[2]) << 16;
+ case 2: b |= ((uint64_t)data[1]) << 8;
+ case 1: b |= ((uint64_t)data[0]); break;
+ case 0: break;
+ }
+ v3 ^= b;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= b;
+ v2 ^= 0xff;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ b = (v0 ^ v1) ^ (v2 ^ v3);
+ return (__force uint64_t)cpu_to_le64(b);
+}
+EXPORT_SYMBOL(siphash24);
+
+#ifdef DEBUG
+static const uint8_t test_vectors[64][8] = {
+ { 0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72 },
+ { 0xfd, 0x67, 0xdc, 0x93, 0xc5, 0x39, 0xf8, 0x74 },
+ { 0x5a, 0x4f, 0xa9, 0xd9, 0x09, 0x80, 0x6c, 0x0d },
+ { 0x2d, 0x7e, 0xfb, 0xd7, 0x96, 0x66, 0x67, 0x85 },
+ { 0xb7, 0x87, 0x71, 0x27, 0xe0, 0x94, 0x27, 0xcf },
+ { 0x8d, 0xa6, 0x99, 0xcd, 0x64, 0x55, 0x76, 0x18 },
+ { 0xce, 0xe3, 0xfe, 0x58, 0x6e, 0x46, 0xc9, 0xcb },
+ { 0x37, 0xd1, 0x01, 0x8b, 0xf5, 0x00, 0x02, 0xab },
+ { 0x62, 0x24, 0x93, 0x9a, 0x79, 0xf5, 0xf5, 0x93 },
+ { 0xb0, 0xe4, 0xa9, 0x0b, 0xdf, 0x82, 0x00, 0x9e },
+ { 0xf3, 0xb9, 0xdd, 0x94, 0xc5, 0xbb, 0x5d, 0x7a },
+ { 0xa7, 0xad, 0x6b, 0x22, 0x46, 0x2f, 0xb3, 0xf4 },
+ { 0xfb, 0xe5, 0x0e, 0x86, 0xbc, 0x8f, 0x1e, 0x75 },
+ { 0x90, 0x3d, 0x84, 0xc0, 0x27, 0x56, 0xea, 0x14 },
+ { 0xee, 0xf2, 0x7a, 0x8e, 0x90, 0xca, 0x23, 0xf7 },
+ { 0xe5, 0x45, 0xbe, 0x49, 0x61, 0xca, 0x29, 0xa1 },
+ { 0xdb, 0x9b, 0xc2, 0x57, 0x7f, 0xcc, 0x2a, 0x3f },
+ { 0x94, 0x47, 0xbe, 0x2c, 0xf5, 0xe9, 0x9a, 0x69 },
+ { 0x9c, 0xd3, 0x8d, 0x96, 0xf0, 0xb3, 0xc1, 0x4b },
+ { 0xbd, 0x61, 0x79, 0xa7, 0x1d, 0xc9, 0x6d, 0xbb },
+ { 0x98, 0xee, 0xa2, 0x1a, 0xf2, 0x5c, 0xd6, 0xbe },
+ { 0xc7, 0x67, 0x3b, 0x2e, 0xb0, 0xcb, 0xf2, 0xd0 },
+ { 0x88, 0x3e, 0xa3, 0xe3, 0x95, 0x67, 0x53, 0x93 },
+ { 0xc8, 0xce, 0x5c, 0xcd, 0x8c, 0x03, 0x0c, 0xa8 },
+ { 0x94, 0xaf, 0x49, 0xf6, 0xc6, 0x50, 0xad, 0xb8 },
+ { 0xea, 0xb8, 0x85, 0x8a, 0xde, 0x92, 0xe1, 0xbc },
+ { 0xf3, 0x15, 0xbb, 0x5b, 0xb8, 0x35, 0xd8, 0x17 },
+ { 0xad, 0xcf, 0x6b, 0x07, 0x63, 0x61, 0x2e, 0x2f },
+ { 0xa5, 0xc9, 0x1d, 0xa7, 0xac, 0xaa, 0x4d, 0xde },
+ { 0x71, 0x65, 0x95, 0x87, 0x66, 0x50, 0xa2, 0xa6 },
+ { 0x28, 0xef, 0x49, 0x5c, 0x53, 0xa3, 0x87, 0xad },
+ { 0x42, 0xc3, 0x41, 0xd8, 0xfa, 0x92, 0xd8, 0x32 },
+ { 0xce, 0x7c, 0xf2, 0x72, 0x2f, 0x51, 0x27, 0x71 },
+ { 0xe3, 0x78, 0x59, 0xf9, 0x46, 0x23, 0xf3, 0xa7 },
+ { 0x38, 0x12, 0x05, 0xbb, 0x1a, 0xb0, 0xe0, 0x12 },
+ { 0xae, 0x97, 0xa1, 0x0f, 0xd4, 0x34, 0xe0, 0x15 },
+ { 0xb4, 0xa3, 0x15, 0x08, 0xbe, 0xff, 0x4d, 0x31 },
+ { 0x81, 0x39, 0x62, 0x29, 0xf0, 0x90, 0x79, 0x02 },
+ { 0x4d, 0x0c, 0xf4, 0x9e, 0xe5, 0xd4, 0xdc, 0xca },
+ { 0x5c, 0x73, 0x33, 0x6a, 0x76, 0xd8, 0xbf, 0x9a },
+ { 0xd0, 0xa7, 0x04, 0x53, 0x6b, 0xa9, 0x3e, 0x0e },
+ { 0x92, 0x59, 0x58, 0xfc, 0xd6, 0x42, 0x0c, 0xad },
+ { 0xa9, 0x15, 0xc2, 0x9b, 0xc8, 0x06, 0x73, 0x18 },
+ { 0x95, 0x2b, 0x79, 0xf3, 0xbc, 0x0a, 0xa6, 0xd4 },
+ { 0xf2, 0x1d, 0xf2, 0xe4, 0x1d, 0x45, 0x35, 0xf9 },
+ { 0x87, 0x57, 0x75, 0x19, 0x04, 0x8f, 0x53, 0xa9 },
+ { 0x10, 0xa5, 0x6c, 0xf5, 0xdf, 0xcd, 0x9a, 0xdb },
+ { 0xeb, 0x75, 0x09, 0x5c, 0xcd, 0x98, 0x6c, 0xd0 },
+ { 0x51, 0xa9, 0xcb, 0x9e, 0xcb, 0xa3, 0x12, 0xe6 },
+ { 0x96, 0xaf, 0xad, 0xfc, 0x2c, 0xe6, 0x66, 0xc7 },
+ { 0x72, 0xfe, 0x52, 0x97, 0x5a, 0x43, 0x64, 0xee },
+ { 0x5a, 0x16, 0x45, 0xb2, 0x76, 0xd5, 0x92, 0xa1 },
+ { 0xb2, 0x74, 0xcb, 0x8e, 0xbf, 0x87, 0x87, 0x0a },
+ { 0x6f, 0x9b, 0xb4, 0x20, 0x3d, 0xe7, 0xb3, 0x81 },
+ { 0xea, 0xec, 0xb2, 0xa3, 0x0b, 0x22, 0xa8, 0x7f },
+ { 0x99, 0x24, 0xa4, 0x3c, 0xc1, 0x31, 0x57, 0x24 },
+ { 0xbd, 0x83, 0x8d, 0x3a, 0xaf, 0xbf, 0x8d, 0xb7 },
+ { 0x0b, 0x1a, 0x2a, 0x32, 0x65, 0xd5, 0x1a, 0xea },
+ { 0x13, 0x50, 0x79, 0xa3, 0x23, 0x1c, 0xe6, 0x60 },
+ { 0x93, 0x2b, 0x28, 0x46, 0xe4, 0xd7, 0x06, 0x66 },
+ { 0xe1, 0x91, 0x5f, 0x5c, 0xb1, 0xec, 0xa4, 0x6c },
+ { 0xf3, 0x25, 0x96, 0x5c, 0xa1, 0x6d, 0x62, 0x9f },
+ { 0x57, 0x5f, 0xf2, 0x8e, 0x60, 0x38, 0x1b, 0xe5 },
+ { 0x72, 0x45, 0x06, 0xeb, 0x4c, 0x32, 0x8a, 0x95 }
+};
+
+static int siphash24_selftest(void)
+{
+ uint8_t in[64], k[16], i;
+ uint64_t out;
+ int ret = 0;
+
+ for (i = 0; i < 16; ++i)
+ k[i] = i;
+
+ for (i = 0; i < 64; ++i) {
+ in[i] = i;
+ out = siphash24(in, i, k);
+ if (memcmp(&out, test_vectors[i], 8)) {
+ printk(KERN_INFO "siphash24: self-test %u: FAIL\n", i + 1);
+ ret = -1;
+ }
+ }
+ if (!ret)
+ printk(KERN_INFO "siphash24: self-tests: pass\n");
+ return ret;
+}
+__initcall(siphash24_selftest);
+#endif
--
2.11.0
On Fri, Dec 09, 2016 at 07:36:59PM +0100, Jason A. Donenfeld wrote:
> SipHash is a 64-bit keyed hash function that is actually a
> cryptographically secure PRF, like HMAC. Except SipHash is super fast,
> and is meant to be used as a hashtable keyed lookup function.
>
> SipHash isn't just some new trendy hash function. It's been around for a
> while, and there really isn't anything that comes remotely close to
> being useful in the way SipHash is. With that said, why do we need this?
>
> There are a variety of attacks known as "hashtable poisoning" in which an
> attacker forms some data such that the hash of that data will be the
> same, and then preceeds to fill up all entries of a hashbucket. This is
> a realistic and well-known denial-of-service vector.
>
> Linux developers already seem to be aware that this is an issue, and
> various places that use hash tables in, say, a network context, use a
> non-cryptographically secure function (usually jhash) and then try to
> twiddle with the key on a time basis (or in many cases just do nothing
> and hope that nobody notices). While this is an admirable attempt at
> solving the problem, it doesn't actually fix it. SipHash fixes it.
>
> (It fixes it in such a sound way that you could even build a stream
> cipher out of SipHash that would resist the modern cryptanalysis.)
>
> There are a modicum of places in the kernel that are vulnerable to
> hashtable poisoning attacks, either via userspace vectors or network
> vectors, and there's not a reliable mechanism inside the kernel at the
> moment to fix it. The first step toward fixing these issues is actually
> getting a secure primitive into the kernel for developers to use. Then
> we can, bit by bit, port things over to it as deemed appropriate.
>
> Dozens of languages are already using this internally for their hash
> tables. Some of the BSDs already use this in their kernels. SipHash is
> a widely known high-speed solution to a widely known problem, and it's
> time we catch-up.
>
> Signed-off-by: Jason A. Donenfeld <[email protected]>
> Cc: Jean-Philippe Aumasson <[email protected]>
> Cc: Daniel J. Bernstein <[email protected]>
> ---
> include/linux/siphash.h | 18 ++++++
> lib/Makefile | 3 +-
> lib/siphash.c | 163 ++++++++++++++++++++++++++++++++++++++++++++++++
> 3 files changed, 183 insertions(+), 1 deletion(-)
> create mode 100644 include/linux/siphash.h
> create mode 100644 lib/siphash.c
This looks really nice, but we don't usually add stuff into lib/ unless
there is an actual user of the code :)
Have you tried converting any of the existing hash users to use this
instead? If you did that, and it shows a solution for the known
problems with our existing hashes (as you point out above), I doubt
there would be any objection for this patch at all.
Minor coding style nits below:
> @@ -0,0 +1,18 @@
> +/* Copyright (C) 2016 Jason A. Donenfeld <[email protected]>
> + *
> + * SipHash: a fast short-input PRF
> + * https://131002.net/siphash/
> + */
> +
> +#ifndef _LINUX_SIPHASH_H
> +#define _LINUX_SIPHASH_H
> +
> +#include <linux/types.h>
> +
> +enum siphash24_lengths {
> + SIPHASH24_KEY_LEN = 16
> +};
> +
> +uint64_t siphash24(const uint8_t *data, size_t len, const uint8_t key[SIPHASH24_KEY_LEN]);
Please use u64 and u8 instead of the userspace uint64_t and uint8_t
types for kernel code. Yes, the ship has probably sailed for trying to
strictly enforce it, but it's a good idea to do where ever possible.
> +
> +#endif /* _LINUX_SIPHASH_H */
> diff --git a/lib/Makefile b/lib/Makefile
> index 50144a3aeebd..d224337b0d01 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -22,7 +22,8 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
> sha1.o chacha20.o md5.o irq_regs.o argv_split.o \
> flex_proportions.o ratelimit.o show_mem.o \
> is_single_threaded.o plist.o decompress.o kobject_uevent.o \
> - earlycpio.o seq_buf.o nmi_backtrace.o nodemask.o win_minmax.o
> + earlycpio.o seq_buf.o siphash.o \
> + nmi_backtrace.o nodemask.o win_minmax.o
>
> lib-$(CONFIG_MMU) += ioremap.o
> lib-$(CONFIG_SMP) += cpumask.o
> diff --git a/lib/siphash.c b/lib/siphash.c
> new file mode 100644
> index 000000000000..022d86f04b9b
> --- /dev/null
> +++ b/lib/siphash.c
> @@ -0,0 +1,163 @@
> +/* Copyright (C) 2015-2016 Jason A. Donenfeld <[email protected]>
> + * Copyright (C) 2012-2014 Jean-Philippe Aumasson <[email protected]>
> + * Copyright (C) 2012-2014 Daniel J. Bernstein <[email protected]>
> + *
> + * SipHash: a fast short-input PRF
> + * https://131002.net/siphash/
> + */
Any specific license for this code? It's good to at the least say what
it is. Yes, we know it will default to GPLv2 only as part of the whole
kernel tree, but it's good to be explicit for when someone wants to copy
this code for their own projects...
> +
> +#include <linux/siphash.h>
> +#include <linux/kernel.h>
> +#include <linux/string.h>
> +
> +#define ROTL(x,b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
Don't we have this in kernel.h somewhere? Ah, yeah, it's rol64() in
bitops.h, no need to define it again please.
> +#define U8TO64(p) le64_to_cpu(*(__le64 *)(p))
Why the crazy casting behind a macro?
> +
> +#define SIPROUND \
> + do { \
> + v0 += v1; v1 = ROTL(v1, 13); v1 ^= v0; v0 = ROTL(v0, 32); \
> + v2 += v3; v3 = ROTL(v3, 16); v3 ^= v2; \
> + v0 += v3; v3 = ROTL(v3, 21); v3 ^= v0; \
> + v2 += v1; v1 = ROTL(v1, 17); v1 ^= v2; v2 = ROTL(v2, 32); \
> + } while(0)
> +
> +__attribute__((optimize("unroll-loops")))
Care to document why this attribute is needed? Older versions of gcc
doesn't know how to handle it properly? Faster with newer versions?
Black magic? :)
> +uint64_t siphash24(const uint8_t *data, size_t len, const uint8_t key[SIPHASH24_KEY_LEN])
> +{
> + uint64_t v0 = 0x736f6d6570736575ULL;
s/uint64_t/u64/g please.
> + uint64_t v1 = 0x646f72616e646f6dULL;
> + uint64_t v2 = 0x6c7967656e657261ULL;
> + uint64_t v3 = 0x7465646279746573ULL;
> + uint64_t b;
> + uint64_t k0 = U8TO64(key);
> + uint64_t k1 = U8TO64(key + sizeof(uint64_t));
> + uint64_t m;
> + const uint8_t *end = data + len - (len % sizeof(uint64_t));
> + const uint8_t left = len & (sizeof(uint64_t) - 1);
> + b = ((uint64_t)len) << 56;
> + v3 ^= k1;
> + v2 ^= k0;
> + v1 ^= k1;
> + v0 ^= k0;
> + for (; data != end; data += sizeof(uint64_t)) {
> + m = U8TO64(data);
> + v3 ^= m;
> + SIPROUND;
> + SIPROUND;
> + v0 ^= m;
> + }
> + switch (left) {
> + case 7: b |= ((uint64_t)data[6]) << 48;
> + case 6: b |= ((uint64_t)data[5]) << 40;
> + case 5: b |= ((uint64_t)data[4]) << 32;
> + case 4: b |= ((uint64_t)data[3]) << 24;
> + case 3: b |= ((uint64_t)data[2]) << 16;
> + case 2: b |= ((uint64_t)data[1]) << 8;
> + case 1: b |= ((uint64_t)data[0]); break;
> + case 0: break;
> + }
> + v3 ^= b;
> + SIPROUND;
> + SIPROUND;
> + v0 ^= b;
> + v2 ^= 0xff;
> + SIPROUND;
> + SIPROUND;
> + SIPROUND;
> + SIPROUND;
> + b = (v0 ^ v1) ^ (v2 ^ v3);
> + return (__force uint64_t)cpu_to_le64(b);
> +}
> +EXPORT_SYMBOL(siphash24);
EXPORT_SYMBOL_GPL()? I have to ask, sorry :)
> +
> +#ifdef DEBUG
> +static const uint8_t test_vectors[64][8] = {
> + { 0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72 },
> + { 0xfd, 0x67, 0xdc, 0x93, 0xc5, 0x39, 0xf8, 0x74 },
> + { 0x5a, 0x4f, 0xa9, 0xd9, 0x09, 0x80, 0x6c, 0x0d },
> + { 0x2d, 0x7e, 0xfb, 0xd7, 0x96, 0x66, 0x67, 0x85 },
> + { 0xb7, 0x87, 0x71, 0x27, 0xe0, 0x94, 0x27, 0xcf },
> + { 0x8d, 0xa6, 0x99, 0xcd, 0x64, 0x55, 0x76, 0x18 },
> + { 0xce, 0xe3, 0xfe, 0x58, 0x6e, 0x46, 0xc9, 0xcb },
> + { 0x37, 0xd1, 0x01, 0x8b, 0xf5, 0x00, 0x02, 0xab },
> + { 0x62, 0x24, 0x93, 0x9a, 0x79, 0xf5, 0xf5, 0x93 },
> + { 0xb0, 0xe4, 0xa9, 0x0b, 0xdf, 0x82, 0x00, 0x9e },
> + { 0xf3, 0xb9, 0xdd, 0x94, 0xc5, 0xbb, 0x5d, 0x7a },
> + { 0xa7, 0xad, 0x6b, 0x22, 0x46, 0x2f, 0xb3, 0xf4 },
> + { 0xfb, 0xe5, 0x0e, 0x86, 0xbc, 0x8f, 0x1e, 0x75 },
> + { 0x90, 0x3d, 0x84, 0xc0, 0x27, 0x56, 0xea, 0x14 },
> + { 0xee, 0xf2, 0x7a, 0x8e, 0x90, 0xca, 0x23, 0xf7 },
> + { 0xe5, 0x45, 0xbe, 0x49, 0x61, 0xca, 0x29, 0xa1 },
> + { 0xdb, 0x9b, 0xc2, 0x57, 0x7f, 0xcc, 0x2a, 0x3f },
> + { 0x94, 0x47, 0xbe, 0x2c, 0xf5, 0xe9, 0x9a, 0x69 },
> + { 0x9c, 0xd3, 0x8d, 0x96, 0xf0, 0xb3, 0xc1, 0x4b },
> + { 0xbd, 0x61, 0x79, 0xa7, 0x1d, 0xc9, 0x6d, 0xbb },
> + { 0x98, 0xee, 0xa2, 0x1a, 0xf2, 0x5c, 0xd6, 0xbe },
> + { 0xc7, 0x67, 0x3b, 0x2e, 0xb0, 0xcb, 0xf2, 0xd0 },
> + { 0x88, 0x3e, 0xa3, 0xe3, 0x95, 0x67, 0x53, 0x93 },
> + { 0xc8, 0xce, 0x5c, 0xcd, 0x8c, 0x03, 0x0c, 0xa8 },
> + { 0x94, 0xaf, 0x49, 0xf6, 0xc6, 0x50, 0xad, 0xb8 },
> + { 0xea, 0xb8, 0x85, 0x8a, 0xde, 0x92, 0xe1, 0xbc },
> + { 0xf3, 0x15, 0xbb, 0x5b, 0xb8, 0x35, 0xd8, 0x17 },
> + { 0xad, 0xcf, 0x6b, 0x07, 0x63, 0x61, 0x2e, 0x2f },
> + { 0xa5, 0xc9, 0x1d, 0xa7, 0xac, 0xaa, 0x4d, 0xde },
> + { 0x71, 0x65, 0x95, 0x87, 0x66, 0x50, 0xa2, 0xa6 },
> + { 0x28, 0xef, 0x49, 0x5c, 0x53, 0xa3, 0x87, 0xad },
> + { 0x42, 0xc3, 0x41, 0xd8, 0xfa, 0x92, 0xd8, 0x32 },
> + { 0xce, 0x7c, 0xf2, 0x72, 0x2f, 0x51, 0x27, 0x71 },
> + { 0xe3, 0x78, 0x59, 0xf9, 0x46, 0x23, 0xf3, 0xa7 },
> + { 0x38, 0x12, 0x05, 0xbb, 0x1a, 0xb0, 0xe0, 0x12 },
> + { 0xae, 0x97, 0xa1, 0x0f, 0xd4, 0x34, 0xe0, 0x15 },
> + { 0xb4, 0xa3, 0x15, 0x08, 0xbe, 0xff, 0x4d, 0x31 },
> + { 0x81, 0x39, 0x62, 0x29, 0xf0, 0x90, 0x79, 0x02 },
> + { 0x4d, 0x0c, 0xf4, 0x9e, 0xe5, 0xd4, 0xdc, 0xca },
> + { 0x5c, 0x73, 0x33, 0x6a, 0x76, 0xd8, 0xbf, 0x9a },
> + { 0xd0, 0xa7, 0x04, 0x53, 0x6b, 0xa9, 0x3e, 0x0e },
> + { 0x92, 0x59, 0x58, 0xfc, 0xd6, 0x42, 0x0c, 0xad },
> + { 0xa9, 0x15, 0xc2, 0x9b, 0xc8, 0x06, 0x73, 0x18 },
> + { 0x95, 0x2b, 0x79, 0xf3, 0xbc, 0x0a, 0xa6, 0xd4 },
> + { 0xf2, 0x1d, 0xf2, 0xe4, 0x1d, 0x45, 0x35, 0xf9 },
> + { 0x87, 0x57, 0x75, 0x19, 0x04, 0x8f, 0x53, 0xa9 },
> + { 0x10, 0xa5, 0x6c, 0xf5, 0xdf, 0xcd, 0x9a, 0xdb },
> + { 0xeb, 0x75, 0x09, 0x5c, 0xcd, 0x98, 0x6c, 0xd0 },
> + { 0x51, 0xa9, 0xcb, 0x9e, 0xcb, 0xa3, 0x12, 0xe6 },
> + { 0x96, 0xaf, 0xad, 0xfc, 0x2c, 0xe6, 0x66, 0xc7 },
> + { 0x72, 0xfe, 0x52, 0x97, 0x5a, 0x43, 0x64, 0xee },
> + { 0x5a, 0x16, 0x45, 0xb2, 0x76, 0xd5, 0x92, 0xa1 },
> + { 0xb2, 0x74, 0xcb, 0x8e, 0xbf, 0x87, 0x87, 0x0a },
> + { 0x6f, 0x9b, 0xb4, 0x20, 0x3d, 0xe7, 0xb3, 0x81 },
> + { 0xea, 0xec, 0xb2, 0xa3, 0x0b, 0x22, 0xa8, 0x7f },
> + { 0x99, 0x24, 0xa4, 0x3c, 0xc1, 0x31, 0x57, 0x24 },
> + { 0xbd, 0x83, 0x8d, 0x3a, 0xaf, 0xbf, 0x8d, 0xb7 },
> + { 0x0b, 0x1a, 0x2a, 0x32, 0x65, 0xd5, 0x1a, 0xea },
> + { 0x13, 0x50, 0x79, 0xa3, 0x23, 0x1c, 0xe6, 0x60 },
> + { 0x93, 0x2b, 0x28, 0x46, 0xe4, 0xd7, 0x06, 0x66 },
> + { 0xe1, 0x91, 0x5f, 0x5c, 0xb1, 0xec, 0xa4, 0x6c },
> + { 0xf3, 0x25, 0x96, 0x5c, 0xa1, 0x6d, 0x62, 0x9f },
> + { 0x57, 0x5f, 0xf2, 0x8e, 0x60, 0x38, 0x1b, 0xe5 },
> + { 0x72, 0x45, 0x06, 0xeb, 0x4c, 0x32, 0x8a, 0x95 }
> +};
> +
> +static int siphash24_selftest(void)
> +{
> + uint8_t in[64], k[16], i;
> + uint64_t out;
> + int ret = 0;
> +
> + for (i = 0; i < 16; ++i)
> + k[i] = i;
> +
> + for (i = 0; i < 64; ++i) {
> + in[i] = i;
> + out = siphash24(in, i, k);
> + if (memcmp(&out, test_vectors[i], 8)) {
> + printk(KERN_INFO "siphash24: self-test %u: FAIL\n", i + 1);
pr_info()?
> + ret = -1;
Pick a real error number?
> + }
> + }
> + if (!ret)
> + printk(KERN_INFO "siphash24: self-tests: pass\n");
pr_info()?
> + return ret;
> +}
> +__initcall(siphash24_selftest);
Don't we have a "do crypto/library/whatever selftests at boot" config
option that this little test could be put under? It would be great to
not have to manually add DEBUG to the build to verify this works on a
specific arch.
thanks,
greg k-h
On 9 December 2016 at 19:36, Jason A. Donenfeld <[email protected]> wrote:
> SipHash is a 64-bit keyed hash function that is actually a
> cryptographically secure PRF, like HMAC. Except SipHash is super fast,
> and is meant to be used as a hashtable keyed lookup function.
>
> SipHash isn't just some new trendy hash function. It's been around for a
> while, and there really isn't anything that comes remotely close to
> being useful in the way SipHash is. With that said, why do we need this?
>
> There are a variety of attacks known as "hashtable poisoning" in which an
> attacker forms some data such that the hash of that data will be the
> same, and then preceeds to fill up all entries of a hashbucket. This is
> a realistic and well-known denial-of-service vector.
>
> Linux developers already seem to be aware that this is an issue, and
> various places that use hash tables in, say, a network context, use a
> non-cryptographically secure function (usually jhash) and then try to
> twiddle with the key on a time basis (or in many cases just do nothing
> and hope that nobody notices). While this is an admirable attempt at
> solving the problem, it doesn't actually fix it. SipHash fixes it.
Could you give some more concrete details/examples? Here's the IPv4
hash table from include/net/inet_sock.h / net/ipv4/inet_hashtables.c:
static inline unsigned int __inet_ehashfn(const __be32 laddr,
const __u16 lport,
const __be32 faddr,
const __be16 fport,
u32 initval)
{
return jhash_3words((__force __u32) laddr,
(__force __u32) faddr,
((__u32) lport) << 16 | (__force __u32)fport,
initval);
}
static u32 inet_ehashfn(const struct net *net, const __be32 laddr,
const __u16 lport, const __be32 faddr,
const __be16 fport)
{
static u32 inet_ehash_secret __read_mostly;
net_get_random_once(&inet_ehash_secret, sizeof(inet_ehash_secret));
return __inet_ehashfn(laddr, lport, faddr, fport,
inet_ehash_secret + net_hash_mix(net));
}
There's a 32-bit secret random salt (inet_ehash_secret) which means
that in practice, inet_ehashfn() will select 1 out of 2^32 different
hash functions at random each time you boot the kernel; without
knowing which one it selected, how can a local or remote attacker can
force IPv4 connections/whatever to go into a single hash bucket?
It is not possible to obtain the secret salt directly (except by
reading from kernel memory, in which case you've lost already), nor is
it possible to obtain the result of inet_ehashfn() other than (maybe)
by a timing attack where you somehow need to detect that two
connections went into the same hash bucket and work backwards from
that to figure out how to land more connections into into the same
bucket -- but if they can do that, you've also already lost.
The same pattern is used for IPv6 hashtables and the dentry cache.
I suppose that using a hash function proven to be cryptographically
secure gives a hard guarantee (under some assumptions) that the
salt/key will give enough diversity between the (in the example above)
2^32 different hash functions that you cannot improve your chances of
guessing that two values will map to the same bucket regardless of the
salt/key. However, I am a bit doubtful that using a cryptographically
secure hash function will make much of a difference as long as the
attacker doesn't actually have any way to get the output/result of the
hash function (and given that the hash function isn't completely
trivial, of course).
I am happy to be proven wrong, but you make it sound very easy to
exploit the current situation, so I would just like to ask whether you
have a concrete way to do that?
Vegard
> There are a modicum of places in the kernel that are vulnerable to
> hashtable poisoning attacks, either via userspace vectors or network
> vectors, and there's not a reliable mechanism inside the kernel at the
> moment to fix it. The first step toward fixing these issues is actually
> getting a secure primitive into the kernel for developers to use. Then
> we can, bit by bit, port things over to it as deemed appropriate.
>
> Dozens of languages are already using this internally for their hash
> tables. Some of the BSDs already use this in their kernels. SipHash is
> a widely known high-speed solution to a widely known problem, and it's
> time we catch-up.
> There's a 32-bit secret random salt (inet_ehash_secret) which means
> that in practice, inet_ehashfn() will select 1 out of 2^32 different
> hash functions at random each time you boot the kernel; without
> knowing which one it selected, how can a local or remote attacker can
> force IPv4 connections/whatever to go into a single hash bucket?
By figuring out the salt. The thing is, the timing of hash table lookups
*is externally visible*. If I create connections to the target, then
see which ones make responses on previous connections slightly slower,
I gain information about the salt.
I dont't know *where* in the hash table the collissions occur, but I
know *which* inputs collide, and that's enough for me to learn something.
(I need more connections than the size of the hash table, but even
with just one IP source I can use 64K ports on my end times however
many the target has open on its end.)
With enough information (google "unicity distance") I can recover the
entire salt. It's not like I care about the cryptographic strength of
the hash; simply trying all 4 billion possible seeds is pretty fast on
a 4 GHz processor.
Once that happens, I can choose a target connection whose timing I can't
observe directly and pack its hash chain without being obvious about it.
> I am happy to be proven wrong, but you make it sound very easy to
> exploit the current situation, so I would just like to ask whether you
> have a concrete way to do that?
I don't think anyone's implemented an attack on this particular hash
table yet, and the reason it hasn't been urgent is that it's just a mild
DoS attack it makes the computer noticeably slower withough disabling
it completely.
But the general style of attack is well known and has been repeatedly
demonstrated. Its practicality is not in question. The only question is
whether it's *more* practical that simpler techniques that don't depend
on any such algorithmic subtlety like brute-force flooding.
But if the history of Internet security has taught us one thing, it's
that naively hoping something won't be a problem is doomed.
The main issue is performance. IPv6 addresses are big, and although
SipHash is fast by the standard of cryptographic hashes, it's far slower
than jhash or any other non-cryptographic hash.
Hi Greg,
Thanks for the review. Responses to your suggestions are inline below:
On Sat, Dec 10, 2016 at 1:37 PM, Greg KH <[email protected]> wrote:
> Please use u64 and u8 instead of the userspace uint64_t and uint8_t
> types for kernel code. Yes, the ship has probably sailed for trying to
> strictly enforce it, but it's a good idea to do where ever possible.
I didn't know this was a rule. Since I had seen a hodgepodge
throughout the kernel I just sort of assumed it was a free for all.
I've fixed this up for v2, and I've also gone through all of my other
[not yet submitted] code and made this change.
> Any specific license for this code? It's good to at the least say what
> it is. Yes, we know it will default to GPLv2 only as part of the whole
> kernel tree, but it's good to be explicit for when someone wants to copy
> this code for their own projects...
Public domain, actually. I'll add notice of this to the header.
> Don't we have this in kernel.h somewhere? Ah, yeah, it's rol64() in
> bitops.h, no need to define it again please.
Thanks!
>
>> +#define U8TO64(p) le64_to_cpu(*(__le64 *)(p))
>
> Why the crazy casting behind a macro?
le64_to_cpup doesn't take the right type. But I agree the macro is not
the nicest way to do this. Instead, I'll copy what
crypto/chacha20_generic.c does and define locally le64_to_cpuvp which
takes a void pointer:
static inline u64 le64_to_cpuvp(const void *p)
{
return le64_to_cpup(p);
}
>> +__attribute__((optimize("unroll-loops")))
>
> Care to document why this attribute is needed? Older versions of gcc
> doesn't know how to handle it properly? Faster with newer versions?
> Black magic? :)
It tells gcc to unroll the loops. Comparing the assembly, it looks
like on x86_64, gcc does twice as many rounds per loop iteration when
asked to unroll the loops. This allows the code to remain neat and
straightforward, while instructing gcc to do the gnarly part.
Is this too much rice? Have I been Gentoo-ing for too long? Or are
limited uses of unroll-loops acceptable?
> s/uint64_t/u64/g please.
Done.
> EXPORT_SYMBOL_GPL()? I have to ask, sorry :)
Since it's public domain, EXPORT_SYMBOL() is fine.
If you have some reason for preferring GPL2 over public domain, I'm
happy to make the change. Maybe you want to preclude the new&shiny
from proprietary modules? That's fine with me, if you desire it being
that way.
>
>
> pr_info()?
Ack.
>
>> + ret = -1;
>
> Pick a real error number?
I started to do this, but couldn't make up my mind, and then resigned
to -1. I'll redouble my efforts to pick something decent.
> pr_info()?
Ack.
> Don't we have a "do crypto/library/whatever selftests at boot" config
> option that this little test could be put under? It would be great to
> not have to manually add DEBUG to the build to verify this works on a
> specific arch.
There is crypto/testmgr.c, but it's designed for testing things that
use the actual crypto API. Clearly for a hashtable function, nobody
would accept the overhead of the enormous crypto API, so siphash has
to remain an ordinary fast function call. Also, it lives in lib/, not
in crypto/. For that reason, I thought that Herbert might object if I
clutter up his testmgr with non crypto API functions. I'll CC him on
this email to double check.
> This looks really nice, but we don't usually add stuff into lib/ unless
> there is an actual user of the code :)
>
> Have you tried converting any of the existing hash users to use this
> instead? If you did that, and it shows a solution for the known
> problems with our existing hashes (as you point out above), I doubt
> there would be any objection for this patch at all.
Here's where the controversy begins! As we've seen from this thread,
there are two hurdles:
1. Convincing people that the cryptographic properties of siphash are
important, and jhash does not have these. I think JP Aumasson's email
described things pretty clearly, and this isn't really up for debate
anymore.
2. Convincing people that for a particular use case, siphash _is_
sufficiently fast, and that any potential (tiny) slowdown, compared to
insecure function like jhash, is either a) not worth having a
known-vulnerability or b) not even measurably relavent for the actual
real life workload.
I suspect that the debates about (2.a) and (2.b) will need to be duked
out one-by-one for a bit of time. I thought that since this will be
more of an evolutionary change, it'd be best to at least get the
primitives into lib/ so they can actually be used.
For example, I found some patches from George Spelvin (CC'd) trying to
get this added a few years back, for reasons related to extfs code. I
found a discussion between Scott Bauer (CC'd) and Andy&Andi (CC'd)
about adding siphash for the purpose of SROP mitigation, but not doing
so because there wasn't the primitive in lib/.
Seeing that siphash is both a solution to current existing problems,
future security mechanisms, and current things people clearly seem to
want, I thought it might be worthwhile to add this straight-up.
But if you really really want me to submit this alongside a patch
series of places that could be changed, I guess I could take the time
to pick out the most uncontroversial places -- some network stack /
netfilter places, some userspace API hashtable DoS places, etc -- but
I fear that's going to drag so many different consumers into the fold
that in the end nothing will get merged. So I think this might be a
good case for an exception with /lib, as a means of making forward
progress in general. Feel free to disagree, though; you know best.
Regards,
Jason
On Sun, Dec 11, 2016 at 04:30:31PM +0100, Jason A. Donenfeld wrote:
> Hi Greg,
>
> Thanks for the review. Responses to your suggestions are inline below:
>
> On Sat, Dec 10, 2016 at 1:37 PM, Greg KH <[email protected]> wrote:
> > Please use u64 and u8 instead of the userspace uint64_t and uint8_t
> > types for kernel code. Yes, the ship has probably sailed for trying to
> > strictly enforce it, but it's a good idea to do where ever possible.
>
> I didn't know this was a rule. Since I had seen a hodgepodge
> throughout the kernel I just sort of assumed it was a free for all.
> I've fixed this up for v2, and I've also gone through all of my other
> [not yet submitted] code and made this change.
>
> > Any specific license for this code? It's good to at the least say what
> > it is. Yes, we know it will default to GPLv2 only as part of the whole
> > kernel tree, but it's good to be explicit for when someone wants to copy
> > this code for their own projects...
>
> Public domain, actually. I'll add notice of this to the header.
Hm, there really is no such license as "Public domain" that works in all
countries, sorry. You will note it's not one of the "valid module
license list" we have in module.h because of that.
So, I don't know where you got the code from, but perhaps "Dual BSD/GPL"
is the correct one for you?
Note, I'm not a lawyer, so this isn't legal advice about the license of
code, but I do spend way too much time with lawyers dealing with license
issues...
> >> +#define U8TO64(p) le64_to_cpu(*(__le64 *)(p))
> >
> > Why the crazy casting behind a macro?
>
> le64_to_cpup doesn't take the right type. But I agree the macro is not
> the nicest way to do this. Instead, I'll copy what
> crypto/chacha20_generic.c does and define locally le64_to_cpuvp which
> takes a void pointer:
>
> static inline u64 le64_to_cpuvp(const void *p)
> {
> return le64_to_cpup(p);
> }
Ah much better.
> >> +__attribute__((optimize("unroll-loops")))
> >
> > Care to document why this attribute is needed? Older versions of gcc
> > doesn't know how to handle it properly? Faster with newer versions?
> > Black magic? :)
>
> It tells gcc to unroll the loops. Comparing the assembly, it looks
> like on x86_64, gcc does twice as many rounds per loop iteration when
> asked to unroll the loops. This allows the code to remain neat and
> straightforward, while instructing gcc to do the gnarly part.
>
> Is this too much rice? Have I been Gentoo-ing for too long? Or are
> limited uses of unroll-loops acceptable?
Given that this would be the first use of it in the kernel, it might be
too much rice :)
Unless you can show real numbers that it actually matters, I wouldn't do
it, it's not worth the hassle. That's the same rule for when you use
likely()/unlikely(), if you can not measure it, don't use it as you
almost always get it wrong, the compiler is smarter, and keeps getting
better over time.
> > s/uint64_t/u64/g please.
>
> Done.
>
> > EXPORT_SYMBOL_GPL()? I have to ask, sorry :)
>
> Since it's public domain, EXPORT_SYMBOL() is fine.
>
> If you have some reason for preferring GPL2 over public domain, I'm
> happy to make the change. Maybe you want to preclude the new&shiny
> from proprietary modules? That's fine with me, if you desire it being
> that way.
Nope, I just have to ask :)
If it's dual licensed, a normal EXPORT_SYMBOL() is just fine, I have no
objection to that at all.
thanks,
greg k-h
SipHash is a 64-bit keyed hash function that is actually a
cryptographically secure PRF, like HMAC. Except SipHash is super fast,
and is meant to be used as a hashtable keyed lookup function.
SipHash isn't just some new trendy hash function. It's been around for a
while, and there really isn't anything that comes remotely close to
being useful in the way SipHash is. With that said, why do we need this?
There are a variety of attacks known as "hashtable poisoning" in which an
attacker forms some data such that the hash of that data will be the
same, and then preceeds to fill up all entries of a hashbucket. This is
a realistic and well-known denial-of-service vector.
Linux developers already seem to be aware that this is an issue, and
various places that use hash tables in, say, a network context, use a
non-cryptographically secure function (usually jhash) and then try to
twiddle with the key on a time basis (or in many cases just do nothing
and hope that nobody notices). While this is an admirable attempt at
solving the problem, it doesn't actually fix it. SipHash fixes it.
(It fixes it in such a sound way that you could even build a stream
cipher out of SipHash that would resist the modern cryptanalysis.)
There are a modicum of places in the kernel that are vulnerable to
hashtable poisoning attacks, either via userspace vectors or network
vectors, and there's not a reliable mechanism inside the kernel at the
moment to fix it. The first step toward fixing these issues is actually
getting a secure primitive into the kernel for developers to use. Then
we can, bit by bit, port things over to it as deemed appropriate.
Dozens of languages are already using this internally for their hash
tables. Some of the BSDs already use this in their kernels. SipHash is
a widely known high-speed solution to a widely known problem, and it's
time we catch-up.
Signed-off-by: Jason A. Donenfeld <[email protected]>
Cc: Jean-Philippe Aumasson <[email protected]>
Cc: Daniel J. Bernstein <[email protected]>
---
include/linux/siphash.h | 20 +++++++++
lib/Makefile | 5 ++-
lib/siphash.c | 72 ++++++++++++++++++++++++++++++
lib/test_siphash.c | 116 ++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 211 insertions(+), 2 deletions(-)
create mode 100644 include/linux/siphash.h
create mode 100644 lib/siphash.c
create mode 100644 lib/test_siphash.c
diff --git a/include/linux/siphash.h b/include/linux/siphash.h
new file mode 100644
index 000000000000..6623b3090645
--- /dev/null
+++ b/include/linux/siphash.h
@@ -0,0 +1,20 @@
+/* Copyright (C) 2016 Jason A. Donenfeld <[email protected]>
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#ifndef _LINUX_SIPHASH_H
+#define _LINUX_SIPHASH_H
+
+#include <linux/types.h>
+
+enum siphash_lengths {
+ SIPHASH24_KEY_LEN = 16
+};
+
+u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]);
+
+#endif /* _LINUX_SIPHASH_H */
diff --git a/lib/Makefile b/lib/Makefile
index 50144a3aeebd..71d398b04a74 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -22,7 +22,8 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
sha1.o chacha20.o md5.o irq_regs.o argv_split.o \
flex_proportions.o ratelimit.o show_mem.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
- earlycpio.o seq_buf.o nmi_backtrace.o nodemask.o win_minmax.o
+ earlycpio.o seq_buf.o siphash.o \
+ nmi_backtrace.o nodemask.o win_minmax.o
lib-$(CONFIG_MMU) += ioremap.o
lib-$(CONFIG_SMP) += cpumask.o
@@ -44,7 +45,7 @@ obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
obj-y += kstrtox.o
obj-$(CONFIG_TEST_BPF) += test_bpf.o
obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
-obj-$(CONFIG_TEST_HASH) += test_hash.o
+obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
obj-$(CONFIG_TEST_KASAN) += test_kasan.o
obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
obj-$(CONFIG_TEST_LKM) += test_module.o
diff --git a/lib/siphash.c b/lib/siphash.c
new file mode 100644
index 000000000000..e78dc36d19b9
--- /dev/null
+++ b/lib/siphash.c
@@ -0,0 +1,72 @@
+/* Copyright (C) 2015-2016 Jason A. Donenfeld <[email protected]>
+ * Copyright (C) 2012-2014 Jean-Philippe Aumasson <[email protected]>
+ * Copyright (C) 2012-2014 Daniel J. Bernstein <[email protected]>
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#include <linux/siphash.h>
+#include <linux/kernel.h>
+
+static inline u64 le64_to_cpuvp(const void *p)
+{
+ return le64_to_cpup(p);
+}
+
+#define SIPROUND \
+ do { \
+ 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); \
+ } while(0)
+
+u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN])
+{
+ u64 v0 = 0x736f6d6570736575ULL;
+ u64 v1 = 0x646f72616e646f6dULL;
+ u64 v2 = 0x6c7967656e657261ULL;
+ u64 v3 = 0x7465646279746573ULL;
+ u64 b = ((u64)len) << 56;
+ u64 k0 = le64_to_cpuvp(key);
+ u64 k1 = le64_to_cpuvp(key + sizeof(u64));
+ u64 m;
+ const u8 *end = data + len - (len % sizeof(u64));
+ const u8 left = len & (sizeof(u64) - 1);
+ v3 ^= k1;
+ v2 ^= k0;
+ v1 ^= k1;
+ v0 ^= k0;
+ for (; data != end; data += sizeof(u64)) {
+ m = le64_to_cpuvp(data);
+ v3 ^= m;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= m;
+ }
+ switch (left) {
+ case 7: b |= ((u64)data[6]) << 48;
+ case 6: b |= ((u64)data[5]) << 40;
+ case 5: b |= ((u64)data[4]) << 32;
+ case 4: b |= ((u64)data[3]) << 24;
+ case 3: b |= ((u64)data[2]) << 16;
+ case 2: b |= ((u64)data[1]) << 8;
+ case 1: b |= ((u64)data[0]); break;
+ case 0: break;
+ }
+ v3 ^= b;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= b;
+ v2 ^= 0xff;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ b = (v0 ^ v1) ^ (v2 ^ v3);
+ return (__force u64)cpu_to_le64(b);
+}
+EXPORT_SYMBOL(siphash24);
diff --git a/lib/test_siphash.c b/lib/test_siphash.c
new file mode 100644
index 000000000000..45b5435540e9
--- /dev/null
+++ b/lib/test_siphash.c
@@ -0,0 +1,116 @@
+/* Test cases for siphash.c
+ *
+ * Copyright (C) 2015-2016 Jason A. Donenfeld <[email protected]>
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/siphash.h>
+#include <linux/kernel.h>
+#include <linux/string.h>
+#include <linux/errno.h>
+#include <linux/module.h>
+
+static const u8 test_vectors[64][8] = {
+ { 0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72 },
+ { 0xfd, 0x67, 0xdc, 0x93, 0xc5, 0x39, 0xf8, 0x74 },
+ { 0x5a, 0x4f, 0xa9, 0xd9, 0x09, 0x80, 0x6c, 0x0d },
+ { 0x2d, 0x7e, 0xfb, 0xd7, 0x96, 0x66, 0x67, 0x85 },
+ { 0xb7, 0x87, 0x71, 0x27, 0xe0, 0x94, 0x27, 0xcf },
+ { 0x8d, 0xa6, 0x99, 0xcd, 0x64, 0x55, 0x76, 0x18 },
+ { 0xce, 0xe3, 0xfe, 0x58, 0x6e, 0x46, 0xc9, 0xcb },
+ { 0x37, 0xd1, 0x01, 0x8b, 0xf5, 0x00, 0x02, 0xab },
+ { 0x62, 0x24, 0x93, 0x9a, 0x79, 0xf5, 0xf5, 0x93 },
+ { 0xb0, 0xe4, 0xa9, 0x0b, 0xdf, 0x82, 0x00, 0x9e },
+ { 0xf3, 0xb9, 0xdd, 0x94, 0xc5, 0xbb, 0x5d, 0x7a },
+ { 0xa7, 0xad, 0x6b, 0x22, 0x46, 0x2f, 0xb3, 0xf4 },
+ { 0xfb, 0xe5, 0x0e, 0x86, 0xbc, 0x8f, 0x1e, 0x75 },
+ { 0x90, 0x3d, 0x84, 0xc0, 0x27, 0x56, 0xea, 0x14 },
+ { 0xee, 0xf2, 0x7a, 0x8e, 0x90, 0xca, 0x23, 0xf7 },
+ { 0xe5, 0x45, 0xbe, 0x49, 0x61, 0xca, 0x29, 0xa1 },
+ { 0xdb, 0x9b, 0xc2, 0x57, 0x7f, 0xcc, 0x2a, 0x3f },
+ { 0x94, 0x47, 0xbe, 0x2c, 0xf5, 0xe9, 0x9a, 0x69 },
+ { 0x9c, 0xd3, 0x8d, 0x96, 0xf0, 0xb3, 0xc1, 0x4b },
+ { 0xbd, 0x61, 0x79, 0xa7, 0x1d, 0xc9, 0x6d, 0xbb },
+ { 0x98, 0xee, 0xa2, 0x1a, 0xf2, 0x5c, 0xd6, 0xbe },
+ { 0xc7, 0x67, 0x3b, 0x2e, 0xb0, 0xcb, 0xf2, 0xd0 },
+ { 0x88, 0x3e, 0xa3, 0xe3, 0x95, 0x67, 0x53, 0x93 },
+ { 0xc8, 0xce, 0x5c, 0xcd, 0x8c, 0x03, 0x0c, 0xa8 },
+ { 0x94, 0xaf, 0x49, 0xf6, 0xc6, 0x50, 0xad, 0xb8 },
+ { 0xea, 0xb8, 0x85, 0x8a, 0xde, 0x92, 0xe1, 0xbc },
+ { 0xf3, 0x15, 0xbb, 0x5b, 0xb8, 0x35, 0xd8, 0x17 },
+ { 0xad, 0xcf, 0x6b, 0x07, 0x63, 0x61, 0x2e, 0x2f },
+ { 0xa5, 0xc9, 0x1d, 0xa7, 0xac, 0xaa, 0x4d, 0xde },
+ { 0x71, 0x65, 0x95, 0x87, 0x66, 0x50, 0xa2, 0xa6 },
+ { 0x28, 0xef, 0x49, 0x5c, 0x53, 0xa3, 0x87, 0xad },
+ { 0x42, 0xc3, 0x41, 0xd8, 0xfa, 0x92, 0xd8, 0x32 },
+ { 0xce, 0x7c, 0xf2, 0x72, 0x2f, 0x51, 0x27, 0x71 },
+ { 0xe3, 0x78, 0x59, 0xf9, 0x46, 0x23, 0xf3, 0xa7 },
+ { 0x38, 0x12, 0x05, 0xbb, 0x1a, 0xb0, 0xe0, 0x12 },
+ { 0xae, 0x97, 0xa1, 0x0f, 0xd4, 0x34, 0xe0, 0x15 },
+ { 0xb4, 0xa3, 0x15, 0x08, 0xbe, 0xff, 0x4d, 0x31 },
+ { 0x81, 0x39, 0x62, 0x29, 0xf0, 0x90, 0x79, 0x02 },
+ { 0x4d, 0x0c, 0xf4, 0x9e, 0xe5, 0xd4, 0xdc, 0xca },
+ { 0x5c, 0x73, 0x33, 0x6a, 0x76, 0xd8, 0xbf, 0x9a },
+ { 0xd0, 0xa7, 0x04, 0x53, 0x6b, 0xa9, 0x3e, 0x0e },
+ { 0x92, 0x59, 0x58, 0xfc, 0xd6, 0x42, 0x0c, 0xad },
+ { 0xa9, 0x15, 0xc2, 0x9b, 0xc8, 0x06, 0x73, 0x18 },
+ { 0x95, 0x2b, 0x79, 0xf3, 0xbc, 0x0a, 0xa6, 0xd4 },
+ { 0xf2, 0x1d, 0xf2, 0xe4, 0x1d, 0x45, 0x35, 0xf9 },
+ { 0x87, 0x57, 0x75, 0x19, 0x04, 0x8f, 0x53, 0xa9 },
+ { 0x10, 0xa5, 0x6c, 0xf5, 0xdf, 0xcd, 0x9a, 0xdb },
+ { 0xeb, 0x75, 0x09, 0x5c, 0xcd, 0x98, 0x6c, 0xd0 },
+ { 0x51, 0xa9, 0xcb, 0x9e, 0xcb, 0xa3, 0x12, 0xe6 },
+ { 0x96, 0xaf, 0xad, 0xfc, 0x2c, 0xe6, 0x66, 0xc7 },
+ { 0x72, 0xfe, 0x52, 0x97, 0x5a, 0x43, 0x64, 0xee },
+ { 0x5a, 0x16, 0x45, 0xb2, 0x76, 0xd5, 0x92, 0xa1 },
+ { 0xb2, 0x74, 0xcb, 0x8e, 0xbf, 0x87, 0x87, 0x0a },
+ { 0x6f, 0x9b, 0xb4, 0x20, 0x3d, 0xe7, 0xb3, 0x81 },
+ { 0xea, 0xec, 0xb2, 0xa3, 0x0b, 0x22, 0xa8, 0x7f },
+ { 0x99, 0x24, 0xa4, 0x3c, 0xc1, 0x31, 0x57, 0x24 },
+ { 0xbd, 0x83, 0x8d, 0x3a, 0xaf, 0xbf, 0x8d, 0xb7 },
+ { 0x0b, 0x1a, 0x2a, 0x32, 0x65, 0xd5, 0x1a, 0xea },
+ { 0x13, 0x50, 0x79, 0xa3, 0x23, 0x1c, 0xe6, 0x60 },
+ { 0x93, 0x2b, 0x28, 0x46, 0xe4, 0xd7, 0x06, 0x66 },
+ { 0xe1, 0x91, 0x5f, 0x5c, 0xb1, 0xec, 0xa4, 0x6c },
+ { 0xf3, 0x25, 0x96, 0x5c, 0xa1, 0x6d, 0x62, 0x9f },
+ { 0x57, 0x5f, 0xf2, 0x8e, 0x60, 0x38, 0x1b, 0xe5 },
+ { 0x72, 0x45, 0x06, 0xeb, 0x4c, 0x32, 0x8a, 0x95 }
+};
+
+static int __init siphash_test_init(void)
+{
+ u8 in[64], k[16], i;
+ u64 out;
+ int ret = 0;
+
+ for (i = 0; i < 16; ++i)
+ k[i] = i;
+
+ for (i = 0; i < 64; ++i) {
+ in[i] = i;
+ out = siphash24(in, i, k);
+ if (memcmp(&out, test_vectors[i], 8)) {
+ pr_info("self-test %u: FAIL\n", i + 1);
+ ret = -EINVAL;
+ }
+ }
+ if (!ret)
+ pr_info("self-tests: pass\n");
+ return ret;
+}
+
+static void __exit siphash_test_exit(void)
+{
+}
+
+module_init(siphash_test_init);
+module_exit(siphash_test_exit);
+
+MODULE_AUTHOR("Jason A. Donenfeld <[email protected]>");
+MODULE_LICENSE("Dual BSD/GPL");
--
2.11.0
On Sun, Dec 11, 2016 at 7:48 PM, Jason A. Donenfeld <[email protected]> wrote:
> + switch (left) {
> + case 7: b |= ((u64)data[6]) << 48;
> + case 6: b |= ((u64)data[5]) << 40;
> + case 5: b |= ((u64)data[4]) << 32;
> + case 4: b |= ((u64)data[3]) << 24;
> + case 3: b |= ((u64)data[2]) << 16;
> + case 2: b |= ((u64)data[1]) << 8;
> + case 1: b |= ((u64)data[0]); break;
> + case 0: break;
> + }
The above is extremely inefficient. Considering that most kernel data
would be expected to be smallish, that matters (ie the usual benchmark
would not be about hashing megabytes of data, but instead millions of
hashes of small data).
I think this could be rewritten (at least for 64-bit architectures) as
#ifdef CONFIG_DCACHE_WORD_ACCESS
if (left)
b |= le64_to_cpu(load_unaligned_zeropad(data) &
bytemask_from_count(left));
#else
.. do the duff's device thing with the switch() ..
#endif
which should give you basically perfect code generation (ie a single
64-bit load and a byte mask).
Totally untested, just looking at the code and trying to make sense of it.
... and obviously, it requires an actual high-performance use-case to
make any difference.
Linus
On Mon, Dec 12, 2016 at 04:48:17AM +0100, Jason A. Donenfeld wrote:
>
> diff --git a/lib/Makefile b/lib/Makefile
> index 50144a3aeebd..71d398b04a74 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -22,7 +22,8 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
> sha1.o chacha20.o md5.o irq_regs.o argv_split.o \
> flex_proportions.o ratelimit.o show_mem.o \
> is_single_threaded.o plist.o decompress.o kobject_uevent.o \
> - earlycpio.o seq_buf.o nmi_backtrace.o nodemask.o win_minmax.o
> + earlycpio.o seq_buf.o siphash.o \
> + nmi_backtrace.o nodemask.o win_minmax.o
>
> lib-$(CONFIG_MMU) += ioremap.o
> lib-$(CONFIG_SMP) += cpumask.o
> @@ -44,7 +45,7 @@ obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
> obj-y += kstrtox.o
> obj-$(CONFIG_TEST_BPF) += test_bpf.o
> obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
> -obj-$(CONFIG_TEST_HASH) += test_hash.o
> +obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
Maybe add to the help text for CONFIG_TEST_HASH that it now tests siphash too?
> +static inline u64 le64_to_cpuvp(const void *p)
> +{
> + return le64_to_cpup(p);
> +}
This assumes the key and message buffers are aligned to __alignof__(u64).
Unless that's going to be a clearly documented requirement for callers, you
should use get_unaligned_le64() instead. And you can pass a 'u8 *' directly to
get_unaligned_le64(), no need for a helper function.
> + b = (v0 ^ v1) ^ (v2 ^ v3);
> + return (__force u64)cpu_to_le64(b);
> +}
It makes sense for this to return a u64, but that means the cpu_to_le64() is
wrong, since u64 indicates CPU endianness. It should just return 'b'.
> +++ b/lib/test_siphash.c
> @@ -0,0 +1,116 @@
> +/* Test cases for siphash.c
> + *
> + * Copyright (C) 2015-2016 Jason A. Donenfeld <[email protected]>
> + *
> + * This file is provided under a dual BSD/GPLv2 license.
> + *
> + * SipHash: a fast short-input PRF
> + * https://131002.net/siphash/
> + */
> +
> +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
> +
> +#include <linux/siphash.h>
> +#include <linux/kernel.h>
> +#include <linux/string.h>
> +#include <linux/errno.h>
> +#include <linux/module.h>
> +
> +static const u8 test_vectors[64][8] = {
> + { 0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72 },
Can you mention in a comment where the test vectors came from?
> + if (memcmp(&out, test_vectors[i], 8)) {
> + pr_info("self-test %u: FAIL\n", i + 1);
> + ret = -EINVAL;
> + }
If you make the output really be CPU-endian like I'm suggesting then this will
need to be something like:
if (out != get_unaligned_le64(test_vectors[i])) {
Or else make the test vectors be an array of u64.
- Eric
Hey Linus,
On Mon, Dec 12, 2016 at 5:01 AM, Linus Torvalds
<[email protected]> wrote:
> The above is extremely inefficient. Considering that most kernel data
> would be expected to be smallish, that matters (ie the usual benchmark
> would not be about hashing megabytes of data, but instead millions of
> hashes of small data).
>
> I think this could be rewritten (at least for 64-bit architectures) as
>
> #ifdef CONFIG_DCACHE_WORD_ACCESS
>
> if (left)
> b |= le64_to_cpu(load_unaligned_zeropad(data) &
> bytemask_from_count(left));
>
> #else
>
> .. do the duff's device thing with the switch() ..
>
> #endif
>
> which should give you basically perfect code generation (ie a single
> 64-bit load and a byte mask).
I modified the test to hash data of size 0 through 7 repeatedly
100000000 times, and benchmarked that a few times on a Skylake laptop.
The `load_unaligned_zeropad & bytemask_from_count` version was
consistently 7% slower.
I then modified it again to simply hash a 4 byte constant repeatedly
1000000000 times. The `load_unaligned_zeropad & bytemask_from_count`
version was around 6% faster. I tried again with a 7 byte constant and
got more or less a similar result.
Then I tried with a 1 byte constant, and found that the
`load_unaligned_zeropad & bytemask_from_count` version was slower.
So, it would seem that between the `if (left)` and the `switch
(left)`, there's the same number of branches. But for small values of
`left`, the duff's device just has simpler arithmetic, whereas for
large values of `left`, the `load_unaligned_zeropad` prevails. If
micro-optimization is really appealing, one could imagine a hybrid of
the two:
switch (left) {
case 7:
case 6:
case 5:
case 4:
b |= le64_to_cpu(load_unaligned_zeropad(data) &
bytemask_from_count(left));
break;
case 3: b |= ((u64)data[2]) << 16;
case 2: b |= ((u64)data[1]) << 8;
case 1: b |= ((u64)data[0]); break;
case 0: break;
}
But I'm not sure this complication is worth it, and it might be more
likely that the left-over size is 4 bytes most of the time, so we
should just use your trick on platforms that support it.
Jason
Hey Eric,
Lots of good points; thanks for the review. Responses are inline below.
On Mon, Dec 12, 2016 at 6:42 AM, Eric Biggers <[email protected]> wrote:
> Maybe add to the help text for CONFIG_TEST_HASH that it now tests siphash too?
Good call. Will do.
> This assumes the key and message buffers are aligned to __alignof__(u64).
> Unless that's going to be a clearly documented requirement for callers, you
> should use get_unaligned_le64() instead. And you can pass a 'u8 *' directly to
> get_unaligned_le64(), no need for a helper function.
I had thought about that briefly, but just sort of figured most people
were passing in aligned variables... but that's a pretty bad
assumption to make especially for 64-bit alignment. I'll switch to
using the get_unaligned functions.
[As a side note, I wonder if crypto/chacha20_generic.c should be using
the unaligned functions instead too, at least for the iv reading...]
> It makes sense for this to return a u64, but that means the cpu_to_le64() is
> wrong, since u64 indicates CPU endianness. It should just return 'b'.
At first I was very opposed to making this change, since by returning
a value with an explicit byte order, you can cast to u8 and have
uniform indexed byte access across platforms. But of course this
doesn't make any sense, since it's returning a u64, and it makes all
other bitwise operations non-uniform anyway. I checked with JP
(co-creator of siphash, CC'd) and he confirmed your suspicion that it
was just to make the test vector comparison easier and for some
byte-wise uniformity, but that it's not strictly necessary. So, I've
removed that last cpu_to_le64, and I've also refactored those test
vectors to be written as ULL literals, so that a simple == integer
comparison will work across platforms.
> Can you mention in a comment where the test vectors came from?
Sure, will do.
> If you make the output really be CPU-endian like I'm suggesting then this will
> need to be something like:
>
> if (out != get_unaligned_le64(test_vectors[i])) {
>
> Or else make the test vectors be an array of u64.
Yep, I wound up doing that.
Thanks Eric! Will submit a v3 soon if nobody else has comments.
Jason
On Sun, Dec 11, 2016 at 9:48 PM, Jason A. Donenfeld <[email protected]> wrote:
> I modified the test to hash data of size 0 through 7 repeatedly
> 100000000 times, and benchmarked that a few times on a Skylake laptop.
> The `load_unaligned_zeropad & bytemask_from_count` version was
> consistently 7% slower.
>
> I then modified it again to simply hash a 4 byte constant repeatedly
> 1000000000 times. The `load_unaligned_zeropad & bytemask_from_count`
> version was around 6% faster. I tried again with a 7 byte constant and
> got more or less a similar result.
>
> Then I tried with a 1 byte constant, and found that the
> `load_unaligned_zeropad & bytemask_from_count` version was slower.
>
> So, it would seem that between the `if (left)` and the `switch
> (left)`, there's the same number of branches.
Interesting.
For the dcache code (which is where that trick comes from), we used to
have a loop (rather than the duff's device thing), and it performed
badly due to the consistently badly predicted branch of the loop. But
I never compared it against the duff's device version.
I guess you could try to just remove the "if (left)" test entirely, if
it is at least partly the mispredict. It should do the right thing
even with a zero count, and it might schedule the code better. Code
size _should_ be better with the byte mask model (which won't matter
in the hot loop example, since it will all be cached, possibly even in
the uop cache for really tight benchmark loops).
Linus
Hi Linus,
> I guess you could try to just remove the "if (left)" test entirely, if
> it is at least partly the mispredict. It should do the right thing
> even with a zero count, and it might schedule the code better. Code
> size _should_ be better with the byte mask model (which won't matter
> in the hot loop example, since it will all be cached, possibly even in
> the uop cache for really tight benchmark loops).
Originally I had just forgotten the `if (left)`, and had the same
sub-par benchmarks. In the v3 revision that I'm working on at the
moment, I'm using your dcache trick for cases 3,5,6,7 and
short-circuiting cases 1,2,4 to just directly access those bytes as
integers. For the 32-bit case, I do something similar, but built
inside of the duff's device. This should give optimal performance for
the most popular use cases, which involve hashing "some stuff" plus a
leftover u16 (port number?) or u32 (ipv4 addr?).
#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
switch (left) {
case 0: break;
case 1: b |= data[0]; break;
case 2: b |= get_unaligned_le16(data); break;
case 4: b |= get_unaligned_le32(data); break;
default:
b |= le64_to_cpu(load_unaligned_zeropad(data) &
bytemask_from_count(left));
break;
}
#else
switch (left) {
case 7: b |= ((u64)data[6]) << 48;
case 6: b |= ((u64)data[5]) << 40;
case 5: b |= ((u64)data[4]) << 32;
case 4: b |= get_unaligned_le32(data); break;
case 3: b |= ((u64)data[2]) << 16;
case 2: b |= get_unaligned_le16(data); break;
case 1: b |= data[0];
}
#endif
It seems like this might be best of all worlds?
Jason
On Mon, Dec 12, 2016 at 10:44 PM, Jason A. Donenfeld <[email protected]> wrote:
> #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
> switch (left) {
> case 0: break;
> case 1: b |= data[0]; break;
> case 2: b |= get_unaligned_le16(data); break;
> case 4: b |= get_unaligned_le32(data); break;
> default:
> b |= le64_to_cpu(load_unaligned_zeropad(data) &
> bytemask_from_count(left));
> break;
> }
> #else
> switch (left) {
> case 7: b |= ((u64)data[6]) << 48;
> case 6: b |= ((u64)data[5]) << 40;
> case 5: b |= ((u64)data[4]) << 32;
> case 4: b |= get_unaligned_le32(data); break;
> case 3: b |= ((u64)data[2]) << 16;
> case 2: b |= get_unaligned_le16(data); break;
> case 1: b |= data[0];
> }
> #endif
As it turns out, perhaps unsurprisingly, the code generation here is
really not nice, resulting in many branches instead of a computed
jump. I'll submit v3 with just a branch-less load_unaligned_zeropad
for the 64-bit/dcache case and the duff's device for the other case.
SipHash is a 64-bit keyed hash function that is actually a
cryptographically secure PRF, like HMAC. Except SipHash is super fast,
and is meant to be used as a hashtable keyed lookup function.
SipHash isn't just some new trendy hash function. It's been around for a
while, and there really isn't anything that comes remotely close to
being useful in the way SipHash is. With that said, why do we need this?
There are a variety of attacks known as "hashtable poisoning" in which an
attacker forms some data such that the hash of that data will be the
same, and then preceeds to fill up all entries of a hashbucket. This is
a realistic and well-known denial-of-service vector.
Linux developers already seem to be aware that this is an issue, and
various places that use hash tables in, say, a network context, use a
non-cryptographically secure function (usually jhash) and then try to
twiddle with the key on a time basis (or in many cases just do nothing
and hope that nobody notices). While this is an admirable attempt at
solving the problem, it doesn't actually fix it. SipHash fixes it.
(It fixes it in such a sound way that you could even build a stream
cipher out of SipHash that would resist the modern cryptanalysis.)
There are a modicum of places in the kernel that are vulnerable to
hashtable poisoning attacks, either via userspace vectors or network
vectors, and there's not a reliable mechanism inside the kernel at the
moment to fix it. The first step toward fixing these issues is actually
getting a secure primitive into the kernel for developers to use. Then
we can, bit by bit, port things over to it as deemed appropriate.
Dozens of languages are already using this internally for their hash
tables. Some of the BSDs already use this in their kernels. SipHash is
a widely known high-speed solution to a widely known problem, and it's
time we catch-up.
Signed-off-by: Jason A. Donenfeld <[email protected]>
Cc: Jean-Philippe Aumasson <[email protected]>
Cc: Daniel J. Bernstein <[email protected]>
---
Changes from v2->v3:
- The unaligned helpers are now used for reading from u8* arrays.
- Linus' trick with load_unaligned_zeropad has been implemented for
64-bit/dcache platforms.
- Non 64-bit/dcache platforms now use a more optimized duff's device
for shortcutting certain sized left-overs.
- The Kconfig help text for the test now mentions siphash.
- The function now returns a native-endian byte sequence inside a
u64, which is more correct. As well, the tests vectors are now
represented as u64 literals, rather than byte sequences.
- The origin of the test vectors is now inside a comment.
include/linux/siphash.h | 20 +++++++++++++
lib/Kconfig.debug | 6 ++--
lib/Makefile | 5 ++--
lib/siphash.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++++
lib/test_siphash.c | 74 ++++++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 175 insertions(+), 5 deletions(-)
create mode 100644 include/linux/siphash.h
create mode 100644 lib/siphash.c
create mode 100644 lib/test_siphash.c
diff --git a/include/linux/siphash.h b/include/linux/siphash.h
new file mode 100644
index 000000000000..6623b3090645
--- /dev/null
+++ b/include/linux/siphash.h
@@ -0,0 +1,20 @@
+/* Copyright (C) 2016 Jason A. Donenfeld <[email protected]>
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#ifndef _LINUX_SIPHASH_H
+#define _LINUX_SIPHASH_H
+
+#include <linux/types.h>
+
+enum siphash_lengths {
+ SIPHASH24_KEY_LEN = 16
+};
+
+u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]);
+
+#endif /* _LINUX_SIPHASH_H */
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index a6c8db1d62f6..2a1797704b41 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1823,9 +1823,9 @@ config TEST_HASH
tristate "Perform selftest on hash functions"
default n
help
- Enable this option to test the kernel's integer (<linux/hash,h>)
- and string (<linux/stringhash.h>) hash functions on boot
- (or module load).
+ Enable this option to test the kernel's integer (<linux/hash.h>),
+ string (<linux/stringhash.h>), and siphash (<linux/siphash.h>)
+ hash functions on boot (or module load).
This is intended to help people writing architecture-specific
optimized versions. If unsure, say N.
diff --git a/lib/Makefile b/lib/Makefile
index 50144a3aeebd..71d398b04a74 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -22,7 +22,8 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
sha1.o chacha20.o md5.o irq_regs.o argv_split.o \
flex_proportions.o ratelimit.o show_mem.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
- earlycpio.o seq_buf.o nmi_backtrace.o nodemask.o win_minmax.o
+ earlycpio.o seq_buf.o siphash.o \
+ nmi_backtrace.o nodemask.o win_minmax.o
lib-$(CONFIG_MMU) += ioremap.o
lib-$(CONFIG_SMP) += cpumask.o
@@ -44,7 +45,7 @@ obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
obj-y += kstrtox.o
obj-$(CONFIG_TEST_BPF) += test_bpf.o
obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
-obj-$(CONFIG_TEST_HASH) += test_hash.o
+obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
obj-$(CONFIG_TEST_KASAN) += test_kasan.o
obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
obj-$(CONFIG_TEST_LKM) += test_module.o
diff --git a/lib/siphash.c b/lib/siphash.c
new file mode 100644
index 000000000000..b259a3295c50
--- /dev/null
+++ b/lib/siphash.c
@@ -0,0 +1,75 @@
+/* Copyright (C) 2015-2016 Jason A. Donenfeld <[email protected]>
+ * Copyright (C) 2012-2014 Jean-Philippe Aumasson <[email protected]>
+ * Copyright (C) 2012-2014 Daniel J. Bernstein <[email protected]>
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#include <linux/siphash.h>
+#include <linux/kernel.h>
+#include <asm/unaligned.h>
+
+#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
+#include <linux/dcache.h>
+#include <asm/word-at-a-time.h>
+#endif
+
+#define SIPROUND \
+ do { \
+ 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); \
+ } while(0)
+
+u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN])
+{
+ u64 v0 = 0x736f6d6570736575ULL;
+ u64 v1 = 0x646f72616e646f6dULL;
+ u64 v2 = 0x6c7967656e657261ULL;
+ u64 v3 = 0x7465646279746573ULL;
+ u64 b = ((u64)len) << 56;
+ u64 k0 = get_unaligned_le64(key);
+ u64 k1 = get_unaligned_le64(key + sizeof(u64));
+ u64 m;
+ const u8 *end = data + len - (len % sizeof(u64));
+ const u8 left = len & (sizeof(u64) - 1);
+ v3 ^= k1;
+ v2 ^= k0;
+ v1 ^= k1;
+ v0 ^= k0;
+ for (; data != end; data += sizeof(u64)) {
+ m = get_unaligned_le64(data);
+ v3 ^= m;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= m;
+ }
+#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
+ b |= le64_to_cpu(load_unaligned_zeropad(data) & bytemask_from_count(left));
+#else
+ switch (left) {
+ case 7: b |= ((u64)data[6]) << 48;
+ case 6: b |= ((u64)data[5]) << 40;
+ case 5: b |= ((u64)data[4]) << 32;
+ case 4: b |= get_unaligned_le32(data); break;
+ case 3: b |= ((u64)data[2]) << 16;
+ case 2: b |= get_unaligned_le16(data); break;
+ case 1: b |= data[0];
+ }
+#endif
+ v3 ^= b;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= b;
+ v2 ^= 0xff;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
+EXPORT_SYMBOL(siphash24);
diff --git a/lib/test_siphash.c b/lib/test_siphash.c
new file mode 100644
index 000000000000..336298aaa33b
--- /dev/null
+++ b/lib/test_siphash.c
@@ -0,0 +1,74 @@
+/* Test cases for siphash.c
+ *
+ * Copyright (C) 2015-2016 Jason A. Donenfeld <[email protected]>
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/siphash.h>
+#include <linux/kernel.h>
+#include <linux/string.h>
+#include <linux/errno.h>
+#include <linux/module.h>
+
+/* Test vectors taken from official reference source available at:
+ * https://131002.net/siphash/siphash24.c
+ */
+static const u64 test_vectors[64] = {
+ 0x726fdb47dd0e0e31ULL, 0x74f839c593dc67fdULL, 0x0d6c8009d9a94f5aULL,
+ 0x85676696d7fb7e2dULL, 0xcf2794e0277187b7ULL, 0x18765564cd99a68dULL,
+ 0xcbc9466e58fee3ceULL, 0xab0200f58b01d137ULL, 0x93f5f5799a932462ULL,
+ 0x9e0082df0ba9e4b0ULL, 0x7a5dbbc594ddb9f3ULL, 0xf4b32f46226bada7ULL,
+ 0x751e8fbc860ee5fbULL, 0x14ea5627c0843d90ULL, 0xf723ca908e7af2eeULL,
+ 0xa129ca6149be45e5ULL, 0x3f2acc7f57c29bdbULL, 0x699ae9f52cbe4794ULL,
+ 0x4bc1b3f0968dd39cULL, 0xbb6dc91da77961bdULL, 0xbed65cf21aa2ee98ULL,
+ 0xd0f2cbb02e3b67c7ULL, 0x93536795e3a33e88ULL, 0xa80c038ccd5ccec8ULL,
+ 0xb8ad50c6f649af94ULL, 0xbce192de8a85b8eaULL, 0x17d835b85bbb15f3ULL,
+ 0x2f2e6163076bcfadULL, 0xde4daaaca71dc9a5ULL, 0xa6a2506687956571ULL,
+ 0xad87a3535c49ef28ULL, 0x32d892fad841c342ULL, 0x7127512f72f27cceULL,
+ 0xa7f32346f95978e3ULL, 0x12e0b01abb051238ULL, 0x15e034d40fa197aeULL,
+ 0x314dffbe0815a3b4ULL, 0x027990f029623981ULL, 0xcadcd4e59ef40c4dULL,
+ 0x9abfd8766a33735cULL, 0x0e3ea96b5304a7d0ULL, 0xad0c42d6fc585992ULL,
+ 0x187306c89bc215a9ULL, 0xd4a60abcf3792b95ULL, 0xf935451de4f21df2ULL,
+ 0xa9538f0419755787ULL, 0xdb9acddff56ca510ULL, 0xd06c98cd5c0975ebULL,
+ 0xe612a3cb9ecba951ULL, 0xc766e62cfcadaf96ULL, 0xee64435a9752fe72ULL,
+ 0xa192d576b245165aULL, 0x0a8787bf8ecb74b2ULL, 0x81b3e73d20b49b6fULL,
+ 0x7fa8220ba3b2eceaULL, 0x245731c13ca42499ULL, 0xb78dbfaf3a8d83bdULL,
+ 0xea1ad565322a1a0bULL, 0x60e61c23a3795013ULL, 0x6606d7e446282b93ULL,
+ 0x6ca4ecb15c5f91e1ULL, 0x9f626da15c9625f3ULL, 0xe51b38608ef25f57ULL,
+ 0x958a324ceb064572ULL
+};
+
+static int __init siphash_test_init(void)
+{
+ u8 in[64], k[16], i;
+ int ret = 0;
+
+ for (i = 0; i < 16; ++i)
+ k[i] = i;
+ for (i = 0; i < 64; ++i) {
+ in[i] = i;
+ if (siphash24(in, i, k) != test_vectors[i]) {
+ pr_info("self-test %u: FAIL\n", i + 1);
+ ret = -EINVAL;
+ }
+ }
+ if (!ret)
+ pr_info("self-tests: pass\n");
+ return ret;
+}
+
+static void __exit siphash_test_exit(void)
+{
+}
+
+module_init(siphash_test_init);
+module_exit(siphash_test_exit);
+
+MODULE_AUTHOR("Jason A. Donenfeld <[email protected]>");
+MODULE_LICENSE("Dual BSD/GPL");
--
2.11.0
> Dozens of languages are already using this internally for their hash
> tables. Some of the BSDs already use this in their kernels. SipHash is
> a widely known high-speed solution to a widely known problem, and it's
> time we catch-up.
It would be nice if the network code could be converted to use siphash
for the secure sequence numbers. Right now it pulls in a lot of code
for bigger secure hashes just for that, which is a problem for tiny
kernels.
-Andi
On Tue, Dec 13, 2016 at 12:01 AM, Andi Kleen <[email protected]> wrote:
> It would be nice if the network code could be converted to use siphash
> for the secure sequence numbers. Right now it pulls in a lot of code
> for bigger secure hashes just for that, which is a problem for tiny
> kernels.
Indeed this would be a great first candidate. There are lots of places
where MD5 (!!) is pulled in for this sort of thing, when SipHash could
be a faster and leaner replacement (and arguably more secure than
rusty MD5).
On Mon, Dec 12, 2016 at 11:18:32PM +0100, Jason A. Donenfeld wrote:
> + for (; data != end; data += sizeof(u64)) {
> + m = get_unaligned_le64(data);
> + v3 ^= m;
> + SIPROUND;
> + SIPROUND;
> + v0 ^= m;
> + }
> +#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
> + b |= le64_to_cpu(load_unaligned_zeropad(data) & bytemask_from_count(left));
> +#else
Hmm, I don't think you can really do load_unaligned_zeropad() without first
checking for 'left != 0'. The fixup section for load_unaligned_zeropad()
assumes that rounding the pointer down to a word boundary will produce an
address from which an 'unsigned long' can be loaded. But if 'left = 0' and we
happen to be on a page boundary with the next page unmapped, then this will not
be true and the second load will still fault.
Eric
On Mon, Dec 12, 2016 at 3:04 PM, Jason A. Donenfeld <[email protected]> wrote:
>
> Indeed this would be a great first candidate. There are lots of places
> where MD5 (!!) is pulled in for this sort of thing, when SipHash could
> be a faster and leaner replacement (and arguably more secure than
> rusty MD5).
Yeah,. the TCP sequence number md5_transform() cases are likely the
best example of something where siphash might be good. That tends to
be really just a couple words of data (the address and port info) plus
the net_secret[] hash. I think they currently simply just fill in the
fixed-sized 64-byte md5-round area.
I wonder it's worth it to have a special spihash version that does
that same "fixed 64-byte area" thing.
But please talk to the netwotrking people. Maybe that's the proper way
to get this merged?
Linus
On Tue, Dec 13, 2016 at 12:39 AM, Eric Biggers <[email protected]> wrote:
>
> Hmm, I don't think you can really do load_unaligned_zeropad() without first
> checking for 'left != 0'.
Right you are. If the allocation is at the end of a page, the 0-size
case would be entirely outside the page and there's no fixup.
Of course, that never happens in normal code, but DEBUG_PAGE_ALLOC can
trigger it.
Linus
Hi Eric,
On Tue, Dec 13, 2016 at 9:39 AM, Eric Biggers <[email protected]> wrote:
> Hmm, I don't think you can really do load_unaligned_zeropad() without first
> checking for 'left != 0'. The fixup section for load_unaligned_zeropad()
> assumes that rounding the pointer down to a word boundary will produce an
> address from which an 'unsigned long' can be loaded. But if 'left = 0' and we
> happen to be on a page boundary with the next page unmapped, then this will not
> be true and the second load will still fault.
Excellent point. I haven't been able to trigger this in my
experiments, but it doesn't look like there's much to prevent this
from happening. I'll submit a v4 with this as fixed, since there
hasn't been any other code quality issues.
Jason
SipHash is a 64-bit keyed hash function that is actually a
cryptographically secure PRF, like HMAC. Except SipHash is super fast,
and is meant to be used as a hashtable keyed lookup function.
SipHash isn't just some new trendy hash function. It's been around for a
while, and there really isn't anything that comes remotely close to
being useful in the way SipHash is. With that said, why do we need this?
There are a variety of attacks known as "hashtable poisoning" in which an
attacker forms some data such that the hash of that data will be the
same, and then preceeds to fill up all entries of a hashbucket. This is
a realistic and well-known denial-of-service vector.
Linux developers already seem to be aware that this is an issue, and
various places that use hash tables in, say, a network context, use a
non-cryptographically secure function (usually jhash) and then try to
twiddle with the key on a time basis (or in many cases just do nothing
and hope that nobody notices). While this is an admirable attempt at
solving the problem, it doesn't actually fix it. SipHash fixes it.
(It fixes it in such a sound way that you could even build a stream
cipher out of SipHash that would resist the modern cryptanalysis.)
There are a modicum of places in the kernel that are vulnerable to
hashtable poisoning attacks, either via userspace vectors or network
vectors, and there's not a reliable mechanism inside the kernel at the
moment to fix it. The first step toward fixing these issues is actually
getting a secure primitive into the kernel for developers to use. Then
we can, bit by bit, port things over to it as deemed appropriate.
Dozens of languages are already using this internally for their hash
tables. Some of the BSDs already use this in their kernels. SipHash is
a widely known high-speed solution to a widely known problem, and it's
time we catch-up.
Signed-off-by: Jason A. Donenfeld <[email protected]>
Cc: Jean-Philippe Aumasson <[email protected]>
Cc: Daniel J. Bernstein <[email protected]>
---
Changes from v3->v4:
- load_unaligned_zeropad is only called when left is non zero
include/linux/siphash.h | 20 +++++++++++++
lib/Kconfig.debug | 6 ++--
lib/Makefile | 5 ++--
lib/siphash.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++
lib/test_siphash.c | 74 +++++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 176 insertions(+), 5 deletions(-)
create mode 100644 include/linux/siphash.h
create mode 100644 lib/siphash.c
create mode 100644 lib/test_siphash.c
diff --git a/include/linux/siphash.h b/include/linux/siphash.h
new file mode 100644
index 000000000000..6623b3090645
--- /dev/null
+++ b/include/linux/siphash.h
@@ -0,0 +1,20 @@
+/* Copyright (C) 2016 Jason A. Donenfeld <[email protected]>
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#ifndef _LINUX_SIPHASH_H
+#define _LINUX_SIPHASH_H
+
+#include <linux/types.h>
+
+enum siphash_lengths {
+ SIPHASH24_KEY_LEN = 16
+};
+
+u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]);
+
+#endif /* _LINUX_SIPHASH_H */
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index a6c8db1d62f6..2a1797704b41 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1823,9 +1823,9 @@ config TEST_HASH
tristate "Perform selftest on hash functions"
default n
help
- Enable this option to test the kernel's integer (<linux/hash,h>)
- and string (<linux/stringhash.h>) hash functions on boot
- (or module load).
+ Enable this option to test the kernel's integer (<linux/hash.h>),
+ string (<linux/stringhash.h>), and siphash (<linux/siphash.h>)
+ hash functions on boot (or module load).
This is intended to help people writing architecture-specific
optimized versions. If unsure, say N.
diff --git a/lib/Makefile b/lib/Makefile
index 50144a3aeebd..71d398b04a74 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -22,7 +22,8 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
sha1.o chacha20.o md5.o irq_regs.o argv_split.o \
flex_proportions.o ratelimit.o show_mem.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
- earlycpio.o seq_buf.o nmi_backtrace.o nodemask.o win_minmax.o
+ earlycpio.o seq_buf.o siphash.o \
+ nmi_backtrace.o nodemask.o win_minmax.o
lib-$(CONFIG_MMU) += ioremap.o
lib-$(CONFIG_SMP) += cpumask.o
@@ -44,7 +45,7 @@ obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
obj-y += kstrtox.o
obj-$(CONFIG_TEST_BPF) += test_bpf.o
obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
-obj-$(CONFIG_TEST_HASH) += test_hash.o
+obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
obj-$(CONFIG_TEST_KASAN) += test_kasan.o
obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
obj-$(CONFIG_TEST_LKM) += test_module.o
diff --git a/lib/siphash.c b/lib/siphash.c
new file mode 100644
index 000000000000..7b55ad3a7fe9
--- /dev/null
+++ b/lib/siphash.c
@@ -0,0 +1,76 @@
+/* Copyright (C) 2015-2016 Jason A. Donenfeld <[email protected]>
+ * Copyright (C) 2012-2014 Jean-Philippe Aumasson <[email protected]>
+ * Copyright (C) 2012-2014 Daniel J. Bernstein <[email protected]>
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#include <linux/siphash.h>
+#include <linux/kernel.h>
+#include <asm/unaligned.h>
+
+#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
+#include <linux/dcache.h>
+#include <asm/word-at-a-time.h>
+#endif
+
+#define SIPROUND \
+ do { \
+ 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); \
+ } while(0)
+
+u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN])
+{
+ u64 v0 = 0x736f6d6570736575ULL;
+ u64 v1 = 0x646f72616e646f6dULL;
+ u64 v2 = 0x6c7967656e657261ULL;
+ u64 v3 = 0x7465646279746573ULL;
+ u64 b = ((u64)len) << 56;
+ u64 k0 = get_unaligned_le64(key);
+ u64 k1 = get_unaligned_le64(key + sizeof(u64));
+ u64 m;
+ const u8 *end = data + len - (len % sizeof(u64));
+ const u8 left = len & (sizeof(u64) - 1);
+ v3 ^= k1;
+ v2 ^= k0;
+ v1 ^= k1;
+ v0 ^= k0;
+ for (; data != end; data += sizeof(u64)) {
+ m = get_unaligned_le64(data);
+ v3 ^= m;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= m;
+ }
+#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
+ if (left)
+ b |= le64_to_cpu(load_unaligned_zeropad(data) & bytemask_from_count(left));
+#else
+ switch (left) {
+ case 7: b |= ((u64)data[6]) << 48;
+ case 6: b |= ((u64)data[5]) << 40;
+ case 5: b |= ((u64)data[4]) << 32;
+ case 4: b |= get_unaligned_le32(data); break;
+ case 3: b |= ((u64)data[2]) << 16;
+ case 2: b |= get_unaligned_le16(data); break;
+ case 1: b |= data[0];
+ }
+#endif
+ v3 ^= b;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= b;
+ v2 ^= 0xff;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
+EXPORT_SYMBOL(siphash24);
diff --git a/lib/test_siphash.c b/lib/test_siphash.c
new file mode 100644
index 000000000000..336298aaa33b
--- /dev/null
+++ b/lib/test_siphash.c
@@ -0,0 +1,74 @@
+/* Test cases for siphash.c
+ *
+ * Copyright (C) 2015-2016 Jason A. Donenfeld <[email protected]>
+ *
+ * This file is provided under a dual BSD/GPLv2 license.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/siphash.h>
+#include <linux/kernel.h>
+#include <linux/string.h>
+#include <linux/errno.h>
+#include <linux/module.h>
+
+/* Test vectors taken from official reference source available at:
+ * https://131002.net/siphash/siphash24.c
+ */
+static const u64 test_vectors[64] = {
+ 0x726fdb47dd0e0e31ULL, 0x74f839c593dc67fdULL, 0x0d6c8009d9a94f5aULL,
+ 0x85676696d7fb7e2dULL, 0xcf2794e0277187b7ULL, 0x18765564cd99a68dULL,
+ 0xcbc9466e58fee3ceULL, 0xab0200f58b01d137ULL, 0x93f5f5799a932462ULL,
+ 0x9e0082df0ba9e4b0ULL, 0x7a5dbbc594ddb9f3ULL, 0xf4b32f46226bada7ULL,
+ 0x751e8fbc860ee5fbULL, 0x14ea5627c0843d90ULL, 0xf723ca908e7af2eeULL,
+ 0xa129ca6149be45e5ULL, 0x3f2acc7f57c29bdbULL, 0x699ae9f52cbe4794ULL,
+ 0x4bc1b3f0968dd39cULL, 0xbb6dc91da77961bdULL, 0xbed65cf21aa2ee98ULL,
+ 0xd0f2cbb02e3b67c7ULL, 0x93536795e3a33e88ULL, 0xa80c038ccd5ccec8ULL,
+ 0xb8ad50c6f649af94ULL, 0xbce192de8a85b8eaULL, 0x17d835b85bbb15f3ULL,
+ 0x2f2e6163076bcfadULL, 0xde4daaaca71dc9a5ULL, 0xa6a2506687956571ULL,
+ 0xad87a3535c49ef28ULL, 0x32d892fad841c342ULL, 0x7127512f72f27cceULL,
+ 0xa7f32346f95978e3ULL, 0x12e0b01abb051238ULL, 0x15e034d40fa197aeULL,
+ 0x314dffbe0815a3b4ULL, 0x027990f029623981ULL, 0xcadcd4e59ef40c4dULL,
+ 0x9abfd8766a33735cULL, 0x0e3ea96b5304a7d0ULL, 0xad0c42d6fc585992ULL,
+ 0x187306c89bc215a9ULL, 0xd4a60abcf3792b95ULL, 0xf935451de4f21df2ULL,
+ 0xa9538f0419755787ULL, 0xdb9acddff56ca510ULL, 0xd06c98cd5c0975ebULL,
+ 0xe612a3cb9ecba951ULL, 0xc766e62cfcadaf96ULL, 0xee64435a9752fe72ULL,
+ 0xa192d576b245165aULL, 0x0a8787bf8ecb74b2ULL, 0x81b3e73d20b49b6fULL,
+ 0x7fa8220ba3b2eceaULL, 0x245731c13ca42499ULL, 0xb78dbfaf3a8d83bdULL,
+ 0xea1ad565322a1a0bULL, 0x60e61c23a3795013ULL, 0x6606d7e446282b93ULL,
+ 0x6ca4ecb15c5f91e1ULL, 0x9f626da15c9625f3ULL, 0xe51b38608ef25f57ULL,
+ 0x958a324ceb064572ULL
+};
+
+static int __init siphash_test_init(void)
+{
+ u8 in[64], k[16], i;
+ int ret = 0;
+
+ for (i = 0; i < 16; ++i)
+ k[i] = i;
+ for (i = 0; i < 64; ++i) {
+ in[i] = i;
+ if (siphash24(in, i, k) != test_vectors[i]) {
+ pr_info("self-test %u: FAIL\n", i + 1);
+ ret = -EINVAL;
+ }
+ }
+ if (!ret)
+ pr_info("self-tests: pass\n");
+ return ret;
+}
+
+static void __exit siphash_test_exit(void)
+{
+}
+
+module_init(siphash_test_init);
+module_exit(siphash_test_exit);
+
+MODULE_AUTHOR("Jason A. Donenfeld <[email protected]>");
+MODULE_LICENSE("Dual BSD/GPL");
--
2.11.0
Hi Linus,
On Tue, Dec 13, 2016 at 8:25 PM, Linus Torvalds
<[email protected]> wrote:
> Yeah,. the TCP sequence number md5_transform() cases are likely the
> best example of something where siphash might be good. That tends to
> be really just a couple words of data (the address and port info) plus
> the net_secret[] hash. I think they currently simply just fill in the
> fixed-sized 64-byte md5-round area.
>
> I wonder it's worth it to have a special spihash version that does
> that same "fixed 64-byte area" thing.
What happens in MD5 the hash function is that it first initializes its
initial 128-bit hash to a magic constant, and then reads 64 bytes at a
time from the input and calls md5_transform on that, which each time
manipulates that 128-bit value from its starting value. At the end of
the input, some special padding is applied for small final blocks,
some finalization, and then the resultant hash is whatever that
128-bit value is at the end of the process.
What the tcp stack does with secure_tcp_sequence_number function in
net/core/secure_seq.c, and a variety of other places, is to just
supply that 128-bit initial value not with the magic constant, but
instead with saddr||daddr||sport||dport||net_secret[15] and then calls
md5_transform on the 64-byte long term secret random value
(net_secret). From the resultant 128-bit value, they take the first
32-bits. In addition to being rather heavy weight, this strikes me as
cryptographically a bit dubious too. But that's where your "fixed
64-byte area" notion comes from.
Siphash makes things a lot more simple than that. Since siphash is a
PRF and not a mere hash function, it takes an explicit secret key
parameter, which would be net_secret, some input data, which would be
saddr||daddr||sport||dport, and then spits out a 64-bit number, 32
bits of which would be used as the sequence number.
seq_num = seq_scale(siphash24(saddr||daddr||sport||dport, net_secret));
A lot simpler, faster, and actually secure.
> But please talk to the netwotrking people. Maybe that's the proper way
> to get this merged?
I had hoped to do it the lazy way, and just have it just wind up in
lib/. But I suppose you and Greg are of course right, and I should
submit this with a real usage. So I'll do that, and resubmit in
another thread as a series to LKML and netdev.
Thanks for your feedback!
Jason