* [PATCH v2 1/4] siphash: add cryptographically secure hashtable function @ 2016-12-14 3:59 Jason A. Donenfeld 2016-12-14 3:59 ` [PATCH v2 2/4] siphash: add convenience functions for jhash converts Jason A. Donenfeld ` (5 more replies) 0 siblings, 6 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 3:59 UTC (permalink / raw) To: Netdev, kernel-hardening, LKML, linux-crypto Cc: Jason A. Donenfeld, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers 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 <Jason@zx2c4.com> Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> Cc: Daniel J. Bernstein <djb@cr.yp.to> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Eric Biggers <ebiggers3@gmail.com> --- Changes from v1->v2: - None in this patch, but see elsewhere in series. 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 <Jason@zx2c4.com> + * + * 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 e6327d102184..32bbf689fc46 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1843,9 +1843,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 <Jason@zx2c4.com> + * Copyright (C) 2012-2014 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> + * Copyright (C) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to> + * + * 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 <Jason@zx2c4.com> + * + * 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 <Jason@zx2c4.com>"); +MODULE_LICENSE("Dual BSD/GPL"); -- 2.11.0 ^ permalink raw reply related [flat|nested] 70+ messages in thread
* [PATCH v2 2/4] siphash: add convenience functions for jhash converts 2016-12-14 3:59 [PATCH v2 1/4] siphash: add cryptographically secure hashtable function Jason A. Donenfeld @ 2016-12-14 3:59 ` Jason A. Donenfeld 2016-12-14 3:59 ` [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform Jason A. Donenfeld ` (4 subsequent siblings) 5 siblings, 0 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 3:59 UTC (permalink / raw) To: Netdev, kernel-hardening, LKML, linux-crypto; +Cc: Jason A. Donenfeld Many jhash users currently rely on the Nwords functions. In order to make transitions to siphash fit something people already know about, we provide analog functions here. This also winds up being nice for the networking stack, where hashing 32-bit fields is common. Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> --- Changes from v1->v2: - None in this patch, but see elsewhere in series. include/linux/siphash.h | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) diff --git a/include/linux/siphash.h b/include/linux/siphash.h index 6623b3090645..1391054c4c29 100644 --- a/include/linux/siphash.h +++ b/include/linux/siphash.h @@ -17,4 +17,37 @@ enum siphash_lengths { u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]); +static inline u64 siphash24_1word(const u32 a, const u8 key[SIPHASH24_KEY_LEN]) +{ + return siphash24((u8 *)&a, sizeof(a), key); +} + +static inline u64 siphash24_2words(const u32 a, const u32 b, const u8 key[SIPHASH24_KEY_LEN]) +{ + const struct { + u32 a; + u32 b; + } __packed combined = { + .a = a, + .b = b + }; + + return siphash24((const u8 *)&combined, sizeof(combined), key); +} + +static inline u64 siphash24_3words(const u32 a, const u32 b, const u32 c, const u8 key[SIPHASH24_KEY_LEN]) +{ + const struct { + u32 a; + u32 b; + u32 c; + } __packed combined = { + .a = a, + .b = b, + .c = c + }; + + return siphash24((const u8 *)&combined, sizeof(combined), key); +} + #endif /* _LINUX_SIPHASH_H */ -- 2.11.0 ^ permalink raw reply related [flat|nested] 70+ messages in thread
* [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 3:59 [PATCH v2 1/4] siphash: add cryptographically secure hashtable function Jason A. Donenfeld 2016-12-14 3:59 ` [PATCH v2 2/4] siphash: add convenience functions for jhash converts Jason A. Donenfeld @ 2016-12-14 3:59 ` Jason A. Donenfeld 2016-12-14 12:53 ` Jason A. Donenfeld 2016-12-14 3:59 ` [PATCH v2 4/4] random: use siphash24 instead of md5 for get_random_int/long Jason A. Donenfeld ` (3 subsequent siblings) 5 siblings, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 3:59 UTC (permalink / raw) To: Netdev, kernel-hardening, LKML, linux-crypto Cc: Jason A. Donenfeld, Andi Kleen This gives a clear speed and security improvement. Siphash is both faster and is more solid crypto than the aging MD5. Rather than manually filling MD5 buffers, we simply create a layout by a simple anonymous struct, for which gcc generates rather efficient code. Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> Cc: Andi Kleen <ak@linux.intel.com> --- Changes from v1->v2: - Rebased on the latest 4.10, and now uses top 32-bits of siphash for the optional ts value. net/core/secure_seq.c | 160 +++++++++++++++++++++++++------------------------- 1 file changed, 79 insertions(+), 81 deletions(-) diff --git a/net/core/secure_seq.c b/net/core/secure_seq.c index 88a8e429fc3e..abadc79cd5d3 100644 --- a/net/core/secure_seq.c +++ b/net/core/secure_seq.c @@ -1,3 +1,5 @@ +/* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. */ + #include <linux/kernel.h> #include <linux/init.h> #include <linux/cryptohash.h> @@ -8,14 +10,14 @@ #include <linux/ktime.h> #include <linux/string.h> #include <linux/net.h> - +#include <linux/siphash.h> #include <net/secure_seq.h> #if IS_ENABLED(CONFIG_IPV6) || IS_ENABLED(CONFIG_INET) +#include <linux/in6.h> #include <net/tcp.h> -#define NET_SECRET_SIZE (MD5_MESSAGE_BYTES / 4) -static u32 net_secret[NET_SECRET_SIZE] ____cacheline_aligned; +static u8 net_secret[SIPHASH24_KEY_LEN]; static __always_inline void net_secret_init(void) { @@ -44,44 +46,39 @@ static u32 seq_scale(u32 seq) u32 secure_tcpv6_sequence_number(const __be32 *saddr, const __be32 *daddr, __be16 sport, __be16 dport, u32 *tsoff) { - u32 secret[MD5_MESSAGE_BYTES / 4]; - u32 hash[MD5_DIGEST_WORDS]; - u32 i; - + const struct { + struct in6_addr saddr; + struct in6_addr daddr; + __be16 sport; + __be16 dport; + } __packed combined = { + .saddr = *(struct in6_addr *)saddr, + .daddr = *(struct in6_addr *)daddr, + .sport = sport, + .dport = dport + }; + u64 hash; net_secret_init(); - memcpy(hash, saddr, 16); - for (i = 0; i < 4; i++) - secret[i] = net_secret[i] + (__force u32)daddr[i]; - secret[4] = net_secret[4] + - (((__force u16)sport << 16) + (__force u16)dport); - for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++) - secret[i] = net_secret[i]; - - md5_transform(hash, secret); - - *tsoff = sysctl_tcp_timestamps == 1 ? hash[1] : 0; - return seq_scale(hash[0]); + hash = siphash24((const u8 *)&combined, sizeof(combined), net_secret); + *tsoff = sysctl_tcp_timestamps == 1 ? (hash >> 32) : 0; + return seq_scale(hash); } EXPORT_SYMBOL(secure_tcpv6_sequence_number); u32 secure_ipv6_port_ephemeral(const __be32 *saddr, const __be32 *daddr, __be16 dport) { - u32 secret[MD5_MESSAGE_BYTES / 4]; - u32 hash[MD5_DIGEST_WORDS]; - u32 i; - + const struct { + struct in6_addr saddr; + struct in6_addr daddr; + __be16 dport; + } __packed combined = { + .saddr = *(struct in6_addr *)saddr, + .daddr = *(struct in6_addr *)daddr, + .dport = dport + }; net_secret_init(); - memcpy(hash, saddr, 16); - for (i = 0; i < 4; i++) - secret[i] = net_secret[i] + (__force u32) daddr[i]; - secret[4] = net_secret[4] + (__force u32)dport; - for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++) - secret[i] = net_secret[i]; - - md5_transform(hash, secret); - - return hash[0]; + return siphash24((const u8 *)&combined, sizeof(combined), net_secret); } EXPORT_SYMBOL(secure_ipv6_port_ephemeral); #endif @@ -91,33 +88,37 @@ EXPORT_SYMBOL(secure_ipv6_port_ephemeral); u32 secure_tcp_sequence_number(__be32 saddr, __be32 daddr, __be16 sport, __be16 dport, u32 *tsoff) { - u32 hash[MD5_DIGEST_WORDS]; - + const struct { + __be32 saddr; + __be32 daddr; + __be16 sport; + __be16 dport; + } __packed combined = { + .saddr = saddr, + .daddr = daddr, + .sport = sport, + .dport = dport + }; + u64 hash; net_secret_init(); - hash[0] = (__force u32)saddr; - hash[1] = (__force u32)daddr; - hash[2] = ((__force u16)sport << 16) + (__force u16)dport; - hash[3] = net_secret[15]; - - md5_transform(hash, net_secret); - - *tsoff = sysctl_tcp_timestamps == 1 ? hash[1] : 0; - return seq_scale(hash[0]); + hash = siphash24((const u8 *)&combined, sizeof(combined), net_secret); + *tsoff = sysctl_tcp_timestamps == 1 ? (hash >> 32) : 0; + return seq_scale(hash); } u32 secure_ipv4_port_ephemeral(__be32 saddr, __be32 daddr, __be16 dport) { - u32 hash[MD5_DIGEST_WORDS]; - + const struct { + __be32 saddr; + __be32 daddr; + __be16 dport; + } __packed combined = { + .saddr = saddr, + .daddr = daddr, + .dport = dport + }; net_secret_init(); - hash[0] = (__force u32)saddr; - hash[1] = (__force u32)daddr; - hash[2] = (__force u32)dport ^ net_secret[14]; - hash[3] = net_secret[15]; - - md5_transform(hash, net_secret); - - return hash[0]; + return seq_scale(siphash24((const u8 *)&combined, sizeof(combined), net_secret)); } EXPORT_SYMBOL_GPL(secure_ipv4_port_ephemeral); #endif @@ -126,21 +127,22 @@ EXPORT_SYMBOL_GPL(secure_ipv4_port_ephemeral); u64 secure_dccp_sequence_number(__be32 saddr, __be32 daddr, __be16 sport, __be16 dport) { - u32 hash[MD5_DIGEST_WORDS]; + const struct { + __be32 saddr; + __be32 daddr; + __be16 sport; + __be16 dport; + } __packed combined = { + .saddr = saddr, + .daddr = daddr, + .sport = sport, + .dport = dport + }; u64 seq; - net_secret_init(); - hash[0] = (__force u32)saddr; - hash[1] = (__force u32)daddr; - hash[2] = ((__force u16)sport << 16) + (__force u16)dport; - hash[3] = net_secret[15]; - - md5_transform(hash, net_secret); - - seq = hash[0] | (((u64)hash[1]) << 32); + seq = siphash24((const u8 *)&combined, sizeof(combined), net_secret); seq += ktime_get_real_ns(); seq &= (1ull << 48) - 1; - return seq; } EXPORT_SYMBOL(secure_dccp_sequence_number); @@ -149,26 +151,22 @@ EXPORT_SYMBOL(secure_dccp_sequence_number); u64 secure_dccpv6_sequence_number(__be32 *saddr, __be32 *daddr, __be16 sport, __be16 dport) { - u32 secret[MD5_MESSAGE_BYTES / 4]; - u32 hash[MD5_DIGEST_WORDS]; + const struct { + struct in6_addr saddr; + struct in6_addr daddr; + __be16 sport; + __be16 dport; + } __packed combined = { + .saddr = *(struct in6_addr *)saddr, + .daddr = *(struct in6_addr *)daddr, + .sport = sport, + .dport = dport + }; u64 seq; - u32 i; - net_secret_init(); - memcpy(hash, saddr, 16); - for (i = 0; i < 4; i++) - secret[i] = net_secret[i] + (__force u32)daddr[i]; - secret[4] = net_secret[4] + - (((__force u16)sport << 16) + (__force u16)dport); - for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++) - secret[i] = net_secret[i]; - - md5_transform(hash, secret); - - seq = hash[0] | (((u64)hash[1]) << 32); + seq = siphash24((const u8 *)&combined, sizeof(combined), net_secret); seq += ktime_get_real_ns(); seq &= (1ull << 48) - 1; - return seq; } EXPORT_SYMBOL(secure_dccpv6_sequence_number); -- 2.11.0 ^ permalink raw reply related [flat|nested] 70+ messages in thread
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 3:59 ` [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform Jason A. Donenfeld @ 2016-12-14 12:53 ` Jason A. Donenfeld 2016-12-14 13:16 ` Hannes Frederic Sowa ` (2 more replies) 0 siblings, 3 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 12:53 UTC (permalink / raw) To: David Laight Cc: Netdev, kernel-hardening, Andi Kleen, LKML, Linux Crypto Mailing List Hi David, On Wed, Dec 14, 2016 at 10:51 AM, David Laight <David.Laight@aculab.com> wrote: > From: Jason A. Donenfeld >> Sent: 14 December 2016 00:17 >> This gives a clear speed and security improvement. Rather than manually >> filling MD5 buffers, we simply create a layout by a simple anonymous >> struct, for which gcc generates rather efficient code. > ... >> + const struct { >> + struct in6_addr saddr; >> + struct in6_addr daddr; >> + __be16 sport; >> + __be16 dport; >> + } __packed combined = { >> + .saddr = *(struct in6_addr *)saddr, >> + .daddr = *(struct in6_addr *)daddr, >> + .sport = sport, >> + .dport = dport >> + }; > > You need to look at the effect of marking this (and the other) > structures 'packed' on architectures like sparc64. In all current uses of __packed in the code, I think the impact is precisely zero, because all structures have members in descending order of size, with each member being a perfect multiple of the one below it. The __packed is therefore just there for safety, in case somebody comes in and screws everything up by sticking a u8 in between. In that case, it wouldn't be desirable to hash the structure padding bits. In the worst case, I don't believe the impact would be worse than a byte-by-byte memcpy, which is what the old code did. But anyway, these structures are already naturally packed anyway, so the present impact is nil. Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 12:53 ` Jason A. Donenfeld @ 2016-12-14 13:16 ` Hannes Frederic Sowa 2016-12-14 13:44 ` Jason A. Donenfeld 2016-12-14 17:56 ` David Miller 2016-12-14 20:12 ` Tom Herbert 2 siblings, 1 reply; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-14 13:16 UTC (permalink / raw) To: Jason A. Donenfeld, David Laight Cc: Netdev, kernel-hardening, Andi Kleen, LKML, Linux Crypto Mailing List On 14.12.2016 13:53, Jason A. Donenfeld wrote: > Hi David, > > On Wed, Dec 14, 2016 at 10:51 AM, David Laight <David.Laight@aculab.com> wrote: >> From: Jason A. Donenfeld >>> Sent: 14 December 2016 00:17 >>> This gives a clear speed and security improvement. Rather than manually >>> filling MD5 buffers, we simply create a layout by a simple anonymous >>> struct, for which gcc generates rather efficient code. >> ... >>> + const struct { >>> + struct in6_addr saddr; >>> + struct in6_addr daddr; >>> + __be16 sport; >>> + __be16 dport; >>> + } __packed combined = { >>> + .saddr = *(struct in6_addr *)saddr, >>> + .daddr = *(struct in6_addr *)daddr, >>> + .sport = sport, >>> + .dport = dport >>> + }; >> >> You need to look at the effect of marking this (and the other) >> structures 'packed' on architectures like sparc64. > > In all current uses of __packed in the code, I think the impact is > precisely zero, because all structures have members in descending > order of size, with each member being a perfect multiple of the one > below it. The __packed is therefore just there for safety, in case > somebody comes in and screws everything up by sticking a u8 in > between. In that case, it wouldn't be desirable to hash the structure > padding bits. In the worst case, I don't believe the impact would be > worse than a byte-by-byte memcpy, which is what the old code did. But > anyway, these structures are already naturally packed anyway, so the > present impact is nil. __packed not only removes all padding of the struct but also changes the alignment assumptions for the whole struct itself. The rule, the struct is aligned by its maximum alignment of a member is no longer true. That said, the code accessing this struct will change (not on archs that can deal efficiently with unaligned access, but on others). A proper test for not introducing padding is to use something with BUILD_BUG_ON. Also gcc also clears the padding of the struct, so padding shouldn't be that bad in there (it is better than byte access on mips). Btw. I think gcc7 gets support for store merging optimization. Bye, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 13:16 ` Hannes Frederic Sowa @ 2016-12-14 13:44 ` Jason A. Donenfeld 2016-12-14 14:47 ` David Laight 0 siblings, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 13:44 UTC (permalink / raw) To: Hannes Frederic Sowa Cc: David Laight, Netdev, kernel-hardening, Andi Kleen, LKML, Linux Crypto Mailing List Hi Hannes, Thanks for the feedback. > __packed not only removes all padding of the struct but also changes the > alignment assumptions for the whole struct itself. The rule, the struct > is aligned by its maximum alignment of a member is no longer true. That > said, the code accessing this struct will change (not on archs that can > deal efficiently with unaligned access, but on others). That's interesting. There currently aren't any alignment requirements in siphash because we use the unaligned helper functions, but as David pointed out in another thread, maybe that too should change. In that case, we'd have an aligned-only version of the function that requires 8-byte aligned input. Perhaps the best way to go about that would be to just mark the struct as __packed __aligned(8). Or, I guess, since 64-bit accesses gets split into two on 32-bit, that'd be best descried as __packed __aligned(sizeof(long)). Would that be an acceptable solution? Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* RE: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 13:44 ` Jason A. Donenfeld @ 2016-12-14 14:47 ` David Laight 2016-12-14 17:49 ` Jason A. Donenfeld 0 siblings, 1 reply; 70+ messages in thread From: David Laight @ 2016-12-14 14:47 UTC (permalink / raw) To: 'Jason A. Donenfeld', Hannes Frederic Sowa Cc: Netdev, kernel-hardening, Andi Kleen, LKML, Linux Crypto Mailing List From: Jason A. Donenfeld > Sent: 14 December 2016 13:44 > To: Hannes Frederic Sowa > > __packed not only removes all padding of the struct but also changes the > > alignment assumptions for the whole struct itself. The rule, the struct > > is aligned by its maximum alignment of a member is no longer true. That > > said, the code accessing this struct will change (not on archs that can > > deal efficiently with unaligned access, but on others). > > That's interesting. There currently aren't any alignment requirements > in siphash because we use the unaligned helper functions, but as David > pointed out in another thread, maybe that too should change. In that > case, we'd have an aligned-only version of the function that requires > 8-byte aligned input. Perhaps the best way to go about that would be > to just mark the struct as __packed __aligned(8). Or, I guess, since > 64-bit accesses gets split into two on 32-bit, that'd be best descried > as __packed __aligned(sizeof(long)). Would that be an acceptable > solution? Just remove the __packed and ensure that the structure is 'nice'. This includes ensuring there is no 'tail padding'. In some cases you'll need to put the port number into a 32bit field. I'd also require that the key be aligned. It probably ought to be a named structure type with two 64bit members (or with an array member that has two elements). David ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 14:47 ` David Laight @ 2016-12-14 17:49 ` Jason A. Donenfeld 0 siblings, 0 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 17:49 UTC (permalink / raw) To: David Laight Cc: Hannes Frederic Sowa, Netdev, kernel-hardening, Andi Kleen, LKML, Linux Crypto Mailing List On Wed, Dec 14, 2016 at 3:47 PM, David Laight <David.Laight@aculab.com> wrote: > Just remove the __packed and ensure that the structure is 'nice'. > This includes ensuring there is no 'tail padding'. > In some cases you'll need to put the port number into a 32bit field. I'd rather not. There's no point in wasting extra cycles on hashing useless data, just for some particular syntactic improvement. __packed __aligned(8) will do what we want perfectly, I think. > I'd also require that the key be aligned. Yep, I'll certainly do this for the siphash24_aligned version in the v3. ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 12:53 ` Jason A. Donenfeld 2016-12-14 13:16 ` Hannes Frederic Sowa @ 2016-12-14 17:56 ` David Miller 2016-12-14 18:06 ` Jason A. Donenfeld 2016-12-14 20:12 ` Tom Herbert 2 siblings, 1 reply; 70+ messages in thread From: David Miller @ 2016-12-14 17:56 UTC (permalink / raw) To: Jason Cc: David.Laight, netdev, kernel-hardening, ak, linux-kernel, linux-crypto From: "Jason A. Donenfeld" <Jason@zx2c4.com> Date: Wed, 14 Dec 2016 13:53:10 +0100 > In all current uses of __packed in the code, I think the impact is > precisely zero, because all structures have members in descending > order of size, with each member being a perfect multiple of the one > below it. The __packed is therefore just there for safety, in case > somebody comes in and screws everything up by sticking a u8 in > between. Just marking the structure __packed, whether necessary or not, makes the compiler assume that the members are not aligned and causes byte-by-byte accesses to be performed for words. Never, _ever_, use __packed unless absolutely necessary, it pessimizes the code on cpus that require proper alignment of types. ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 17:56 ` David Miller @ 2016-12-14 18:06 ` Jason A. Donenfeld 2016-12-14 19:22 ` Hannes Frederic Sowa 0 siblings, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 18:06 UTC (permalink / raw) To: David Miller Cc: David Laight, Netdev, kernel-hardening, Andi Kleen, LKML, Linux Crypto Mailing List Hi David, On Wed, Dec 14, 2016 at 6:56 PM, David Miller <davem@davemloft.net> wrote: > Just marking the structure __packed, whether necessary or not, makes > the compiler assume that the members are not aligned and causes > byte-by-byte accesses to be performed for words. > Never, _ever_, use __packed unless absolutely necessary, it pessimizes > the code on cpus that require proper alignment of types. Oh, jimminy cricket, I did not realize that it made assignments byte-by-byte *always*. So what options am I left with? What immediately comes to mind are: 1) struct { u64 a; u32 b; u32 c; u16 d; u8 end[]; } a = { .a = a, .b = b, .c = c, .d = d }; siphash24(&a, offsetof(typeof(a), end), key); 2) u8 bytes[sizeof(u64) + sizeof(u32) * 2 + sizeof(u16)]; *(u64 *)&bytes[0] = a; *(u32 *)&bytes[sizeof(u64)] = b; *(u32 *)&bytes[sizeof(u64) + sizeof(u32)] = c; *(u16 *)&bytes[sizeof(u64) + sizeof(u32) * 2] = d; siphash24(bytes, sizeof(bytes), key); Personally I find (1) a bit neater than (2). What's your opinion? Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 18:06 ` Jason A. Donenfeld @ 2016-12-14 19:22 ` Hannes Frederic Sowa 2016-12-14 19:38 ` Jason A. Donenfeld 0 siblings, 1 reply; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-14 19:22 UTC (permalink / raw) To: Jason A. Donenfeld, David Miller Cc: David Laight, Netdev, kernel-hardening, Andi Kleen, LKML, Linux Crypto Mailing List On 14.12.2016 19:06, Jason A. Donenfeld wrote: > Hi David, > > On Wed, Dec 14, 2016 at 6:56 PM, David Miller <davem@davemloft.net> wrote: >> Just marking the structure __packed, whether necessary or not, makes >> the compiler assume that the members are not aligned and causes >> byte-by-byte accesses to be performed for words. >> Never, _ever_, use __packed unless absolutely necessary, it pessimizes >> the code on cpus that require proper alignment of types. > > Oh, jimminy cricket, I did not realize that it made assignments > byte-by-byte *always*. So what options am I left with? What > immediately comes to mind are: > > 1) > > struct { > u64 a; > u32 b; > u32 c; > u16 d; > u8 end[]; I don't think this helps. Did you test it? I don't see reason why padding could be left out between `d' and `end' because of the flexible array member? Bye, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 19:22 ` Hannes Frederic Sowa @ 2016-12-14 19:38 ` Jason A. Donenfeld 2016-12-14 20:27 ` Hannes Frederic Sowa 0 siblings, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 19:38 UTC (permalink / raw) To: Hannes Frederic Sowa Cc: David Miller, David Laight, Netdev, kernel-hardening, Andi Kleen, LKML, Linux Crypto Mailing List Hi Hannes, On Wed, Dec 14, 2016 at 8:22 PM, Hannes Frederic Sowa <hannes@stressinduktion.org> wrote: > I don't think this helps. Did you test it? I don't see reason why > padding could be left out between `d' and `end' because of the flexible > array member? Because the type u8 doesn't require any alignment requirements, it can nestle right up there cozy with the u16: zx2c4@thinkpad ~ $ cat a.c #include <stdint.h> #include <stdio.h> #include <stddef.h> int main() { struct { uint64_t a; uint32_t b; uint32_t c; uint16_t d; char x[]; } a; printf("%zu\n", sizeof(a)); printf("%zu\n", offsetof(typeof(a), x)); return 0; } zx2c4@thinkpad ~ $ gcc a.c zx2c4@thinkpad ~ $ ./a.out 24 18 Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 19:38 ` Jason A. Donenfeld @ 2016-12-14 20:27 ` Hannes Frederic Sowa 0 siblings, 0 replies; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-14 20:27 UTC (permalink / raw) To: Jason A. Donenfeld Cc: David Miller, David Laight, Netdev, kernel-hardening, Andi Kleen, LKML, Linux Crypto Mailing List Hey Jason, On 14.12.2016 20:38, Jason A. Donenfeld wrote: > On Wed, Dec 14, 2016 at 8:22 PM, Hannes Frederic Sowa > <hannes@stressinduktion.org> wrote: >> I don't think this helps. Did you test it? I don't see reason why >> padding could be left out between `d' and `end' because of the flexible >> array member? > > Because the type u8 doesn't require any alignment requirements, it can > nestle right up there cozy with the u16: > > zx2c4@thinkpad ~ $ cat a.c > #include <stdint.h> > #include <stdio.h> > #include <stddef.h> > int main() > { > struct { > uint64_t a; > uint32_t b; > uint32_t c; > uint16_t d; > char x[]; > } a; > printf("%zu\n", sizeof(a)); > printf("%zu\n", offsetof(typeof(a), x)); > return 0; > } > zx2c4@thinkpad ~ $ gcc a.c > zx2c4@thinkpad ~ $ ./a.out > 24 > 18 Sorry, I misread the patch. You are using offsetof. In this case remove the char x[] and just use offsetofend because it is misleading otherwise. Should work like that though. What I don't really understand is that the addition of this complexity actually reduces the performance, as you have to take the "if (left)" branch during hashing and causes you to make a load_unaligned_zeropad. Bye, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 12:53 ` Jason A. Donenfeld 2016-12-14 13:16 ` Hannes Frederic Sowa 2016-12-14 17:56 ` David Miller @ 2016-12-14 20:12 ` Tom Herbert 2016-12-14 21:01 ` Jason A. Donenfeld 2 siblings, 1 reply; 70+ messages in thread From: Tom Herbert @ 2016-12-14 20:12 UTC (permalink / raw) To: Jason A. Donenfeld Cc: David Laight, Netdev, kernel-hardening, Andi Kleen, LKML, Linux Crypto Mailing List On Wed, Dec 14, 2016 at 4:53 AM, Jason A. Donenfeld <Jason@zx2c4.com> wrote: > Hi David, > > On Wed, Dec 14, 2016 at 10:51 AM, David Laight <David.Laight@aculab.com> wrote: >> From: Jason A. Donenfeld >>> Sent: 14 December 2016 00:17 >>> This gives a clear speed and security improvement. Rather than manually >>> filling MD5 buffers, we simply create a layout by a simple anonymous >>> struct, for which gcc generates rather efficient code. >> ... >>> + const struct { >>> + struct in6_addr saddr; >>> + struct in6_addr daddr; >>> + __be16 sport; >>> + __be16 dport; >>> + } __packed combined = { >>> + .saddr = *(struct in6_addr *)saddr, >>> + .daddr = *(struct in6_addr *)daddr, >>> + .sport = sport, >>> + .dport = dport >>> + }; >> >> You need to look at the effect of marking this (and the other) >> structures 'packed' on architectures like sparc64. > > In all current uses of __packed in the code, I think the impact is > precisely zero, because all structures have members in descending > order of size, with each member being a perfect multiple of the one > below it. The __packed is therefore just there for safety, in case > somebody comes in and screws everything up by sticking a u8 in > between. In that case, it wouldn't be desirable to hash the structure > padding bits. In the worst case, I don't believe the impact would be > worse than a byte-by-byte memcpy, which is what the old code did. But > anyway, these structures are already naturally packed anyway, so the > present impact is nil. > If you pad the data structure to 64 bits then we can call the version of siphash that only deals in 64 bit words. Writing a zero in the padding will be cheaper than dealing with odd lengths in siphash24. Tom > Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform 2016-12-14 20:12 ` Tom Herbert @ 2016-12-14 21:01 ` Jason A. Donenfeld 0 siblings, 0 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 21:01 UTC (permalink / raw) To: Tom Herbert Cc: David Laight, Netdev, kernel-hardening, Andi Kleen, LKML, Linux Crypto Mailing List On Wed, Dec 14, 2016 at 9:12 PM, Tom Herbert <tom@herbertland.com> wrote: > If you pad the data structure to 64 bits then we can call the version > of siphash that only deals in 64 bit words. Writing a zero in the > padding will be cheaper than dealing with odd lengths in siphash24. On Wed, Dec 14, 2016 at 9:27 PM, Hannes Frederic Sowa <hannes@stressinduktion.org> wrote: > What I don't really understand is that the addition of this complexity > actually reduces the performance, as you have to take the "if (left)" > branch during hashing and causes you to make a load_unaligned_zeropad. Oh, duh, you guys are right. Fixed in my repo [1]. I'll submit the next version in a day or so to let some other comments come in. Thanks again for your reviews. Jason [1] https://git.zx2c4.com/linux-dev/log/?h=siphash ^ permalink raw reply [flat|nested] 70+ messages in thread
* [PATCH v2 4/4] random: use siphash24 instead of md5 for get_random_int/long 2016-12-14 3:59 [PATCH v2 1/4] siphash: add cryptographically secure hashtable function Jason A. Donenfeld 2016-12-14 3:59 ` [PATCH v2 2/4] siphash: add convenience functions for jhash converts Jason A. Donenfeld 2016-12-14 3:59 ` [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform Jason A. Donenfeld @ 2016-12-14 3:59 ` Jason A. Donenfeld 2016-12-14 11:21 ` [PATCH v2 1/4] siphash: add cryptographically secure hashtable function Hannes Frederic Sowa ` (2 subsequent siblings) 5 siblings, 0 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 3:59 UTC (permalink / raw) To: Netdev, kernel-hardening, LKML, linux-crypto Cc: Jason A. Donenfeld, Jean-Philippe Aumasson, Ted Tso This duplicates the current algorithm for get_random_int/long, but uses siphash24 instead. This comes with several benefits. It's certainly faster and more cryptographically secure than MD5. This patch also hashes the pid, entropy, and timestamp as fixed width fields, in order to increase diffusion. The previous md5 algorithm used a per-cpu md5 state, which caused successive calls to the function to chain upon each other. While it's not entirely clear that this kind of chaining is absolutely necessary when using a secure PRF like siphash24, it can't hurt, and the timing of the call chain does add a degree of natural entropy. So, in keeping with this design, instead of the massive per-cpu 64-byte md5 state, there is instead a per-cpu previously returned value for chaining. Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> Cc: Ted Tso <tytso@mit.edu> --- Changes from v1->v2: - Uses u64 instead of uint64_t - Uses get_cpu_ptr instead of get_cpu_var drivers/char/random.c | 50 +++++++++++++++++++++++++++++++------------------- 1 file changed, 31 insertions(+), 19 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d6876d506220..61c4b45427dc 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -262,6 +262,7 @@ #include <linux/syscalls.h> #include <linux/completion.h> #include <linux/uuid.h> +#include <linux/siphash.h> #include <crypto/chacha20.h> #include <asm/processor.h> @@ -2042,7 +2043,7 @@ struct ctl_table random_table[] = { }; #endif /* CONFIG_SYSCTL */ -static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned; +static u8 random_int_secret[SIPHASH24_KEY_LEN]; int random_int_secret_init(void) { @@ -2050,8 +2051,7 @@ int random_int_secret_init(void) return 0; } -static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash) - __aligned(sizeof(unsigned long)); +static DEFINE_PER_CPU(u64, get_random_int_chaining); /* * Get a random word for internal kernel use only. Similar to urandom but @@ -2061,19 +2061,25 @@ static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash) */ unsigned int get_random_int(void) { - __u32 *hash; unsigned int ret; + struct { + u64 chaining; + unsigned long ts; + unsigned long entropy; + pid_t pid; + } __packed combined; + u64 *chaining; if (arch_get_random_int(&ret)) return ret; - hash = get_cpu_var(get_random_int_hash); - - hash[0] += current->pid + jiffies + random_get_entropy(); - md5_transform(hash, random_int_secret); - ret = hash[0]; - put_cpu_var(get_random_int_hash); - + chaining = get_cpu_ptr(&get_random_int_chaining); + combined.chaining = *chaining; + combined.ts = jiffies; + combined.entropy = random_get_entropy(); + combined.pid = current->pid; + ret = *chaining = siphash24((u8 *)&combined, sizeof(combined), random_int_secret); + put_cpu_ptr(chaining); return ret; } EXPORT_SYMBOL(get_random_int); @@ -2083,19 +2089,25 @@ EXPORT_SYMBOL(get_random_int); */ unsigned long get_random_long(void) { - __u32 *hash; unsigned long ret; + struct { + u64 chaining; + unsigned long ts; + unsigned long entropy; + pid_t pid; + } __packed combined; + u64 *chaining; if (arch_get_random_long(&ret)) return ret; - hash = get_cpu_var(get_random_int_hash); - - hash[0] += current->pid + jiffies + random_get_entropy(); - md5_transform(hash, random_int_secret); - ret = *(unsigned long *)hash; - put_cpu_var(get_random_int_hash); - + chaining = get_cpu_ptr(&get_random_int_chaining); + combined.chaining = *chaining; + combined.ts = jiffies; + combined.entropy = random_get_entropy(); + combined.pid = current->pid; + ret = *chaining = siphash24((u8 *)&combined, sizeof(combined), random_int_secret); + put_cpu_ptr(chaining); return ret; } EXPORT_SYMBOL(get_random_long); -- 2.11.0 ^ permalink raw reply related [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-14 3:59 [PATCH v2 1/4] siphash: add cryptographically secure hashtable function Jason A. Donenfeld ` (2 preceding siblings ...) 2016-12-14 3:59 ` [PATCH v2 4/4] random: use siphash24 instead of md5 for get_random_int/long Jason A. Donenfeld @ 2016-12-14 11:21 ` Hannes Frederic Sowa 2016-12-14 13:10 ` Jason A. Donenfeld 2016-12-14 12:46 ` Jason A. Donenfeld 2016-12-14 18:46 ` [PATCH v3 1/3] " Jason A. Donenfeld 5 siblings, 1 reply; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-14 11:21 UTC (permalink / raw) To: Jason A. Donenfeld, Netdev, kernel-hardening, LKML, linux-crypto Cc: Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers Hello, On 14.12.2016 04:59, 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. Can you show or cite benchmarks in comparison with jhash? Last time I looked, especially for short inputs, siphash didn't beat jhash (also on all the 32 bit devices etc.). > 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. This pretty much depends on the linearity of the hash function? I don't think a crypto secure hash function is needed for a hash table. Albeit I agree that siphash certainly looks good to be used here. > 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. I am pretty sure that SipHash still needs a random key per hash table also. So far it was only the choice of hash function you are questioning. > (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. Hmm, I tried to follow up with all the HashDoS work and so far didn't see any HashDoS attacks against the Jenkins/SpookyHash family. If this is an issue we might need to also put those changes into stable. > 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. Bye, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-14 11:21 ` [PATCH v2 1/4] siphash: add cryptographically secure hashtable function Hannes Frederic Sowa @ 2016-12-14 13:10 ` Jason A. Donenfeld 2016-12-14 15:09 ` Hannes Frederic Sowa 2016-12-15 7:57 ` Herbert Xu 0 siblings, 2 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 13:10 UTC (permalink / raw) To: Hannes Frederic Sowa Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers Hi Hannes, On Wed, Dec 14, 2016 at 12:21 PM, Hannes Frederic Sowa <hannes@stressinduktion.org> wrote: > Can you show or cite benchmarks in comparison with jhash? Last time I > looked, especially for short inputs, siphash didn't beat jhash (also on > all the 32 bit devices etc.). I assume that jhash is likely faster than siphash, but I wouldn't be surprised if with optimization we can make siphash at least pretty close on 64-bit platforms. (I'll do some tests though; maybe I'm wrong and jhash is already slower.) With that said, siphash is here to replace uses of jhash where hashtable poisoning vulnerabilities make it necessary. Where there's no significant security improvement, if there's no speed improvement either, then of course nothing's going to change. I should have mentioned md5_transform in this first message too, as two other patches in this series actually replace md5_transform usage with siphash. I think in this case, siphash is a clear performance winner (and security winner) over md5_transform. So if the push back against replacing jhash usages is just too high, at the very least it remains useful already for the md5_transform usage. > This pretty much depends on the linearity of the hash function? I don't > think a crypto secure hash function is needed for a hash table. Albeit I > agree that siphash certainly looks good to be used here. In order to prevent the aforementioned poisoning attacks, a PRF with perfect linearity is required, which is what's achieved when it's a cryptographically secure one. Check out section 7 of https://131002.net/siphash/siphash.pdf . > I am pretty sure that SipHash still needs a random key per hash table > also. So far it was only the choice of hash function you are questioning. Siphash needs a random secret key, yes. The point is that the hash function remains secure so long as the secret key is kept secret. Other functions can't make the same guarantee, and so nervous periodic key rotation is necessary, but in most cases nothing is done, and so things just leak over time. > Hmm, I tried to follow up with all the HashDoS work and so far didn't > see any HashDoS attacks against the Jenkins/SpookyHash family. > > If this is an issue we might need to also put those changes into stable. jhash just isn't secure; it's not a cryptographically secure PRF. If there hasn't already been an academic paper put out there about it this year, let's make this thread 1000 messages long to garner attention, and next year perhaps we'll see one. No doubt that motivated government organizations, defense contractors, criminals, and other netizens have already done research in private. Replacing insecure functions with secure functions is usually a good thing. Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-14 13:10 ` Jason A. Donenfeld @ 2016-12-14 15:09 ` Hannes Frederic Sowa 2016-12-14 19:47 ` Jason A. Donenfeld 2016-12-15 7:57 ` Herbert Xu 1 sibling, 1 reply; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-14 15:09 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers Hello, On 14.12.2016 14:10, Jason A. Donenfeld wrote: > On Wed, Dec 14, 2016 at 12:21 PM, Hannes Frederic Sowa > <hannes@stressinduktion.org> wrote: >> Can you show or cite benchmarks in comparison with jhash? Last time I >> looked, especially for short inputs, siphash didn't beat jhash (also on >> all the 32 bit devices etc.). > > I assume that jhash is likely faster than siphash, but I wouldn't be > surprised if with optimization we can make siphash at least pretty > close on 64-bit platforms. (I'll do some tests though; maybe I'm wrong > and jhash is already slower.) Yes, numbers would be very usable here. I am mostly concerned about small plastic router cases. E.g. assume you double packet processing time with a change of the hashing function at what point is the actual packet processing more of an attack vector than the hashtable? > With that said, siphash is here to replace uses of jhash where > hashtable poisoning vulnerabilities make it necessary. Where there's > no significant security improvement, if there's no speed improvement > either, then of course nothing's going to change. It still changes currently well working source. ;-) > I should have mentioned md5_transform in this first message too, as > two other patches in this series actually replace md5_transform usage > with siphash. I think in this case, siphash is a clear performance > winner (and security winner) over md5_transform. So if the push back > against replacing jhash usages is just too high, at the very least it > remains useful already for the md5_transform usage. MD5 is considered broken because its collision resistance is broken? SipHash doesn't even claim to have collision resistance (which we don't need here)? But I agree, certainly it could be a nice speed-up! >> This pretty much depends on the linearity of the hash function? I don't >> think a crypto secure hash function is needed for a hash table. Albeit I >> agree that siphash certainly looks good to be used here. > > In order to prevent the aforementioned poisoning attacks, a PRF with > perfect linearity is required, which is what's achieved when it's a > cryptographically secure one. Check out section 7 of > https://131002.net/siphash/siphash.pdf . I think you mean non-linearity. Otherwise I agree that siphash is certainly a better suited hashing algorithm as far as I know. But it would be really interesting to compare some performance numbers. Hard to say anything without them. >> I am pretty sure that SipHash still needs a random key per hash table >> also. So far it was only the choice of hash function you are questioning. > > Siphash needs a random secret key, yes. The point is that the hash > function remains secure so long as the secret key is kept secret. > Other functions can't make the same guarantee, and so nervous periodic > key rotation is necessary, but in most cases nothing is done, and so > things just leak over time. > > >> Hmm, I tried to follow up with all the HashDoS work and so far didn't >> see any HashDoS attacks against the Jenkins/SpookyHash family. >> >> If this is an issue we might need to also put those changes into stable. > > jhash just isn't secure; it's not a cryptographically secure PRF. If > there hasn't already been an academic paper put out there about it > this year, let's make this thread 1000 messages long to garner > attention, and next year perhaps we'll see one. No doubt that > motivated government organizations, defense contractors, criminals, > and other netizens have already done research in private. Replacing > insecure functions with secure functions is usually a good thing. I think this is a weak argument. In general I am in favor to switch to siphash, but it would be nice to see some benchmarks with the specific kernel implementation also on some smaller 32 bit CPUs and especially without using any SIMD instructions (which might have been used in paper comparison). Bye, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-14 15:09 ` Hannes Frederic Sowa @ 2016-12-14 19:47 ` Jason A. Donenfeld 0 siblings, 0 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 19:47 UTC (permalink / raw) To: Hannes Frederic Sowa Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers Hi Hannes, On Wed, Dec 14, 2016 at 4:09 PM, Hannes Frederic Sowa <hannes@stressinduktion.org> wrote: > Yes, numbers would be very usable here. I am mostly concerned about > small plastic router cases. E.g. assume you double packet processing > time with a change of the hashing function at what point is the actual > packet processing more of an attack vector than the hashtable? I agree. Looks like Tom did some very quick benchmarks. I'll do some more precise benchmarks myself when we graduate from looking at md5 replacement (the easy case) to looking at jhash replacement (the harder case). >> With that said, siphash is here to replace uses of jhash where >> hashtable poisoning vulnerabilities make it necessary. Where there's >> no significant security improvement, if there's no speed improvement >> either, then of course nothing's going to change. > > It still changes currently well working source. ;-) I mean if siphash doesn't make things better in someway, we'll just continue using jhash, so no source change or anything. In other words: evolutionary conservative approach rather than hasty "replace 'em all!" tomfoolery. > MD5 is considered broken because its collision resistance is broken? > SipHash doesn't even claim to have collision resistance (which we don't > need here)? Not just that, but it's not immediately clear to me that using MD5 as a PRF the way it is now with md5_transform is even a straightforwardly good idea. > But I agree, certainly it could be a nice speed-up! The benchmarks for the secure sequence number generation and the rng are indeed really promising. > I think you mean non-linearity. Yea of course, editing typo, sorry. > In general I am in favor to switch to siphash, but it would be nice to > see some benchmarks with the specific kernel implementation also on some > smaller 32 bit CPUs and especially without using any SIMD instructions > (which might have been used in paper comparison). Sure, agreed. Each proposed jhash replacement will need to be benchmarked on little MIPS machines and x86 monsters alike, with patches indicating PPS before and after. Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-14 13:10 ` Jason A. Donenfeld 2016-12-14 15:09 ` Hannes Frederic Sowa @ 2016-12-15 7:57 ` Herbert Xu 2016-12-15 8:15 ` [kernel-hardening] " Daniel Micay 1 sibling, 1 reply; 70+ messages in thread From: Herbert Xu @ 2016-12-15 7:57 UTC (permalink / raw) To: Jason A. Donenfeld Cc: hannes, netdev, kernel-hardening, linux-kernel, linux-crypto, jeanphilippe.aumasson, djb, torvalds, ebiggers3 Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > Siphash needs a random secret key, yes. The point is that the hash > function remains secure so long as the secret key is kept secret. > Other functions can't make the same guarantee, and so nervous periodic > key rotation is necessary, but in most cases nothing is done, and so > things just leak over time. Actually those users that use rhashtable now have a much more sophisticated defence against these attacks, dyanmic rehashing when bucket length exceeds a preset limit. Cheers, -- Email: Herbert Xu <herbert@gondor.apana.org.au> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [kernel-hardening] Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 7:57 ` Herbert Xu @ 2016-12-15 8:15 ` Daniel Micay 0 siblings, 0 replies; 70+ messages in thread From: Daniel Micay @ 2016-12-15 8:15 UTC (permalink / raw) To: kernel-hardening, Jason A. Donenfeld Cc: hannes, netdev, linux-kernel, linux-crypto, jeanphilippe.aumasson, djb, torvalds, ebiggers3 [-- Attachment #1: Type: text/plain, Size: 768 bytes --] On Thu, 2016-12-15 at 15:57 +0800, Herbert Xu wrote: > Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > > > Siphash needs a random secret key, yes. The point is that the hash > > function remains secure so long as the secret key is kept secret. > > Other functions can't make the same guarantee, and so nervous > > periodic > > key rotation is necessary, but in most cases nothing is done, and so > > things just leak over time. > > Actually those users that use rhashtable now have a much more > sophisticated defence against these attacks, dyanmic rehashing > when bucket length exceeds a preset limit. > > Cheers, Key independent collisions won't be mitigated by picking a new secret. A simple solution with clear security properties is ideal. [-- Attachment #2: This is a digitally signed message part --] [-- Type: application/pgp-signature, Size: 866 bytes --] ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-14 3:59 [PATCH v2 1/4] siphash: add cryptographically secure hashtable function Jason A. Donenfeld ` (3 preceding siblings ...) 2016-12-14 11:21 ` [PATCH v2 1/4] siphash: add cryptographically secure hashtable function Hannes Frederic Sowa @ 2016-12-14 12:46 ` Jason A. Donenfeld 2016-12-14 22:03 ` Hannes Frederic Sowa 2016-12-14 18:46 ` [PATCH v3 1/3] " Jason A. Donenfeld 5 siblings, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 12:46 UTC (permalink / raw) To: David Laight Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers Hi David, On Wed, Dec 14, 2016 at 10:56 AM, David Laight <David.Laight@aculab.com> wrote: > ... >> +u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]) > ... >> + u64 k0 = get_unaligned_le64(key); >> + u64 k1 = get_unaligned_le64(key + sizeof(u64)); > ... >> + m = get_unaligned_le64(data); > > All these unaligned accesses are going to get expensive on architectures > like sparc64. Yes, the unaligned accesses aren't pretty. Since in pretty much all use cases thus far, the data can easily be made aligned, perhaps it makes sense to create siphash24() and siphash24_unaligned(). Any thoughts on doing something like that? Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-14 12:46 ` Jason A. Donenfeld @ 2016-12-14 22:03 ` Hannes Frederic Sowa 2016-12-14 23:29 ` Jason A. Donenfeld 2016-12-15 11:04 ` David Laight 0 siblings, 2 replies; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-14 22:03 UTC (permalink / raw) To: Jason A. Donenfeld, David Laight Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On 14.12.2016 13:46, Jason A. Donenfeld wrote: > Hi David, > > On Wed, Dec 14, 2016 at 10:56 AM, David Laight <David.Laight@aculab.com> wrote: >> ... >>> +u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]) >> ... >>> + u64 k0 = get_unaligned_le64(key); >>> + u64 k1 = get_unaligned_le64(key + sizeof(u64)); >> ... >>> + m = get_unaligned_le64(data); >> >> All these unaligned accesses are going to get expensive on architectures >> like sparc64. > > Yes, the unaligned accesses aren't pretty. Since in pretty much all > use cases thus far, the data can easily be made aligned, perhaps it > makes sense to create siphash24() and siphash24_unaligned(). Any > thoughts on doing something like that? I fear that the alignment requirement will be a source of bugs on 32 bit machines, where you cannot even simply take a well aligned struct on a stack and put it into the normal siphash(aligned) function without adding alignment annotations everywhere. Even blocks returned from kmalloc on 32 bit are not aligned to 64 bit. Can we do this a runtime check and just have one function (siphash) dealing with that? Bye, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-14 22:03 ` Hannes Frederic Sowa @ 2016-12-14 23:29 ` Jason A. Donenfeld 2016-12-15 8:31 ` Hannes Frederic Sowa 2016-12-15 11:04 ` David Laight 1 sibling, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 23:29 UTC (permalink / raw) To: Hannes Frederic Sowa Cc: David Laight, Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers Hi Hannes, On Wed, Dec 14, 2016 at 11:03 PM, Hannes Frederic Sowa <hannes@stressinduktion.org> wrote: > I fear that the alignment requirement will be a source of bugs on 32 bit > machines, where you cannot even simply take a well aligned struct on a > stack and put it into the normal siphash(aligned) function without > adding alignment annotations everywhere. Even blocks returned from > kmalloc on 32 bit are not aligned to 64 bit. That's what the "__aligned(SIPHASH24_ALIGNMENT)" attribute is for. The aligned siphash function will be for structs explicitly made for siphash consumption. For everything else there's siphash_unaligned. > Can we do this a runtime check and just have one function (siphash) > dealing with that? Seems like the runtime branching on the aligned function would be bad for performance, when we likely know at compile time if it's going to be aligned or not. I suppose we could add that check just to the unaligned version, and rename it to "maybe_unaligned"? Is this what you have in mind? Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-14 23:29 ` Jason A. Donenfeld @ 2016-12-15 8:31 ` Hannes Frederic Sowa 0 siblings, 0 replies; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-15 8:31 UTC (permalink / raw) To: Jason A. Donenfeld Cc: David Laight, Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On 15.12.2016 00:29, Jason A. Donenfeld wrote: > Hi Hannes, > > On Wed, Dec 14, 2016 at 11:03 PM, Hannes Frederic Sowa > <hannes@stressinduktion.org> wrote: >> I fear that the alignment requirement will be a source of bugs on 32 bit >> machines, where you cannot even simply take a well aligned struct on a >> stack and put it into the normal siphash(aligned) function without >> adding alignment annotations everywhere. Even blocks returned from >> kmalloc on 32 bit are not aligned to 64 bit. > > That's what the "__aligned(SIPHASH24_ALIGNMENT)" attribute is for. The > aligned siphash function will be for structs explicitly made for > siphash consumption. For everything else there's siphash_unaligned. So in case you have a pointer from somewhere on 32 bit you can essentially only guarantee it has natural alignment or max. native alignment (based on the arch). gcc only fulfills your request for alignment when you allocate on the stack (minus gcc bugs). Let's say you get a pointer from somewhere, maybe embedded in a struct, which came from kmalloc. kmalloc doesn't care about aligned attribute, it will align according to architecture description. That said, if you want to hash that, you would need manually align the memory returned from kmalloc or make sure the the data is more than naturally aligned on that architecture. >> Can we do this a runtime check and just have one function (siphash) >> dealing with that? > > Seems like the runtime branching on the aligned function would be bad > for performance, when we likely know at compile time if it's going to > be aligned or not. I suppose we could add that check just to the > unaligned version, and rename it to "maybe_unaligned"? Is this what > you have in mind? I argue that you mostly don't know at compile time if it is correctly aligned if the alignment requirements are larger than the natural ones. Also, we don't even have that for memcpy, even we use it probably much more than hashing, so I think this is overkill. Bye, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* RE: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-14 22:03 ` Hannes Frederic Sowa 2016-12-14 23:29 ` Jason A. Donenfeld @ 2016-12-15 11:04 ` David Laight 2016-12-15 12:23 ` Hannes Frederic Sowa 1 sibling, 1 reply; 70+ messages in thread From: David Laight @ 2016-12-15 11:04 UTC (permalink / raw) To: 'Hannes Frederic Sowa', Jason A. Donenfeld Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers From: Hannes Frederic Sowa > Sent: 14 December 2016 22:03 > On 14.12.2016 13:46, Jason A. Donenfeld wrote: > > Hi David, > > > > On Wed, Dec 14, 2016 at 10:56 AM, David Laight <David.Laight@aculab.com> wrote: > >> ... > >>> +u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]) > >> ... > >>> + u64 k0 = get_unaligned_le64(key); > >>> + u64 k1 = get_unaligned_le64(key + sizeof(u64)); > >> ... > >>> + m = get_unaligned_le64(data); > >> > >> All these unaligned accesses are going to get expensive on architectures > >> like sparc64. > > > > Yes, the unaligned accesses aren't pretty. Since in pretty much all > > use cases thus far, the data can easily be made aligned, perhaps it > > makes sense to create siphash24() and siphash24_unaligned(). Any > > thoughts on doing something like that? > > I fear that the alignment requirement will be a source of bugs on 32 bit > machines, where you cannot even simply take a well aligned struct on a > stack and put it into the normal siphash(aligned) function without > adding alignment annotations everywhere. Even blocks returned from > kmalloc on 32 bit are not aligned to 64 bit. Are you doing anything that will require 64bit alignment on 32bit systems? It is unlikely that the kernel can use any simd registers that have wider alignment requirements. You also really don't want to request on-stack items have large alignments. While gcc can generate code to do it, it isn't pretty. David ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 11:04 ` David Laight @ 2016-12-15 12:23 ` Hannes Frederic Sowa 2016-12-15 12:28 ` David Laight 0 siblings, 1 reply; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-15 12:23 UTC (permalink / raw) To: David Laight, Jason A. Donenfeld Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On 15.12.2016 12:04, David Laight wrote: > From: Hannes Frederic Sowa >> Sent: 14 December 2016 22:03 >> On 14.12.2016 13:46, Jason A. Donenfeld wrote: >>> Hi David, >>> >>> On Wed, Dec 14, 2016 at 10:56 AM, David Laight <David.Laight@aculab.com> wrote: >>>> ... >>>>> +u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]) >>>> ... >>>>> + u64 k0 = get_unaligned_le64(key); >>>>> + u64 k1 = get_unaligned_le64(key + sizeof(u64)); >>>> ... >>>>> + m = get_unaligned_le64(data); >>>> >>>> All these unaligned accesses are going to get expensive on architectures >>>> like sparc64. >>> >>> Yes, the unaligned accesses aren't pretty. Since in pretty much all >>> use cases thus far, the data can easily be made aligned, perhaps it >>> makes sense to create siphash24() and siphash24_unaligned(). Any >>> thoughts on doing something like that? >> >> I fear that the alignment requirement will be a source of bugs on 32 bit >> machines, where you cannot even simply take a well aligned struct on a >> stack and put it into the normal siphash(aligned) function without >> adding alignment annotations everywhere. Even blocks returned from >> kmalloc on 32 bit are not aligned to 64 bit. > > Are you doing anything that will require 64bit alignment on 32bit systems? > It is unlikely that the kernel can use any simd registers that have wider > alignment requirements. > > You also really don't want to request on-stack items have large alignments. > While gcc can generate code to do it, it isn't pretty. Hmm? Even the Intel ABI expects alignment of unsigned long long to be 8 bytes on 32 bit. Do you question that? ^ permalink raw reply [flat|nested] 70+ messages in thread
* RE: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 12:23 ` Hannes Frederic Sowa @ 2016-12-15 12:28 ` David Laight 2016-12-15 12:50 ` Hannes Frederic Sowa 0 siblings, 1 reply; 70+ messages in thread From: David Laight @ 2016-12-15 12:28 UTC (permalink / raw) To: 'Hannes Frederic Sowa', Jason A. Donenfeld Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers From: Hannes Frederic Sowa > Sent: 15 December 2016 12:23 ... > Hmm? Even the Intel ABI expects alignment of unsigned long long to be 8 > bytes on 32 bit. Do you question that? Yes. The linux ABI for x86 (32 bit) only requires 32bit alignment for u64 (etc). David ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 12:28 ` David Laight @ 2016-12-15 12:50 ` Hannes Frederic Sowa 2016-12-15 13:56 ` David Laight 0 siblings, 1 reply; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-15 12:50 UTC (permalink / raw) To: David Laight, Jason A. Donenfeld Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On 15.12.2016 13:28, David Laight wrote: > From: Hannes Frederic Sowa >> Sent: 15 December 2016 12:23 > ... >> Hmm? Even the Intel ABI expects alignment of unsigned long long to be 8 >> bytes on 32 bit. Do you question that? > > Yes. > > The linux ABI for x86 (32 bit) only requires 32bit alignment for u64 (etc). Hmm, u64 on 32 bit is unsigned long long and not unsigned long. Thus I am actually not sure if the ABI would say anything about that (sorry also for my wrong statement above). Alignment requirement of unsigned long long on gcc with -m32 actually seem to be 8. ^ permalink raw reply [flat|nested] 70+ messages in thread
* RE: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 12:50 ` Hannes Frederic Sowa @ 2016-12-15 13:56 ` David Laight 2016-12-15 14:56 ` Hannes Frederic Sowa 0 siblings, 1 reply; 70+ messages in thread From: David Laight @ 2016-12-15 13:56 UTC (permalink / raw) To: 'Hannes Frederic Sowa', Jason A. Donenfeld Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers From: Hannes Frederic Sowa > Sent: 15 December 2016 12:50 > On 15.12.2016 13:28, David Laight wrote: > > From: Hannes Frederic Sowa > >> Sent: 15 December 2016 12:23 > > ... > >> Hmm? Even the Intel ABI expects alignment of unsigned long long to be 8 > >> bytes on 32 bit. Do you question that? > > > > Yes. > > > > The linux ABI for x86 (32 bit) only requires 32bit alignment for u64 (etc). > > Hmm, u64 on 32 bit is unsigned long long and not unsigned long. Thus I > am actually not sure if the ABI would say anything about that (sorry > also for my wrong statement above). > > Alignment requirement of unsigned long long on gcc with -m32 actually > seem to be 8. It depends on the architecture. For x86 it is definitely 4. It might be 8 for sparc, ppc and/or alpha. David ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 13:56 ` David Laight @ 2016-12-15 14:56 ` Hannes Frederic Sowa 2016-12-15 15:41 ` David Laight 0 siblings, 1 reply; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-15 14:56 UTC (permalink / raw) To: David Laight, Jason A. Donenfeld Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On 15.12.2016 14:56, David Laight wrote: > From: Hannes Frederic Sowa >> Sent: 15 December 2016 12:50 >> On 15.12.2016 13:28, David Laight wrote: >>> From: Hannes Frederic Sowa >>>> Sent: 15 December 2016 12:23 >>> ... >>>> Hmm? Even the Intel ABI expects alignment of unsigned long long to be 8 >>>> bytes on 32 bit. Do you question that? >>> >>> Yes. >>> >>> The linux ABI for x86 (32 bit) only requires 32bit alignment for u64 (etc). >> >> Hmm, u64 on 32 bit is unsigned long long and not unsigned long. Thus I >> am actually not sure if the ABI would say anything about that (sorry >> also for my wrong statement above). >> >> Alignment requirement of unsigned long long on gcc with -m32 actually >> seem to be 8. > > It depends on the architecture. > For x86 it is definitely 4. May I ask for a reference? I couldn't see unsigned long long being mentioned in the ia32 abi spec that I found. I agree that those accesses might be synthetically assembled by gcc and for me the alignment of 4 would have seemed natural. But my gcc at least in 32 bit mode disagrees with that. > It might be 8 for sparc, ppc and/or alpha. This is something to find out... Right now ipv6 addresses have an alignment of 4. So we couldn't even naturally pass them to siphash but would need to copy them around, which I feel like a source of bugs. Bye, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* RE: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 14:56 ` Hannes Frederic Sowa @ 2016-12-15 15:41 ` David Laight 2016-12-15 15:53 ` Hannes Frederic Sowa 0 siblings, 1 reply; 70+ messages in thread From: David Laight @ 2016-12-15 15:41 UTC (permalink / raw) To: 'Hannes Frederic Sowa', Jason A. Donenfeld Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers From: Hannes Frederic Sowa > Sent: 15 December 2016 14:57 > On 15.12.2016 14:56, David Laight wrote: > > From: Hannes Frederic Sowa > >> Sent: 15 December 2016 12:50 > >> On 15.12.2016 13:28, David Laight wrote: > >>> From: Hannes Frederic Sowa > >>>> Sent: 15 December 2016 12:23 > >>> ... > >>>> Hmm? Even the Intel ABI expects alignment of unsigned long long to be 8 > >>>> bytes on 32 bit. Do you question that? > >>> > >>> Yes. > >>> > >>> The linux ABI for x86 (32 bit) only requires 32bit alignment for u64 (etc). > >> > >> Hmm, u64 on 32 bit is unsigned long long and not unsigned long. Thus I > >> am actually not sure if the ABI would say anything about that (sorry > >> also for my wrong statement above). > >> > >> Alignment requirement of unsigned long long on gcc with -m32 actually > >> seem to be 8. > > > > It depends on the architecture. > > For x86 it is definitely 4. > > May I ask for a reference? Ask anyone who has had to do compatibility layers to support 32bit binaries on 64bit systems. > I couldn't see unsigned long long being > mentioned in the ia32 abi spec that I found. I agree that those accesses > might be synthetically assembled by gcc and for me the alignment of 4 > would have seemed natural. But my gcc at least in 32 bit mode disagrees > with that. Try (retyped): echo 'struct { long a; long long b; } s; int bar { return sizeof s; }' >foo.c gcc [-m32] -O2 -S foo.c; cat foo.s And look at what is generated. > Right now ipv6 addresses have an alignment of 4. So we couldn't even > naturally pass them to siphash but would need to copy them around, which > I feel like a source of bugs. That is more of a problem on systems that don't support misaligned accesses. Reading the 64bit values with two explicit 32bit reads would work. I think you can get gcc to do that by adding an aligned(4) attribute to the structure member. David ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 15:41 ` David Laight @ 2016-12-15 15:53 ` Hannes Frederic Sowa 2016-12-15 18:50 ` Jason A. Donenfeld 0 siblings, 1 reply; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-15 15:53 UTC (permalink / raw) To: David Laight, Jason A. Donenfeld Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On 15.12.2016 16:41, David Laight wrote: > Try (retyped): > > echo 'struct { long a; long long b; } s; int bar { return sizeof s; }' >foo.c > gcc [-m32] -O2 -S foo.c; cat foo.s > > And look at what is generated. I used __alignof__(unsigned long long) with -m32. >> Right now ipv6 addresses have an alignment of 4. So we couldn't even >> naturally pass them to siphash but would need to copy them around, which >> I feel like a source of bugs. > > That is more of a problem on systems that don't support misaligned accesses. > Reading the 64bit values with two explicit 32bit reads would work. > I think you can get gcc to do that by adding an aligned(4) attribute to the > structure member. Yes, and that is actually my fear, because we support those architectures. I can't comment on that as I don't understand enough of this. If someone finds a way to cause misaligned reads on a small box this seems (maybe depending on sysctls they get fixed up or panic) to be a much bigger issue than having a hash DoS. Thanks, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 15:53 ` Hannes Frederic Sowa @ 2016-12-15 18:50 ` Jason A. Donenfeld 2016-12-15 20:31 ` Hannes Frederic Sowa 2016-12-15 21:09 ` Peter Zijlstra 0 siblings, 2 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-15 18:50 UTC (permalink / raw) To: Hannes Frederic Sowa, David Laight Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers Hi David & Hannes, This conversation is veering off course. I think this doesn't really matter at all. Gcc converts u64 into essentially a pair of u32 on 32-bit platforms, so the alignment requirements for 32-bit is at a maximum 32 bits. On 64-bit platforms the alignment requirements are related at a maximum to the biggest register size, so 64-bit alignment. For this reason, no matter the behavior of __aligned(8), we're okay. Likewise, even without __aligned(8), if gcc aligns structs by their biggest member, then we get 4 byte alignment on 32-bit and 8 byte alignment on 64-bit, which is fine. There's no 32-bit platform that will trap on a 64-bit unaligned access because there's no such thing as a 64-bit access there. In short, we're fine. (The reason in6_addr aligns itself to 4 bytes on 64-bit platforms is that it's defined as being u32 blah[4]. If we added a u64 blah[2], we'd get 8 byte alignment, but that's not in the header. Feel free to start a new thread about this issue if you feel this ought to be added for whatever reason.) One optimization that's been suggested on this list is that instead of u8 key[16] and requiring the alignment attribute, I should just use u64 key[2]. This seems reasonable to me, and it will also save the endian conversion call. These keys generally aren't transmitted over a network, so I don't think a byte-wise encoding is particularly important. The other suggestion I've seen is that I make the functions take a const void * instead of a const u8 * for the data, in order to save ugly casts. I'll do this too. Meanwhile Linus has condemned our 4dwords/2qwords naming, and I'll need to think of something different. The best I can think of right now is siphash_4_u32/siphash_2_u64, but I don't find it especially pretty. Open to suggestions. Regards, Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 18:50 ` Jason A. Donenfeld @ 2016-12-15 20:31 ` Hannes Frederic Sowa 2016-12-15 20:43 ` Jason A. Donenfeld 2016-12-15 21:09 ` Peter Zijlstra 1 sibling, 1 reply; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-15 20:31 UTC (permalink / raw) To: Jason A. Donenfeld, David Laight Cc: Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers Hello, On 15.12.2016 19:50, Jason A. Donenfeld wrote: > Hi David & Hannes, > > This conversation is veering off course. Why? > I think this doesn't really > matter at all. Gcc converts u64 into essentially a pair of u32 on > 32-bit platforms, so the alignment requirements for 32-bit is at a > maximum 32 bits. On 64-bit platforms the alignment requirements are > related at a maximum to the biggest register size, so 64-bit > alignment. For this reason, no matter the behavior of __aligned(8), > we're okay. Likewise, even without __aligned(8), if gcc aligns structs > by their biggest member, then we get 4 byte alignment on 32-bit and 8 > byte alignment on 64-bit, which is fine. There's no 32-bit platform > that will trap on a 64-bit unaligned access because there's no such > thing as a 64-bit access there. In short, we're fine. ARM64 and x86-64 have memory operations that are not vector operations that operate on 128 bit memory. How do you know that the compiler for some architecture will not chose a more optimized instruction to load a 64 bit memory value into two 32 bit registers if you tell the compiler it is 8 byte aligned but it actually isn't? I don't know the answer but telling the compiler some data is 8 byte aligned while it isn't really pretty much seems like a call for trouble. Why can't a compiler not vectorize this code if it can prove that it doesn't conflict with other register users? Bye, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 20:31 ` Hannes Frederic Sowa @ 2016-12-15 20:43 ` Jason A. Donenfeld 2016-12-15 21:04 ` Peter Zijlstra 2016-12-15 21:17 ` Hannes Frederic Sowa 0 siblings, 2 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-15 20:43 UTC (permalink / raw) To: Hannes Frederic Sowa Cc: David Laight, Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On Thu, Dec 15, 2016 at 9:31 PM, Hannes Frederic Sowa <hannes@stressinduktion.org> wrote: > ARM64 and x86-64 have memory operations that are not vector operations > that operate on 128 bit memory. Fair enough. imull I guess. > How do you know that the compiler for some architecture will not chose a > more optimized instruction to load a 64 bit memory value into two 32 bit > registers if you tell the compiler it is 8 byte aligned but it actually > isn't? I don't know the answer but telling the compiler some data is 8 > byte aligned while it isn't really pretty much seems like a call for > trouble. If a compiler is in the business of using special 64-bit instructions on 64-bit aligned data, then it is also the job of the compiler to align structs to 64-bits when passed __aligned(8), which is what we've done in this code. If the compiler were to hypothetically choose to ignore that and internally convert it to a __aligned(4), then it would only be able to do so with the knowledge that it will never use 64-bit aligned data instructions. But so far as I can tell, gcc always respects __aligned(8), which is why I use it in this patchset. I think there might have been confusion here, because perhaps someone was hoping that since in6_addr is 128-bits, that the __aligned attribute would not be required and that the struct would just automatically be aligned to at least 8 bytes. But in fact, as I mentioned, in6_addr is actually composed of u32[4] and not u64[2], so it will only be aligned to 4 bytes, making the __aligned(8) necessary. I think for the purposes of this patchset, this is a solved problem. There's the unaligned version of the function if you don't know about the data, and there's the aligned version if you're using __aligned(SIPHASH_ALIGNMENT) on your data. Plain and simple. Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 20:43 ` Jason A. Donenfeld @ 2016-12-15 21:04 ` Peter Zijlstra 2016-12-15 21:09 ` Hannes Frederic Sowa 2016-12-15 21:17 ` Hannes Frederic Sowa 1 sibling, 1 reply; 70+ messages in thread From: Peter Zijlstra @ 2016-12-15 21:04 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Hannes Frederic Sowa, David Laight, Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On Thu, Dec 15, 2016 at 09:43:04PM +0100, Jason A. Donenfeld wrote: > On Thu, Dec 15, 2016 at 9:31 PM, Hannes Frederic Sowa > <hannes@stressinduktion.org> wrote: > > ARM64 and x86-64 have memory operations that are not vector operations > > that operate on 128 bit memory. > > Fair enough. imull I guess. imull is into rdx:rax, not memory. I suspect he's talking about cmpxchg16b. ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 21:04 ` Peter Zijlstra @ 2016-12-15 21:09 ` Hannes Frederic Sowa 0 siblings, 0 replies; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-15 21:09 UTC (permalink / raw) To: Peter Zijlstra, Jason A. Donenfeld Cc: David Laight, Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On 15.12.2016 22:04, Peter Zijlstra wrote: > On Thu, Dec 15, 2016 at 09:43:04PM +0100, Jason A. Donenfeld wrote: >> On Thu, Dec 15, 2016 at 9:31 PM, Hannes Frederic Sowa >> <hannes@stressinduktion.org> wrote: >>> ARM64 and x86-64 have memory operations that are not vector operations >>> that operate on 128 bit memory. >> >> Fair enough. imull I guess. > > imull is into rdx:rax, not memory. I suspect he's talking about > cmpxchg16b. Exactly and I think I saw a ll/sc 128 bit on armv8 to atomically manipulate linked lists. Bye, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 20:43 ` Jason A. Donenfeld 2016-12-15 21:04 ` Peter Zijlstra @ 2016-12-15 21:17 ` Hannes Frederic Sowa 1 sibling, 0 replies; 70+ messages in thread From: Hannes Frederic Sowa @ 2016-12-15 21:17 UTC (permalink / raw) To: Jason A. Donenfeld Cc: David Laight, Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On 15.12.2016 21:43, Jason A. Donenfeld wrote: > On Thu, Dec 15, 2016 at 9:31 PM, Hannes Frederic Sowa > <hannes@stressinduktion.org> wrote: >> ARM64 and x86-64 have memory operations that are not vector operations >> that operate on 128 bit memory. > > Fair enough. imull I guess. > >> How do you know that the compiler for some architecture will not chose a >> more optimized instruction to load a 64 bit memory value into two 32 bit >> registers if you tell the compiler it is 8 byte aligned but it actually >> isn't? I don't know the answer but telling the compiler some data is 8 >> byte aligned while it isn't really pretty much seems like a call for >> trouble. > > If a compiler is in the business of using special 64-bit instructions > on 64-bit aligned data, then it is also the job of the compiler to > align structs to 64-bits when passed __aligned(8), which is what we've > done in this code. If the compiler were to hypothetically choose to > ignore that and internally convert it to a __aligned(4), then it would > only be able to do so with the knowledge that it will never use 64-bit > aligned data instructions. But so far as I can tell, gcc always > respects __aligned(8), which is why I use it in this patchset. > > I think there might have been confusion here, because perhaps someone > was hoping that since in6_addr is 128-bits, that the __aligned > attribute would not be required and that the struct would just > automatically be aligned to at least 8 bytes. But in fact, as I > mentioned, in6_addr is actually composed of u32[4] and not u64[2], so > it will only be aligned to 4 bytes, making the __aligned(8) necessary. > > I think for the purposes of this patchset, this is a solved problem. > There's the unaligned version of the function if you don't know about > the data, and there's the aligned version if you're using > __aligned(SIPHASH_ALIGNMENT) on your data. Plain and simple. And I was exactly questioning this. static unsigned int inet6_hash_frag(__be32 id, const struct in6_addr *saddr, const struct in6_addr *daddr) { net_get_random_once(&ip6_frags.rnd, sizeof(ip6_frags.rnd)); return jhash_3words(ipv6_addr_hash(saddr), ipv6_addr_hash(daddr), (__force u32)id, ip6_frags.rnd); } This function had a hash DoS (and kind of still has), but it has been mitigated by explicit checks, I hope. So you start looking for all the pointers where ipv6 addresses could come from and find some globally defined struct where I would need to put the aligned(SIPHASH_ALIGNMENT) into to make this work on 32 bit code? Otherwise just the unaligned version is safe on 32 bit code. Who knows this? It isn't even obvious by looking at the header! I would be interested if the compiler can actually constant-fold the address of the stack allocation with an simple if () or some __builtin_constant_p fiddeling, so we don't have this constant review overhead to which function we pass which data. This would also make this whole discussion mood. Bye, Hannes ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 18:50 ` Jason A. Donenfeld 2016-12-15 20:31 ` Hannes Frederic Sowa @ 2016-12-15 21:09 ` Peter Zijlstra 2016-12-15 21:11 ` [kernel-hardening] " Jason A. Donenfeld 1 sibling, 1 reply; 70+ messages in thread From: Peter Zijlstra @ 2016-12-15 21:09 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Hannes Frederic Sowa, David Laight, Netdev, kernel-hardening, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On Thu, Dec 15, 2016 at 07:50:36PM +0100, Jason A. Donenfeld wrote: > There's no 32-bit platform > that will trap on a 64-bit unaligned access because there's no such > thing as a 64-bit access there. In short, we're fine. ARMv7 LPAE is a 32bit architecture that has 64bit load/stores IIRC. x86 has cmpxchg8b that can do 64bit things and very much wants the u64 aligned. Also, IIRC we have a few platforms where u64 doesn't carry 8 byte alignment, m68k or something like that, but yes, you likely don't care. Just to make life interesting... ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [kernel-hardening] Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 21:09 ` Peter Zijlstra @ 2016-12-15 21:11 ` Jason A. Donenfeld 2016-12-15 21:14 ` Linus Torvalds 0 siblings, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-15 21:11 UTC (permalink / raw) To: kernel-hardening Cc: Hannes Frederic Sowa, David Laight, Netdev, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Linus Torvalds, Eric Biggers On Thu, Dec 15, 2016 at 10:09 PM, Peter Zijlstra <peterz@infradead.org> wrote: > On Thu, Dec 15, 2016 at 07:50:36PM +0100, Jason A. Donenfeld wrote: >> There's no 32-bit platform >> that will trap on a 64-bit unaligned access because there's no such >> thing as a 64-bit access there. In short, we're fine. > > ARMv7 LPAE is a 32bit architecture that has 64bit load/stores IIRC. > > x86 has cmpxchg8b that can do 64bit things and very much wants the u64 > aligned. > > Also, IIRC we have a few platforms where u64 doesn't carry 8 byte > alignment, m68k or something like that, but yes, you likely don't care. Indeed, I stand corrected. But in any case, the use of __aligned(8) in the patchset ensures that things are fixed and that we don't have this issue. ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [kernel-hardening] Re: [PATCH v2 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 21:11 ` [kernel-hardening] " Jason A. Donenfeld @ 2016-12-15 21:14 ` Linus Torvalds 0 siblings, 0 replies; 70+ messages in thread From: Linus Torvalds @ 2016-12-15 21:14 UTC (permalink / raw) To: Jason A. Donenfeld Cc: kernel-hardening, Hannes Frederic Sowa, David Laight, Netdev, Jean-Philippe Aumasson, LKML, Linux Crypto Mailing List, Daniel J . Bernstein, Eric Biggers On Thu, Dec 15, 2016 at 1:11 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > Indeed, I stand corrected. But in any case, the use of __aligned(8) in > the patchset ensures that things are fixed and that we don't have this > issue. I think you can/should just use the natural alignment for "u64". For architectures that need 8-byte alignment, u64 will already be properly aligned. For architectures (like x86-32) that only need 4-byte alignment, you get it. Linus ^ permalink raw reply [flat|nested] 70+ messages in thread
* [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 3:59 [PATCH v2 1/4] siphash: add cryptographically secure hashtable function Jason A. Donenfeld ` (4 preceding siblings ...) 2016-12-14 12:46 ` Jason A. Donenfeld @ 2016-12-14 18:46 ` Jason A. Donenfeld 2016-12-14 18:46 ` [PATCH v3 2/3] secure_seq: use siphash24 instead of md5_transform Jason A. Donenfeld ` (4 more replies) 5 siblings, 5 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 18:46 UTC (permalink / raw) To: Netdev, kernel-hardening, LKML, linux-crypto Cc: Jason A. Donenfeld, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight 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. Secondly, a few places are using MD5 for creating secure sequence numbers, port numbers, or fast random numbers. Siphash is a faster, more fittting, and more secure replacement for MD5 in those situations. 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 <Jason@zx2c4.com> Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> Cc: Daniel J. Bernstein <djb@cr.yp.to> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Eric Biggers <ebiggers3@gmail.com> Cc: David Laight <David.Laight@aculab.com> --- Changes from v2->v3: - There is now a fast aligned version of the function and a not-as-fast unaligned version. The requirements for each have been documented in a docbook-style comment. As well, the header now contains a constant for the expected alignment. - The test suite has been updated to check both the unaligned and aligned version of the function. include/linux/siphash.h | 30 ++++++++++ lib/Kconfig.debug | 6 +- lib/Makefile | 5 +- lib/siphash.c | 153 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/test_siphash.c | 85 +++++++++++++++++++++++++++ 5 files changed, 274 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..82dc1a911a2e --- /dev/null +++ b/include/linux/siphash.h @@ -0,0 +1,30 @@ +/* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com> + * + * 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, + SIPHASH24_ALIGNMENT = 8 +}; + +u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]); + +#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS +static inline u64 siphash24_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]) +{ + return siphash24(data, len, key); +} +#else +u64 siphash24_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]); +#endif + +#endif /* _LINUX_SIPHASH_H */ diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index e6327d102184..32bbf689fc46 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1843,9 +1843,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..32acdc26234f --- /dev/null +++ b/lib/siphash.c @@ -0,0 +1,153 @@ +/* Copyright (C) 2015-2016 Jason A. Donenfeld <Jason@zx2c4.com> + * Copyright (C) 2012-2014 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> + * Copyright (C) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to> + * + * 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) + +static inline u16 le16_to_cpuvp(const void *p) +{ + return le16_to_cpup(p); +} +static inline u32 le32_to_cpuvp(const void *p) +{ + return le32_to_cpup(p); +} +static inline u64 le64_to_cpuvp(const void *p) +{ + return le64_to_cpup(p); +} + +/** + * siphash24 - compute 64-bit siphash24 PRF value + * @data: buffer to hash, must be aligned to SIPHASH24_ALIGNMENT + * @size: size of @data + * @key: key buffer of size SIPHASH24_KEY_LEN, must be aligned to SIPHASH24_ALIGNMENT + */ +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; + } +#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64 + if (left) + b |= le64_to_cpu((__force __le64)(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 |= le32_to_cpuvp(data); break; + case 3: b |= ((u64)data[2]) << 16; + case 2: b |= le16_to_cpuvp(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); + +#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS +/** + * siphash24 - compute 64-bit siphash24 PRF value, without alignment requirements + * @data: buffer to hash + * @size: size of @data + * @key: key buffer of size SIPHASH24_KEY_LEN + */ +u64 siphash24_unaligned(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((__force __le64)(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_unaligned); +#endif diff --git a/lib/test_siphash.c b/lib/test_siphash.c new file mode 100644 index 000000000000..69ac94dec366 --- /dev/null +++ b/lib/test_siphash.c @@ -0,0 +1,85 @@ +/* Test cases for siphash.c + * + * Copyright (C) 2015-2016 Jason A. Donenfeld <Jason@zx2c4.com> + * + * 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] __aligned(SIPHASH24_ALIGNMENT); + u8 k[16] __aligned(SIPHASH24_ALIGNMENT); + u8 in_unaligned[65]; + u8 k_unaligned[65]; + u8 i; + int ret = 0; + + for (i = 0; i < 16; ++i) { + k[i] = i; + k_unaligned[i + 1] = i; + } + for (i = 0; i < 64; ++i) { + in[i] = i; + in_unaligned[i + 1] = i; + if (siphash24(in, i, k) != test_vectors[i]) { + pr_info("self-test aligned %u: FAIL\n", i + 1); + ret = -EINVAL; + } + if (siphash24_unaligned(in_unaligned + 1, i, k_unaligned + 1) != test_vectors[i]) { + pr_info("self-test unaligned %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 <Jason@zx2c4.com>"); +MODULE_LICENSE("Dual BSD/GPL"); -- 2.11.0 ^ permalink raw reply related [flat|nested] 70+ messages in thread
* [PATCH v3 2/3] secure_seq: use siphash24 instead of md5_transform 2016-12-14 18:46 ` [PATCH v3 1/3] " Jason A. Donenfeld @ 2016-12-14 18:46 ` Jason A. Donenfeld 2016-12-14 21:44 ` kbuild test robot 2016-12-14 18:46 ` [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long Jason A. Donenfeld ` (3 subsequent siblings) 4 siblings, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 18:46 UTC (permalink / raw) To: Netdev, kernel-hardening, LKML, linux-crypto Cc: Jason A. Donenfeld, Andi Kleen, David Miller, David Laight This gives a clear speed and security improvement. Siphash is both faster and is more solid crypto than the aging MD5. Rather than manually filling MD5 buffers, we simply create a layout by a simple anonymous struct, for which gcc generates rather efficient code. Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> Cc: Andi Kleen <ak@linux.intel.com> Cc: David Miller <davem@davemloft.net> Cc: David Laight <David.Laight@aculab.com> --- Changes from v2->v3: - Structs are no longer packed, to mitigate slow byte-by-byte assignment. - A typo has been fixed in the port number assignment. net/core/secure_seq.c | 166 ++++++++++++++++++++++++++------------------------ 1 file changed, 85 insertions(+), 81 deletions(-) diff --git a/net/core/secure_seq.c b/net/core/secure_seq.c index 88a8e429fc3e..00eb141c981b 100644 --- a/net/core/secure_seq.c +++ b/net/core/secure_seq.c @@ -1,3 +1,5 @@ +/* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. */ + #include <linux/kernel.h> #include <linux/init.h> #include <linux/cryptohash.h> @@ -8,14 +10,14 @@ #include <linux/ktime.h> #include <linux/string.h> #include <linux/net.h> - +#include <linux/siphash.h> #include <net/secure_seq.h> #if IS_ENABLED(CONFIG_IPV6) || IS_ENABLED(CONFIG_INET) +#include <linux/in6.h> #include <net/tcp.h> -#define NET_SECRET_SIZE (MD5_MESSAGE_BYTES / 4) -static u32 net_secret[NET_SECRET_SIZE] ____cacheline_aligned; +static u8 net_secret[SIPHASH24_KEY_LEN] __aligned(SIPHASH24_ALIGNMENT); static __always_inline void net_secret_init(void) { @@ -44,44 +46,41 @@ static u32 seq_scale(u32 seq) u32 secure_tcpv6_sequence_number(const __be32 *saddr, const __be32 *daddr, __be16 sport, __be16 dport, u32 *tsoff) { - u32 secret[MD5_MESSAGE_BYTES / 4]; - u32 hash[MD5_DIGEST_WORDS]; - u32 i; - + const struct { + struct in6_addr saddr; + struct in6_addr daddr; + __be16 sport; + __be16 dport; + char end[]; + } __aligned(SIPHASH24_ALIGNMENT) combined = { + .saddr = *(struct in6_addr *)saddr, + .daddr = *(struct in6_addr *)daddr, + .sport = sport, + .dport = dport + }; + u64 hash; net_secret_init(); - memcpy(hash, saddr, 16); - for (i = 0; i < 4; i++) - secret[i] = net_secret[i] + (__force u32)daddr[i]; - secret[4] = net_secret[4] + - (((__force u16)sport << 16) + (__force u16)dport); - for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++) - secret[i] = net_secret[i]; - - md5_transform(hash, secret); - - *tsoff = sysctl_tcp_timestamps == 1 ? hash[1] : 0; - return seq_scale(hash[0]); + hash = siphash24((const u8 *)&combined, offsetof(typeof(combined), end), net_secret); + *tsoff = sysctl_tcp_timestamps == 1 ? (hash >> 32) : 0; + return seq_scale(hash); } EXPORT_SYMBOL(secure_tcpv6_sequence_number); u32 secure_ipv6_port_ephemeral(const __be32 *saddr, const __be32 *daddr, __be16 dport) { - u32 secret[MD5_MESSAGE_BYTES / 4]; - u32 hash[MD5_DIGEST_WORDS]; - u32 i; - + const struct { + struct in6_addr saddr; + struct in6_addr daddr; + __be16 dport; + char end[]; + } __aligned(SIPHASH24_ALIGNMENT) combined = { + .saddr = *(struct in6_addr *)saddr, + .daddr = *(struct in6_addr *)daddr, + .dport = dport + }; net_secret_init(); - memcpy(hash, saddr, 16); - for (i = 0; i < 4; i++) - secret[i] = net_secret[i] + (__force u32) daddr[i]; - secret[4] = net_secret[4] + (__force u32)dport; - for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++) - secret[i] = net_secret[i]; - - md5_transform(hash, secret); - - return hash[0]; + return siphash24((const u8 *)&combined, offsetof(typeof(combined), end), net_secret); } EXPORT_SYMBOL(secure_ipv6_port_ephemeral); #endif @@ -91,33 +90,39 @@ EXPORT_SYMBOL(secure_ipv6_port_ephemeral); u32 secure_tcp_sequence_number(__be32 saddr, __be32 daddr, __be16 sport, __be16 dport, u32 *tsoff) { - u32 hash[MD5_DIGEST_WORDS]; - + const struct { + __be32 saddr; + __be32 daddr; + __be16 sport; + __be16 dport; + char end[]; + } __aligned(SIPHASH24_ALIGNMENT) combined = { + .saddr = saddr, + .daddr = daddr, + .sport = sport, + .dport = dport + }; + u64 hash; net_secret_init(); - hash[0] = (__force u32)saddr; - hash[1] = (__force u32)daddr; - hash[2] = ((__force u16)sport << 16) + (__force u16)dport; - hash[3] = net_secret[15]; - - md5_transform(hash, net_secret); - - *tsoff = sysctl_tcp_timestamps == 1 ? hash[1] : 0; - return seq_scale(hash[0]); + hash = siphash24((const u8 *)&combined, offsetof(typeof(combined), end), net_secret); + *tsoff = sysctl_tcp_timestamps == 1 ? (hash >> 32) : 0; + return seq_scale(hash); } u32 secure_ipv4_port_ephemeral(__be32 saddr, __be32 daddr, __be16 dport) { - u32 hash[MD5_DIGEST_WORDS]; - + const struct { + __be32 saddr; + __be32 daddr; + __be16 dport; + char end[]; + } __aligned(SIPHASH24_ALIGNMENT) combined = { + .saddr = saddr, + .daddr = daddr, + .dport = dport + }; net_secret_init(); - hash[0] = (__force u32)saddr; - hash[1] = (__force u32)daddr; - hash[2] = (__force u32)dport ^ net_secret[14]; - hash[3] = net_secret[15]; - - md5_transform(hash, net_secret); - - return hash[0]; + return siphash24((const u8 *)&combined, offsetof(typeof(combined), end), net_secret); } EXPORT_SYMBOL_GPL(secure_ipv4_port_ephemeral); #endif @@ -126,21 +131,23 @@ EXPORT_SYMBOL_GPL(secure_ipv4_port_ephemeral); u64 secure_dccp_sequence_number(__be32 saddr, __be32 daddr, __be16 sport, __be16 dport) { - u32 hash[MD5_DIGEST_WORDS]; + const struct { + __be32 saddr; + __be32 daddr; + __be16 sport; + __be16 dport; + char end[]; + } __aligned(SIPHASH24_ALIGNMENT) combined = { + .saddr = saddr, + .daddr = daddr, + .sport = sport, + .dport = dport + }; u64 seq; - net_secret_init(); - hash[0] = (__force u32)saddr; - hash[1] = (__force u32)daddr; - hash[2] = ((__force u16)sport << 16) + (__force u16)dport; - hash[3] = net_secret[15]; - - md5_transform(hash, net_secret); - - seq = hash[0] | (((u64)hash[1]) << 32); + seq = siphash24((const u8 *)&combined, offsetof(typeof(combined), end), net_secret); seq += ktime_get_real_ns(); seq &= (1ull << 48) - 1; - return seq; } EXPORT_SYMBOL(secure_dccp_sequence_number); @@ -149,26 +156,23 @@ EXPORT_SYMBOL(secure_dccp_sequence_number); u64 secure_dccpv6_sequence_number(__be32 *saddr, __be32 *daddr, __be16 sport, __be16 dport) { - u32 secret[MD5_MESSAGE_BYTES / 4]; - u32 hash[MD5_DIGEST_WORDS]; + const struct { + struct in6_addr saddr; + struct in6_addr daddr; + __be16 sport; + __be16 dport; + char end[]; + } __aligned(SIPHASH24_ALIGNMENT) combined = { + .saddr = *(struct in6_addr *)saddr, + .daddr = *(struct in6_addr *)daddr, + .sport = sport, + .dport = dport + }; u64 seq; - u32 i; - net_secret_init(); - memcpy(hash, saddr, 16); - for (i = 0; i < 4; i++) - secret[i] = net_secret[i] + (__force u32)daddr[i]; - secret[4] = net_secret[4] + - (((__force u16)sport << 16) + (__force u16)dport); - for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++) - secret[i] = net_secret[i]; - - md5_transform(hash, secret); - - seq = hash[0] | (((u64)hash[1]) << 32); + seq = siphash24((const u8 *)&combined, offsetof(typeof(combined), end), net_secret); seq += ktime_get_real_ns(); seq &= (1ull << 48) - 1; - return seq; } EXPORT_SYMBOL(secure_dccpv6_sequence_number); -- 2.11.0 ^ permalink raw reply related [flat|nested] 70+ messages in thread
* Re: [PATCH v3 2/3] secure_seq: use siphash24 instead of md5_transform 2016-12-14 18:46 ` [PATCH v3 2/3] secure_seq: use siphash24 instead of md5_transform Jason A. Donenfeld @ 2016-12-14 21:44 ` kbuild test robot 0 siblings, 0 replies; 70+ messages in thread From: kbuild test robot @ 2016-12-14 21:44 UTC (permalink / raw) To: Jason A. Donenfeld Cc: kbuild-all, Netdev, kernel-hardening, LKML, linux-crypto, Jason A. Donenfeld, Andi Kleen, David Miller, David Laight [-- Attachment #1: Type: text/plain, Size: 1635 bytes --] Hi Jason, [auto build test ERROR on linus/master] [also build test ERROR on next-20161214] [cannot apply to v4.9] [if your patch is applied to the wrong git tree, please drop us a note to help improve the system] url: https://github.com/0day-ci/linux/commits/Jason-A-Donenfeld/siphash-add-cryptographically-secure-hashtable-function/20161215-041458 config: openrisc-or1ksim_defconfig (attached as .config) compiler: or32-linux-gcc (GCC) 4.5.1-or32-1.0rc1 reproduce: wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross # save the attached .config to linux build tree make.cross ARCH=openrisc All errors (new ones prefixed by >>): >> net/core/secure_seq.c:20:1: error: requested alignment is not a constant net/core/secure_seq.c: In function 'secure_tcp_sequence_number': net/core/secure_seq.c:99:2: error: requested alignment is not a constant net/core/secure_seq.c: In function 'secure_ipv4_port_ephemeral': net/core/secure_seq.c:119:2: error: requested alignment is not a constant vim +20 net/core/secure_seq.c 14 #include <net/secure_seq.h> 15 16 #if IS_ENABLED(CONFIG_IPV6) || IS_ENABLED(CONFIG_INET) 17 #include <linux/in6.h> 18 #include <net/tcp.h> 19 > 20 static u8 net_secret[SIPHASH24_KEY_LEN] __aligned(SIPHASH24_ALIGNMENT); 21 22 static __always_inline void net_secret_init(void) 23 { --- 0-DAY kernel test infrastructure Open Source Technology Center https://lists.01.org/pipermail/kbuild-all Intel Corporation [-- Attachment #2: .config.gz --] [-- Type: application/gzip, Size: 7325 bytes --] ^ permalink raw reply [flat|nested] 70+ messages in thread
* [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long 2016-12-14 18:46 ` [PATCH v3 1/3] " Jason A. Donenfeld 2016-12-14 18:46 ` [PATCH v3 2/3] secure_seq: use siphash24 instead of md5_transform Jason A. Donenfeld @ 2016-12-14 18:46 ` Jason A. Donenfeld 2016-12-14 21:56 ` kbuild test robot ` (2 more replies) 2016-12-14 19:18 ` [PATCH v3 1/3] siphash: add cryptographically secure hashtable function Tom Herbert ` (2 subsequent siblings) 4 siblings, 3 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 18:46 UTC (permalink / raw) To: Netdev, kernel-hardening, LKML, linux-crypto Cc: Jason A. Donenfeld, Jean-Philippe Aumasson, Ted Tso This duplicates the current algorithm for get_random_int/long, but uses siphash24 instead. This comes with several benefits. It's certainly faster and more cryptographically secure than MD5. This patch also hashes the pid, entropy, and timestamp as fixed width fields, in order to increase diffusion. The previous md5 algorithm used a per-cpu md5 state, which caused successive calls to the function to chain upon each other. While it's not entirely clear that this kind of chaining is absolutely necessary when using a secure PRF like siphash24, it can't hurt, and the timing of the call chain does add a degree of natural entropy. So, in keeping with this design, instead of the massive per-cpu 64-byte md5 state, there is instead a per-cpu previously returned value for chaining. Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> Cc: Ted Tso <tytso@mit.edu> --- Changes from v2->v3: - Structs are no longer packed, to mitigate slow byte-by-byte assignment. drivers/char/random.c | 52 ++++++++++++++++++++++++++++++++------------------- 1 file changed, 33 insertions(+), 19 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d6876d506220..b1c2e3b26430 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -262,6 +262,7 @@ #include <linux/syscalls.h> #include <linux/completion.h> #include <linux/uuid.h> +#include <linux/siphash.h> #include <crypto/chacha20.h> #include <asm/processor.h> @@ -2042,7 +2043,7 @@ struct ctl_table random_table[] = { }; #endif /* CONFIG_SYSCTL */ -static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned; +static u8 random_int_secret[SIPHASH24_KEY_LEN] __aligned(SIPHASH24_ALIGNMENT); int random_int_secret_init(void) { @@ -2050,8 +2051,7 @@ int random_int_secret_init(void) return 0; } -static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash) - __aligned(sizeof(unsigned long)); +static DEFINE_PER_CPU(u64, get_random_int_chaining); /* * Get a random word for internal kernel use only. Similar to urandom but @@ -2061,19 +2061,26 @@ static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash) */ unsigned int get_random_int(void) { - __u32 *hash; unsigned int ret; + struct { + u64 chaining; + unsigned long ts; + unsigned long entropy; + pid_t pid; + char end[]; + } __aligned(SIPHASH24_ALIGNMENT) combined; + u64 *chaining; if (arch_get_random_int(&ret)) return ret; - hash = get_cpu_var(get_random_int_hash); - - hash[0] += current->pid + jiffies + random_get_entropy(); - md5_transform(hash, random_int_secret); - ret = hash[0]; - put_cpu_var(get_random_int_hash); - + chaining = get_cpu_ptr(&get_random_int_chaining); + combined.chaining = *chaining; + combined.ts = jiffies; + combined.entropy = random_get_entropy(); + combined.pid = current->pid; + ret = *chaining = siphash24((u8 *)&combined, offsetof(typeof(combined), end), random_int_secret); + put_cpu_ptr(chaining); return ret; } EXPORT_SYMBOL(get_random_int); @@ -2083,19 +2090,26 @@ EXPORT_SYMBOL(get_random_int); */ unsigned long get_random_long(void) { - __u32 *hash; unsigned long ret; + struct { + u64 chaining; + unsigned long ts; + unsigned long entropy; + pid_t pid; + char end[]; + } __aligned(SIPHASH24_ALIGNMENT) combined; + u64 *chaining; if (arch_get_random_long(&ret)) return ret; - hash = get_cpu_var(get_random_int_hash); - - hash[0] += current->pid + jiffies + random_get_entropy(); - md5_transform(hash, random_int_secret); - ret = *(unsigned long *)hash; - put_cpu_var(get_random_int_hash); - + chaining = get_cpu_ptr(&get_random_int_chaining); + combined.chaining = *chaining; + combined.ts = jiffies; + combined.entropy = random_get_entropy(); + combined.pid = current->pid; + ret = *chaining = siphash24((u8 *)&combined, offsetof(typeof(combined), end), random_int_secret); + put_cpu_ptr(chaining); return ret; } EXPORT_SYMBOL(get_random_long); -- 2.11.0 ^ permalink raw reply related [flat|nested] 70+ messages in thread
* Re: [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long 2016-12-14 18:46 ` [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long Jason A. Donenfeld @ 2016-12-14 21:56 ` kbuild test robot 2016-12-14 21:57 ` kbuild test robot 2016-12-15 10:14 ` David Laight 2 siblings, 0 replies; 70+ messages in thread From: kbuild test robot @ 2016-12-14 21:56 UTC (permalink / raw) To: Jason A. Donenfeld Cc: kbuild-all, Netdev, kernel-hardening, LKML, linux-crypto, Jason A. Donenfeld, Jean-Philippe Aumasson, Ted Tso [-- Attachment #1: Type: text/plain, Size: 1583 bytes --] Hi Jason, [auto build test ERROR on linus/master] [also build test ERROR on next-20161214] [cannot apply to v4.9] [if your patch is applied to the wrong git tree, please drop us a note to help improve the system] url: https://github.com/0day-ci/linux/commits/Jason-A-Donenfeld/siphash-add-cryptographically-secure-hashtable-function/20161215-041458 config: i386-randconfig-i1-201650 (attached as .config) compiler: gcc-4.8 (Debian 4.8.4-1) 4.8.4 reproduce: # save the attached .config to linux build tree make ARCH=i386 All errors (new ones prefixed by >>): >> drivers/char/random.c:2046:1: error: requested alignment is not an integer constant static u8 random_int_secret[SIPHASH24_KEY_LEN] __aligned(SIPHASH24_ALIGNMENT); ^ drivers/char/random.c: In function 'get_random_int': drivers/char/random.c:2071:2: error: requested alignment is not an integer constant } __aligned(SIPHASH24_ALIGNMENT) combined; ^ drivers/char/random.c: In function 'get_random_long': drivers/char/random.c:2100:2: error: requested alignment is not an integer constant } __aligned(SIPHASH24_ALIGNMENT) combined; ^ vim +2046 drivers/char/random.c 2040 }, 2041 #endif 2042 { } 2043 }; 2044 #endif /* CONFIG_SYSCTL */ 2045 > 2046 static u8 random_int_secret[SIPHASH24_KEY_LEN] __aligned(SIPHASH24_ALIGNMENT); 2047 2048 int random_int_secret_init(void) 2049 { --- 0-DAY kernel test infrastructure Open Source Technology Center https://lists.01.org/pipermail/kbuild-all Intel Corporation [-- Attachment #2: .config.gz --] [-- Type: application/gzip, Size: 26712 bytes --] ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long 2016-12-14 18:46 ` [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long Jason A. Donenfeld 2016-12-14 21:56 ` kbuild test robot @ 2016-12-14 21:57 ` kbuild test robot 2016-12-15 10:14 ` David Laight 2 siblings, 0 replies; 70+ messages in thread From: kbuild test robot @ 2016-12-14 21:57 UTC (permalink / raw) To: Jason A. Donenfeld Cc: kbuild-all, Netdev, kernel-hardening, LKML, linux-crypto, Jason A. Donenfeld, Jean-Philippe Aumasson, Ted Tso [-- Attachment #1: Type: text/plain, Size: 1528 bytes --] Hi Jason, [auto build test ERROR on linus/master] [also build test ERROR on next-20161214] [cannot apply to v4.9] [if your patch is applied to the wrong git tree, please drop us a note to help improve the system] url: https://github.com/0day-ci/linux/commits/Jason-A-Donenfeld/siphash-add-cryptographically-secure-hashtable-function/20161215-041458 config: openrisc-or1ksim_defconfig (attached as .config) compiler: or32-linux-gcc (GCC) 4.5.1-or32-1.0rc1 reproduce: wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross # save the attached .config to linux build tree make.cross ARCH=openrisc All errors (new ones prefixed by >>): >> drivers/char/random.c:2046:1: error: requested alignment is not a constant drivers/char/random.c: In function 'get_random_int': drivers/char/random.c:2071:2: error: requested alignment is not a constant drivers/char/random.c: In function 'get_random_long': drivers/char/random.c:2100:2: error: requested alignment is not a constant vim +2046 drivers/char/random.c 2040 }, 2041 #endif 2042 { } 2043 }; 2044 #endif /* CONFIG_SYSCTL */ 2045 > 2046 static u8 random_int_secret[SIPHASH24_KEY_LEN] __aligned(SIPHASH24_ALIGNMENT); 2047 2048 int random_int_secret_init(void) 2049 { --- 0-DAY kernel test infrastructure Open Source Technology Center https://lists.01.org/pipermail/kbuild-all Intel Corporation [-- Attachment #2: .config.gz --] [-- Type: application/gzip, Size: 7325 bytes --] ^ permalink raw reply [flat|nested] 70+ messages in thread
* RE: [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long 2016-12-14 18:46 ` [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long Jason A. Donenfeld 2016-12-14 21:56 ` kbuild test robot 2016-12-14 21:57 ` kbuild test robot @ 2016-12-15 10:14 ` David Laight 2016-12-15 18:51 ` Jason A. Donenfeld 2 siblings, 1 reply; 70+ messages in thread From: David Laight @ 2016-12-15 10:14 UTC (permalink / raw) To: 'Jason A. Donenfeld', Netdev, kernel-hardening, LKML, linux-crypto Cc: Jean-Philippe Aumasson, Ted Tso From: Behalf Of Jason A. Donenfeld > Sent: 14 December 2016 18:46 ... > + ret = *chaining = siphash24((u8 *)&combined, offsetof(typeof(combined), end), If you make the first argument 'const void *' you won't need the cast on every call. I'd also suggest making the key u64[2]. David ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long 2016-12-15 10:14 ` David Laight @ 2016-12-15 18:51 ` Jason A. Donenfeld 0 siblings, 0 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-15 18:51 UTC (permalink / raw) To: David Laight Cc: Netdev, kernel-hardening, LKML, linux-crypto, Jean-Philippe Aumasson, Ted Tso Hi David, On Thu, Dec 15, 2016 at 11:14 AM, David Laight <David.Laight@aculab.com> wrote: > From: Behalf Of Jason A. Donenfeld >> Sent: 14 December 2016 18:46 > ... >> + ret = *chaining = siphash24((u8 *)&combined, offsetof(typeof(combined), end), > > If you make the first argument 'const void *' you won't need the cast > on every call. > > I'd also suggest making the key u64[2]. I'll do both. Thanks for the suggestion. Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 18:46 ` [PATCH v3 1/3] " Jason A. Donenfeld 2016-12-14 18:46 ` [PATCH v3 2/3] secure_seq: use siphash24 instead of md5_transform Jason A. Donenfeld 2016-12-14 18:46 ` [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long Jason A. Donenfeld @ 2016-12-14 19:18 ` Tom Herbert 2016-12-14 19:35 ` Jason A. Donenfeld 2016-12-14 21:15 ` kbuild test robot 2016-12-15 1:46 ` [PATCH v4 1/4] " Jason A. Donenfeld 4 siblings, 1 reply; 70+ messages in thread From: Tom Herbert @ 2016-12-14 19:18 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Netdev, kernel-hardening, LKML, linux-crypto, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight On Wed, Dec 14, 2016 at 10:46 AM, Jason A. Donenfeld <Jason@zx2c4.com> 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. > "super fast" is relative. My quick test shows that this faster than Toeplitz (good, but not exactly hard to achieve), but is about 4x slower than jhash. > 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? > I don't think we need advertising nor a lesson on hashing. It would be much more useful if you just point us to the paper on siphash (which I assume I http://cr.yp.to/siphash/siphash-20120918.pdf ?). > 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. > Key rotation is important anyway, without any key rotation even if the key is compromised in siphash by some external means we would have an insecure hash until the system reboots. > (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. > > Secondly, a few places are using MD5 for creating secure sequence > numbers, port numbers, or fast random numbers. Siphash is a faster, more > fittting, and more secure replacement for MD5 in those situations. > > 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. > Maybe so, but we need to do due diligence before considering adopting siphash as the primary hashing in the network stack. Consider that we may very well perform a hash over L4 tuples on _every_ packet. We've done a good job at limiting this to be at most one hash per packet, but nevertheless the performance of the hash function must be take into account. A few points: 1) My quick test shows siphash is about four times more expensive than jhash. On my test system, computing a hash over IPv4 tuple (two 32 bit addresses and 2 16 bit source ports) is 6.9 nsecs in Jenkins hash, 33 nsecs with siphash. Given that we have eliminated most of the packet header hashes this might be tolerable, but still should be looking at ways to optimize. 2) I like moving to use u64 (quad words) in the hash, this is an improvement over Jenkins which is based on 32 bit words. If we put this in the kernel we probably want to have several variants of siphash for specific sizes (e.g. siphash1, siphash2, siphash2, siphashn for hash over one, two, three, or n sixty four bit words). 3) I also tested siphash distribution and Avalanche Effect (these really should have been covered in the paper :-( ). Both of these are good with siphash, in fact almost have identical characteristics to Jenkins hash. Tom > Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> > Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> > Cc: Daniel J. Bernstein <djb@cr.yp.to> > Cc: Linus Torvalds <torvalds@linux-foundation.org> > Cc: Eric Biggers <ebiggers3@gmail.com> > Cc: David Laight <David.Laight@aculab.com> > --- > Changes from v2->v3: > > - There is now a fast aligned version of the function and a not-as-fast > unaligned version. The requirements for each have been documented in > a docbook-style comment. As well, the header now contains a constant > for the expected alignment. > > - The test suite has been updated to check both the unaligned and aligned > version of the function. > > include/linux/siphash.h | 30 ++++++++++ > lib/Kconfig.debug | 6 +- > lib/Makefile | 5 +- > lib/siphash.c | 153 ++++++++++++++++++++++++++++++++++++++++++++++++ > lib/test_siphash.c | 85 +++++++++++++++++++++++++++ > 5 files changed, 274 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..82dc1a911a2e > --- /dev/null > +++ b/include/linux/siphash.h > @@ -0,0 +1,30 @@ > +/* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com> > + * > + * 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, > + SIPHASH24_ALIGNMENT = 8 > +}; > + > +u64 siphash24(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]); > + > +#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS > +static inline u64 siphash24_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]) > +{ > + return siphash24(data, len, key); > +} > +#else > +u64 siphash24_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH24_KEY_LEN]); > +#endif > + > +#endif /* _LINUX_SIPHASH_H */ > diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug > index e6327d102184..32bbf689fc46 100644 > --- a/lib/Kconfig.debug > +++ b/lib/Kconfig.debug > @@ -1843,9 +1843,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..32acdc26234f > --- /dev/null > +++ b/lib/siphash.c > @@ -0,0 +1,153 @@ > +/* Copyright (C) 2015-2016 Jason A. Donenfeld <Jason@zx2c4.com> > + * Copyright (C) 2012-2014 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> > + * Copyright (C) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to> > + * > + * 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) > + > +static inline u16 le16_to_cpuvp(const void *p) > +{ > + return le16_to_cpup(p); > +} > +static inline u32 le32_to_cpuvp(const void *p) > +{ > + return le32_to_cpup(p); > +} > +static inline u64 le64_to_cpuvp(const void *p) > +{ > + return le64_to_cpup(p); > +} > + > +/** > + * siphash24 - compute 64-bit siphash24 PRF value > + * @data: buffer to hash, must be aligned to SIPHASH24_ALIGNMENT > + * @size: size of @data > + * @key: key buffer of size SIPHASH24_KEY_LEN, must be aligned to SIPHASH24_ALIGNMENT > + */ > +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; > + } > +#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64 > + if (left) > + b |= le64_to_cpu((__force __le64)(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 |= le32_to_cpuvp(data); break; > + case 3: b |= ((u64)data[2]) << 16; > + case 2: b |= le16_to_cpuvp(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); > + > +#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS > +/** > + * siphash24 - compute 64-bit siphash24 PRF value, without alignment requirements > + * @data: buffer to hash > + * @size: size of @data > + * @key: key buffer of size SIPHASH24_KEY_LEN > + */ > +u64 siphash24_unaligned(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((__force __le64)(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_unaligned); > +#endif > diff --git a/lib/test_siphash.c b/lib/test_siphash.c > new file mode 100644 > index 000000000000..69ac94dec366 > --- /dev/null > +++ b/lib/test_siphash.c > @@ -0,0 +1,85 @@ > +/* Test cases for siphash.c > + * > + * Copyright (C) 2015-2016 Jason A. Donenfeld <Jason@zx2c4.com> > + * > + * 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] __aligned(SIPHASH24_ALIGNMENT); > + u8 k[16] __aligned(SIPHASH24_ALIGNMENT); > + u8 in_unaligned[65]; > + u8 k_unaligned[65]; > + u8 i; > + int ret = 0; > + > + for (i = 0; i < 16; ++i) { > + k[i] = i; > + k_unaligned[i + 1] = i; > + } > + for (i = 0; i < 64; ++i) { > + in[i] = i; > + in_unaligned[i + 1] = i; > + if (siphash24(in, i, k) != test_vectors[i]) { > + pr_info("self-test aligned %u: FAIL\n", i + 1); > + ret = -EINVAL; > + } > + if (siphash24_unaligned(in_unaligned + 1, i, k_unaligned + 1) != test_vectors[i]) { > + pr_info("self-test unaligned %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 <Jason@zx2c4.com>"); > +MODULE_LICENSE("Dual BSD/GPL"); > -- > 2.11.0 > ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 19:18 ` [PATCH v3 1/3] siphash: add cryptographically secure hashtable function Tom Herbert @ 2016-12-14 19:35 ` Jason A. Donenfeld 2016-12-14 20:55 ` Jason A. Donenfeld 0 siblings, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 19:35 UTC (permalink / raw) To: Tom Herbert Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight Hi Tom, On Wed, Dec 14, 2016 at 8:18 PM, Tom Herbert <tom@herbertland.com> wrote: > "super fast" is relative. My quick test shows that this faster than > Toeplitz (good, but not exactly hard to achieve), but is about 4x > slower than jhash. Fast relative to other cryptographically secure PRFs. >> 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? > I don't think we need advertising nor a lesson on hashing. It would be > much more useful if you just point us to the paper on siphash (which I > assume I http://cr.yp.to/siphash/siphash-20120918.pdf ?). Ugh. Sorry. It definitely wasn't my intention to give an uninvited lesson or an annoying advert. For the former, I didn't want to make any expectations about fields of knowledge, because I honest have no idea. For the latter, I wrote that sentence to indicate that siphash isn't just some newfangled hipster function, but something useful and well established. I didn't mean it as a form of advertising. My apologies if I've offended your sensibilities. That cr.yp.to link is fine, or https://131002.net/siphash/siphash.pdf I believe. > Key rotation is important anyway, without any key rotation even if the > key is compromised in siphash by some external means we would have an > insecure hash until the system reboots. I'm a bit surprised to read this. I've never designed a system to be secure even in the event of remote arbitrary kernel memory disclosure, and I wasn't aware this was generally considered an architectural requirement or Linux. In any case, if you want this, I suppose you can have it with siphash too. > Maybe so, but we need to do due diligence before considering adopting > siphash as the primary hashing in the network stack. Consider that we > may very well perform a hash over L4 tuples on _every_ packet. We've > done a good job at limiting this to be at most one hash per packet, > but nevertheless the performance of the hash function must be take > into account. I agree with you. It seems like each case is going to needed to be measured on a case by case basis. In this series I make the first use of siphash in the secure sequence generation and get_random_int/long, where siphash replaces md5, so there's a pretty clear performance in. But for the jhash replacements indeed things are going to need to be individually evaluated. > 1) My quick test shows siphash is about four times more expensive than > jhash. On my test system, computing a hash over IPv4 tuple (two 32 bit > addresses and 2 16 bit source ports) is 6.9 nsecs in Jenkins hash, 33 > nsecs with siphash. Given that we have eliminated most of the packet > header hashes this might be tolerable, but still should be looking at > ways to optimize. > 2) I like moving to use u64 (quad words) in the hash, this is an > improvement over Jenkins which is based on 32 bit words. If we put > this in the kernel we probably want to have several variants of > siphash for specific sizes (e.g. siphash1, siphash2, siphash2, > siphashn for hash over one, two, three, or n sixty four bit words). I think your suggestion for (2) will contribute to further optimizations for (1). In v2, I had another patch in there adding siphash_1word, siphash_2words, etc, like jhash, but I implemented it by taking u32 variables and then just concatenating these into a buffer and passing them to the main siphash function. I removed it from v3 because I thought that these kind of missed the whole point. In particular: a) siphash24_1word, siphash24_2words, siphash24_3words, etc should take u64, not u32, since that's what siphash operates on natively b) Rather than concatenating them in a buffer, I should write specializations of the siphash24 function _especially_ for these size inputs to avoid the copy and to reduce the book keeping. I'll add these functions to v4 implemented like that. Thanks for the useful feedback and benchmarks! Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 19:35 ` Jason A. Donenfeld @ 2016-12-14 20:55 ` Jason A. Donenfeld 2016-12-14 21:35 ` Tom Herbert 0 siblings, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 20:55 UTC (permalink / raw) To: Tom Herbert Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight Hey Tom, Just following up on what I mentioned in my last email... On Wed, Dec 14, 2016 at 8:35 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote: > I think your suggestion for (2) will contribute to further > optimizations for (1). In v2, I had another patch in there adding > siphash_1word, siphash_2words, etc, like jhash, but I implemented it > by taking u32 variables and then just concatenating these into a > buffer and passing them to the main siphash function. I removed it > from v3 because I thought that these kind of missed the whole point. > In particular: > > a) siphash24_1word, siphash24_2words, siphash24_3words, etc should > take u64, not u32, since that's what siphash operates on natively I implemented these here: https://git.zx2c4.com/linux-dev/commit/?h=siphash&id=4652b6f3643bdba217e2194d89661348bbac48a0 This will be part of the next version of the series I submit. It's not immediately clear that using it is strictly faster than the struct trick though. However, I'm not yet sure why this would be. Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 20:55 ` Jason A. Donenfeld @ 2016-12-14 21:35 ` Tom Herbert 2016-12-14 22:56 ` Jason A. Donenfeld 0 siblings, 1 reply; 70+ messages in thread From: Tom Herbert @ 2016-12-14 21:35 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight On Wed, Dec 14, 2016 at 12:55 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote: > Hey Tom, > > Just following up on what I mentioned in my last email... > > On Wed, Dec 14, 2016 at 8:35 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote: >> I think your suggestion for (2) will contribute to further >> optimizations for (1). In v2, I had another patch in there adding >> siphash_1word, siphash_2words, etc, like jhash, but I implemented it >> by taking u32 variables and then just concatenating these into a >> buffer and passing them to the main siphash function. I removed it >> from v3 because I thought that these kind of missed the whole point. >> In particular: >> >> a) siphash24_1word, siphash24_2words, siphash24_3words, etc should >> take u64, not u32, since that's what siphash operates on natively > > I implemented these here: > https://git.zx2c4.com/linux-dev/commit/?h=siphash&id=4652b6f3643bdba217e2194d89661348bbac48a0 > Those look good, although I would probably just do 1,2,3 words and then have a function that takes n words like jhash. Might want to call these dword to distinguish from 32 bit words in jhash. Also, what is the significance of "24" in the function and constant names? Can we just drop that and call this siphash? Tom > This will be part of the next version of the series I submit. It's not > immediately clear that using it is strictly faster than the struct > trick though. However, I'm not yet sure why this would be. > > Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 21:35 ` Tom Herbert @ 2016-12-14 22:56 ` Jason A. Donenfeld 2016-12-14 23:14 ` Tom Herbert 2016-12-14 23:30 ` Linus Torvalds 0 siblings, 2 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 22:56 UTC (permalink / raw) To: Tom Herbert Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight Hey Tom, On Wed, Dec 14, 2016 at 10:35 PM, Tom Herbert <tom@herbertland.com> wrote: > Those look good, although I would probably just do 1,2,3 words and > then have a function that takes n words like jhash. Might want to call > these dword to distinguish from 32 bit words in jhash. So actually jhash_Nwords makes no sense, since it takes dwords (32-bits) not words (16-bits). The siphash analog should be called siphash24_Nqwords. I think what I'll do is change what I already have to: siphash24_1qword siphash24_2qword siphash24_3qword siphash24_4qword And then add some static inline helpers to assist with smaller u32s like ipv4 addresses called: siphash24_2dword siphash24_4dword siphash24_6dword siphash24_8dword While we're having something new, might as well call it the right thing. > Also, what is the significance of "24" in the function and constant > names? Can we just drop that and call this siphash? SipHash is actually a family of PRFs, differentiated by the number of SIPROUNDs after each 64-bit input is processed and the number of SIPROUNDs at the very end of the function. The best trade-off of speed and security for kernel usage is 2 rounds after each 64-bit input and 4 rounds at the end of the function. This doesn't fall to any known cryptanalysis and it's very fast. ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 22:56 ` Jason A. Donenfeld @ 2016-12-14 23:14 ` Tom Herbert 2016-12-14 23:17 ` Jason A. Donenfeld 2016-12-14 23:30 ` Linus Torvalds 1 sibling, 1 reply; 70+ messages in thread From: Tom Herbert @ 2016-12-14 23:14 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight On Wed, Dec 14, 2016 at 2:56 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote: > Hey Tom, > > On Wed, Dec 14, 2016 at 10:35 PM, Tom Herbert <tom@herbertland.com> wrote: >> Those look good, although I would probably just do 1,2,3 words and >> then have a function that takes n words like jhash. Might want to call >> these dword to distinguish from 32 bit words in jhash. > > So actually jhash_Nwords makes no sense, since it takes dwords > (32-bits) not words (16-bits). The siphash analog should be called > siphash24_Nqwords. > Yeah, that's a "bug" with jhash function names. > I think what I'll do is change what I already have to: > siphash24_1qword > siphash24_2qword > siphash24_3qword > siphash24_4qword > > And then add some static inline helpers to assist with smaller u32s > like ipv4 addresses called: > > siphash24_2dword > siphash24_4dword > siphash24_6dword > siphash24_8dword > > While we're having something new, might as well call it the right thing. > I'm confused, doesn't 2dword == 1qword? Anyway, I think the qword functions are good enough. If someone needs to hash over some odd length they can either put them in a structure padded to 64 bits or call the hash function that takes a byte length. > >> Also, what is the significance of "24" in the function and constant >> names? Can we just drop that and call this siphash? > > SipHash is actually a family of PRFs, differentiated by the number of > SIPROUNDs after each 64-bit input is processed and the number of > SIPROUNDs at the very end of the function. The best trade-off of speed > and security for kernel usage is 2 rounds after each 64-bit input and > 4 rounds at the end of the function. This doesn't fall to any known > cryptanalysis and it's very fast. I'd still drop the "24" unless you really think we're going to have multiple variants coming into the kernel. Tom ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 23:14 ` Tom Herbert @ 2016-12-14 23:17 ` Jason A. Donenfeld 2016-12-18 0:06 ` Christian Kujau 0 siblings, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 23:17 UTC (permalink / raw) To: Tom Herbert Cc: Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight Hey Tom, On Thu, Dec 15, 2016 at 12:14 AM, Tom Herbert <tom@herbertland.com> wrote: > I'm confused, doesn't 2dword == 1qword? Anyway, I think the qword > functions are good enough. If someone needs to hash over some odd > length they can either put them in a structure padded to 64 bits or > call the hash function that takes a byte length. Yes. Here's an example: static inline u64 siphash24_2dwords(const u32 a, const u32 b, const u8 key[SIPHASH24_KEY_LEN]) { return siphash24_1qword(((u64)b << 32) | a, key); } This winds up being extremely useful and syntactically convenient in a few places. Check out my git branch in about 10 minutes or wait for v4 to be posted tomorrow; these are nice helpers. > I'd still drop the "24" unless you really think we're going to have > multiple variants coming into the kernel. Okay. I don't have a problem with this, unless anybody has some reason to the contrary. Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 23:17 ` Jason A. Donenfeld @ 2016-12-18 0:06 ` Christian Kujau 0 siblings, 0 replies; 70+ messages in thread From: Christian Kujau @ 2016-12-18 0:06 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Tom Herbert, Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight On Thu, 15 Dec 2016, Jason A. Donenfeld wrote: > > I'd still drop the "24" unless you really think we're going to have > > multiple variants coming into the kernel. > > Okay. I don't have a problem with this, unless anybody has some reason > to the contrary. What if the 2/4-round version falls and we need more rounds to withstand future cryptoanalysis? We'd then have siphash_ and siphash48_ functions, no? My amateurish bike-shedding argument would be "let's keep the 24 then" :-) C. -- BOFH excuse #354: Chewing gum on /dev/sd3c ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 22:56 ` Jason A. Donenfeld 2016-12-14 23:14 ` Tom Herbert @ 2016-12-14 23:30 ` Linus Torvalds 2016-12-14 23:34 ` Jason A. Donenfeld 1 sibling, 1 reply; 70+ messages in thread From: Linus Torvalds @ 2016-12-14 23:30 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Tom Herbert, Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Eric Biggers, David Laight On Wed, Dec 14, 2016 at 2:56 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > So actually jhash_Nwords makes no sense, since it takes dwords > (32-bits) not words (16-bits). The siphash analog should be called > siphash24_Nqwords. No. The bug is talking about "words" in the first place. Depending on your background, a "word" can be generally be either 16 bits or 32 bits (or, in some cases, 18 bits). In theory, a 64-bit entity can be a "word" too, but pretty much nobody uses that. Even architectures that started out with a 64-bit register size and never had any smaller historical baggage (eg alpha) tend to call 32-bit entities "words". So 16 bits can be a word, but some people/architectures will call it a "half-word". To make matters even more confusing, a "quadword" is generally always 64 bits, regardless of the size of "word". So please try to avoid the use of "word" entirely. It's too ambiguous, and it's not even helpful as a "size of the native register". It's almost purely random. For the kernel, we tend use - uX for types that have specific sizes (X being the number of bits) - "[unsigned] long" for native register size But never "word". Linus ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 23:30 ` Linus Torvalds @ 2016-12-14 23:34 ` Jason A. Donenfeld 2016-12-15 0:10 ` Linus Torvalds 0 siblings, 1 reply; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 23:34 UTC (permalink / raw) To: Linus Torvalds Cc: Tom Herbert, Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Eric Biggers, David Laight Hey Linus, On Thu, Dec 15, 2016 at 12:30 AM, Linus Torvalds <torvalds@linux-foundation.org> wrote: > No. The bug is talking about "words" in the first place. > > Depending on your background, a "word" can be generally be either 16 > bits or 32 bits (or, in some cases, 18 bits). > > In theory, a 64-bit entity can be a "word" too, but pretty much nobody > uses that. Even architectures that started out with a 64-bit register > size and never had any smaller historical baggage (eg alpha) tend to > call 32-bit entities "words". > > So 16 bits can be a word, but some people/architectures will call it a > "half-word". > > To make matters even more confusing, a "quadword" is generally always > 64 bits, regardless of the size of "word". > > So please try to avoid the use of "word" entirely. It's too ambiguous, > and it's not even helpful as a "size of the native register". It's > almost purely random. > > For the kernel, we tend use > > - uX for types that have specific sizes (X being the number of bits) > > - "[unsigned] long" for native register size > > But never "word". The voice of reason. Have a desired name for this function family? siphash_3u64s siphash_3u64 siphash_three_u64 siphash_3sixityfourbitintegers Or does your reasonable dislike of "word" still allow for the use of dword and qword, so that the current function names of: siphash_3qwords siphash_6dwords are okay? Jason ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 23:34 ` Jason A. Donenfeld @ 2016-12-15 0:10 ` Linus Torvalds 2016-12-15 10:22 ` David Laight 0 siblings, 1 reply; 70+ messages in thread From: Linus Torvalds @ 2016-12-15 0:10 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Tom Herbert, Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Eric Biggers, David Laight On Wed, Dec 14, 2016 at 3:34 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > Or does your reasonable dislike of "word" still allow for the use of > dword and qword, so that the current function names of: dword really is confusing to people. If you have a MIPS background, it means 64 bits. While to people with Windows programming backgrounds it means 32 bits. Please try to avoid using it. As mentioned, I think almost everybody agrees on the "q" part being 64 bits, but that may just be me not having seen it in any other context. And before anybody points it out - yes, we already have lots of uses of "dword" in various places. But they tend to be mostly hardware-specific - either architectures or drivers. So I'd _prefer_ to try to keep "word" and "dword" away from generic helper routines. But it's not like anything is really black and white. Linus ^ permalink raw reply [flat|nested] 70+ messages in thread
* RE: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-15 0:10 ` Linus Torvalds @ 2016-12-15 10:22 ` David Laight 0 siblings, 0 replies; 70+ messages in thread From: David Laight @ 2016-12-15 10:22 UTC (permalink / raw) To: 'Linus Torvalds', Jason A. Donenfeld Cc: Tom Herbert, Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Eric Biggers From: Linus Torvalds > Sent: 15 December 2016 00:11 > On Wed, Dec 14, 2016 at 3:34 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > > > Or does your reasonable dislike of "word" still allow for the use of > > dword and qword, so that the current function names of: > > dword really is confusing to people. > > If you have a MIPS background, it means 64 bits. While to people with > Windows programming backgrounds it means 32 bits. Guess what a DWORD_PTR is on 64bit windows ... (it is an integer type). David ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 18:46 ` [PATCH v3 1/3] " Jason A. Donenfeld ` (2 preceding siblings ...) 2016-12-14 19:18 ` [PATCH v3 1/3] siphash: add cryptographically secure hashtable function Tom Herbert @ 2016-12-14 21:15 ` kbuild test robot 2016-12-14 21:21 ` Jason A. Donenfeld 2016-12-15 1:46 ` [PATCH v4 1/4] " Jason A. Donenfeld 4 siblings, 1 reply; 70+ messages in thread From: kbuild test robot @ 2016-12-14 21:15 UTC (permalink / raw) To: Jason A. Donenfeld Cc: kbuild-all, Netdev, kernel-hardening, LKML, linux-crypto, Jason A. Donenfeld, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight [-- Attachment #1: Type: text/plain, Size: 1420 bytes --] Hi Jason, [auto build test ERROR on linus/master] [also build test ERROR on v4.9 next-20161214] [if your patch is applied to the wrong git tree, please drop us a note to help improve the system] url: https://github.com/0day-ci/linux/commits/Jason-A-Donenfeld/siphash-add-cryptographically-secure-hashtable-function/20161215-041458 config: i386-randconfig-i1-201650 (attached as .config) compiler: gcc-4.8 (Debian 4.8.4-1) 4.8.4 reproduce: # save the attached .config to linux build tree make ARCH=i386 All errors (new ones prefixed by >>): lib/test_siphash.c: In function 'siphash_test_init': >> lib/test_siphash.c:49:2: error: requested alignment is not an integer constant u8 in[64] __aligned(SIPHASH24_ALIGNMENT); ^ lib/test_siphash.c:50:2: error: requested alignment is not an integer constant u8 k[16] __aligned(SIPHASH24_ALIGNMENT); ^ vim +49 lib/test_siphash.c 43 0x6ca4ecb15c5f91e1ULL, 0x9f626da15c9625f3ULL, 0xe51b38608ef25f57ULL, 44 0x958a324ceb064572ULL 45 }; 46 47 static int __init siphash_test_init(void) 48 { > 49 u8 in[64] __aligned(SIPHASH24_ALIGNMENT); 50 u8 k[16] __aligned(SIPHASH24_ALIGNMENT); 51 u8 in_unaligned[65]; 52 u8 k_unaligned[65]; --- 0-DAY kernel test infrastructure Open Source Technology Center https://lists.01.org/pipermail/kbuild-all Intel Corporation [-- Attachment #2: .config.gz --] [-- Type: application/gzip, Size: 26712 bytes --] ^ permalink raw reply [flat|nested] 70+ messages in thread
* Re: [PATCH v3 1/3] siphash: add cryptographically secure hashtable function 2016-12-14 21:15 ` kbuild test robot @ 2016-12-14 21:21 ` Jason A. Donenfeld 0 siblings, 0 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-14 21:21 UTC (permalink / raw) To: kbuild test robot Cc: kbuild-all, Netdev, kernel-hardening, LKML, Linux Crypto Mailing List, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight Interesting. Evidently gcc 4.8 doesn't like my use of: enum siphash_lengths { SIPHASH24_KEY_LEN = 16, SIPHASH24_ALIGNMENT = 8 }; I'll convert this to the more boring: #define SIPHASH24_KEY_LEN 16 #define SIPHASH24_ALIGNMENT 8 ^ permalink raw reply [flat|nested] 70+ messages in thread
* [PATCH v4 1/4] siphash: add cryptographically secure hashtable function 2016-12-14 18:46 ` [PATCH v3 1/3] " Jason A. Donenfeld ` (3 preceding siblings ...) 2016-12-14 21:15 ` kbuild test robot @ 2016-12-15 1:46 ` Jason A. Donenfeld 2016-12-15 1:46 ` [PATCH v4 2/4] siphash: add N[qd]word helpers Jason A. Donenfeld ` (3 more replies) 4 siblings, 4 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-15 1:46 UTC (permalink / raw) To: Netdev, kernel-hardening, LKML, linux-crypto Cc: Jason A. Donenfeld, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight 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. 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. Secondly, a few places are using MD5 for creating secure sequence numbers, port numbers, or fast random numbers. Siphash is a faster, more fitting, and more secure replacement for MD5 in those situations. 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 <Jason@zx2c4.com> Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> Cc: Daniel J. Bernstein <djb@cr.yp.to> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Eric Biggers <ebiggers3@gmail.com> Cc: David Laight <David.Laight@aculab.com> --- Changes from v3->v4: - Renamed from siphash24 to siphash. - Using macros instead of enums for old gcc. - Keys must now always be aligned, even for the unaligned data one, since generally these keys are just long term secrets which are easy to ensure are aligned anyway. include/linux/siphash.h | 30 ++++++++++ lib/Kconfig.debug | 6 +- lib/Makefile | 5 +- lib/siphash.c | 153 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/test_siphash.c | 84 ++++++++++++++++++++++++++ 5 files changed, 273 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..d0bcca7b992b --- /dev/null +++ b/include/linux/siphash.h @@ -0,0 +1,30 @@ +/* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. + * + * This file is provided under a dual BSD/GPLv2 license. + * + * SipHash: a fast short-input PRF + * https://131002.net/siphash/ + * + * This implementation is specifically for SipHash2-4. + */ + +#ifndef _LINUX_SIPHASH_H +#define _LINUX_SIPHASH_H + +#include <linux/types.h> + +#define SIPHASH_KEY_LEN 16 +#define SIPHASH_ALIGNMENT 8 + +u64 siphash(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN]); + +#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS +static inline u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN]) +{ + return siphash(data, len, key); +} +#else +u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN]); +#endif + +#endif /* _LINUX_SIPHASH_H */ diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index e6327d102184..32bbf689fc46 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1843,9 +1843,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..b500231f61cd --- /dev/null +++ b/lib/siphash.c @@ -0,0 +1,153 @@ +/* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. + * + * This file is provided under a dual BSD/GPLv2 license. + * + * SipHash: a fast short-input PRF + * https://131002.net/siphash/ + * + * This implementation is specifically for SipHash2-4. + */ + +#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 + +static inline u16 le16_to_cpuvp(const void *p) +{ + return le16_to_cpup(p); +} +static inline u32 le32_to_cpuvp(const void *p) +{ + return le32_to_cpup(p); +} +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) + +/** + * siphash - compute 64-bit siphash PRF value + * @data: buffer to hash, must be aligned to SIPHASH_ALIGNMENT + * @size: size of @data + * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT + */ +u64 siphash(const u8 *data, size_t len, const u8 key[SIPHASH_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; + } +#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64 + if (left) + b |= le64_to_cpu((__force __le64)(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 |= le32_to_cpuvp(data); break; + case 3: b |= ((u64)data[2]) << 16; + case 2: b |= le16_to_cpuvp(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(siphash); + +#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS +/** + * siphash - compute 64-bit siphash PRF value, without alignment requirements + * @data: buffer to hash + * @size: size of @data + * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT + */ +u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_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 = 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((__force __le64)(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_unaligned); +#endif diff --git a/lib/test_siphash.c b/lib/test_siphash.c new file mode 100644 index 000000000000..444725c7834f --- /dev/null +++ b/lib/test_siphash.c @@ -0,0 +1,84 @@ +/* Test cases for siphash.c + * + * Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. + * + * This file is provided under a dual BSD/GPLv2 license. + * + * SipHash: a fast short-input PRF + * https://131002.net/siphash/ + * + * This implementation is specifically for SipHash2-4. + */ + +#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] __aligned(SIPHASH_ALIGNMENT); + u8 k[16] __aligned(SIPHASH_ALIGNMENT); + u8 in_unaligned[65]; + u8 i; + int ret = 0; + + for (i = 0; i < 16; ++i) + k[i] = i; + for (i = 0; i < 64; ++i) { + in[i] = i; + in_unaligned[i + 1] = i; + if (siphash(in, i, k) != test_vectors[i]) { + pr_info("self-test aligned %u: FAIL\n", i + 1); + ret = -EINVAL; + } + if (siphash_unaligned(in_unaligned + 1, i, k) != test_vectors[i]) { + pr_info("self-test unaligned %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 <Jason@zx2c4.com>"); +MODULE_LICENSE("Dual BSD/GPL"); -- 2.11.0 ^ permalink raw reply related [flat|nested] 70+ messages in thread
* [PATCH v4 2/4] siphash: add N[qd]word helpers 2016-12-15 1:46 ` [PATCH v4 1/4] " Jason A. Donenfeld @ 2016-12-15 1:46 ` Jason A. Donenfeld 2016-12-15 1:46 ` [PATCH v4 3/4] secure_seq: use siphash instead of md5_transform Jason A. Donenfeld ` (2 subsequent siblings) 3 siblings, 0 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-15 1:46 UTC (permalink / raw) To: Netdev, kernel-hardening, LKML, linux-crypto Cc: Jason A. Donenfeld, Tom Herbert These restore parity with the jhash interface by providing high performance helpers for common input sizes. Linus doesn't like the use of "qword" and "dword", but I haven't been able to come up with another name for these that fits as well. Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> Cc: Tom Herbert <tom@herbertland.com> --- Changes from v2->v4: - Rather than just wrapping siphash(), we actually implement the fully optimized and manually unrolled version, so that lengths don't need to be checked and loops don't need to branch. - We now provide both 32-bit and 64-bit versions, both of which are quite useful for different circumstances. include/linux/siphash.h | 31 ++++++++++ lib/siphash.c | 161 ++++++++++++++++++++++++++++++++++++------------ lib/test_siphash.c | 18 ++++++ 3 files changed, 170 insertions(+), 40 deletions(-) diff --git a/include/linux/siphash.h b/include/linux/siphash.h index d0bcca7b992b..6e7c2a421bd9 100644 --- a/include/linux/siphash.h +++ b/include/linux/siphash.h @@ -27,4 +27,35 @@ static inline u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIP u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN]); #endif +u64 siphash_1qword(const u64 a, const u8 key[SIPHASH_KEY_LEN]); +u64 siphash_2qwords(const u64 a, const u64 b, const u8 key[SIPHASH_KEY_LEN]); +u64 siphash_3qwords(const u64 a, const u64 b, const u64 c, const u8 key[SIPHASH_KEY_LEN]); +u64 siphash_4qwords(const u64 a, const u64 b, const u64 c, const u64 d, const u8 key[SIPHASH_KEY_LEN]); + +static inline u64 siphash_2dwords(const u32 a, const u32 b, const u8 key[SIPHASH_KEY_LEN]) +{ + return siphash_1qword((u64)b << 32 | a, key); +} + +static inline u64 siphash_4dwords(const u32 a, const u32 b, const u32 c, const u32 d, + const u8 key[SIPHASH_KEY_LEN]) +{ + return siphash_2qwords((u64)b << 32 | a, (u64)d << 32 | c, key); +} + +static inline u64 siphash_6dwords(const u32 a, const u32 b, const u32 c, const u32 d, + const u32 e, const u32 f, const u8 key[SIPHASH_KEY_LEN]) +{ + return siphash_3qwords((u64)b << 32 | a, (u64)d << 32 | c, (u64)f << 32 | e, + key); +} + +static inline u64 siphash_8dwords(const u32 a, const u32 b, const u32 c, const u32 d, + const u32 e, const u32 f, const u32 g, const u32 h, + const u8 key[SIPHASH_KEY_LEN]) +{ + return siphash_4qwords((u64)b << 32 | a, (u64)d << 32 | c, (u64)f << 32 | e, + (u64)h << 32 | g, key); +} + #endif /* _LINUX_SIPHASH_H */ diff --git a/lib/siphash.c b/lib/siphash.c index b500231f61cd..c13d2b2bb76e 100644 --- a/lib/siphash.c +++ b/lib/siphash.c @@ -38,6 +38,31 @@ static inline u64 le64_to_cpuvp(const void *p) v2 += v1; v1 = rol64(v1, 17); v1 ^= v2; v2 = rol64(v2, 32); \ } while(0) +#define PREAMBLE(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)); \ + v3 ^= k1; \ + v2 ^= k0; \ + v1 ^= k1; \ + v0 ^= k0; + +#define POSTAMBLE \ + v3 ^= b; \ + SIPROUND; \ + SIPROUND; \ + v0 ^= b; \ + v2 ^= 0xff; \ + SIPROUND; \ + SIPROUND; \ + SIPROUND; \ + SIPROUND; \ + return (v0 ^ v1) ^ (v2 ^ v3); + /** * siphash - compute 64-bit siphash PRF value * @data: buffer to hash, must be aligned to SIPHASH_ALIGNMENT @@ -46,20 +71,10 @@ static inline u64 le64_to_cpuvp(const void *p) */ u64 siphash(const u8 *data, size_t len, const u8 key[SIPHASH_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; + u64 m; + PREAMBLE(len) for (; data != end; data += sizeof(u64)) { m = le64_to_cpuvp(data); v3 ^= m; @@ -81,16 +96,7 @@ u64 siphash(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN]) case 1: b |= data[0]; } #endif - v3 ^= b; - SIPROUND; - SIPROUND; - v0 ^= b; - v2 ^= 0xff; - SIPROUND; - SIPROUND; - SIPROUND; - SIPROUND; - return (v0 ^ v1) ^ (v2 ^ v3); + POSTAMBLE } EXPORT_SYMBOL(siphash); @@ -103,20 +109,10 @@ EXPORT_SYMBOL(siphash); */ u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_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; + u64 m; + PREAMBLE(len) for (; data != end; data += sizeof(u64)) { m = get_unaligned_le64(data); v3 ^= m; @@ -138,16 +134,101 @@ u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN]) case 1: b |= data[0]; } #endif - v3 ^= b; + POSTAMBLE +} +EXPORT_SYMBOL(siphash_unaligned); +#endif + +/** + * siphash_1qword - compute 64-bit siphash PRF value of 1 quad-word + * @first: first quadword + * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT + */ +u64 siphash_1qword(const u64 first, const u8 key[SIPHASH_KEY_LEN]) +{ + PREAMBLE(8) + v3 ^= first; + SIPROUND; + SIPROUND; + v0 ^= first; + POSTAMBLE +} +EXPORT_SYMBOL(siphash_1qword); + +/** + * siphash_2qwords - compute 64-bit siphash PRF value of 2 quad-words + * @first: first quadword + * @second: second quadword + * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT + */ +u64 siphash_2qwords(const u64 first, const u64 second, const u8 key[SIPHASH_KEY_LEN]) +{ + PREAMBLE(16) + v3 ^= first; SIPROUND; SIPROUND; - v0 ^= b; - v2 ^= 0xff; + v0 ^= first; + v3 ^= second; SIPROUND; SIPROUND; + v0 ^= second; + POSTAMBLE +} +EXPORT_SYMBOL(siphash_2qwords); + +/** + * siphash_3qwords - compute 64-bit siphash PRF value of 3 quad-words + * @first: first quadword + * @second: second quadword + * @third: third quadword + * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT + */ +u64 siphash_3qwords(const u64 first, const u64 second, const u64 third, const u8 key[SIPHASH_KEY_LEN]) +{ + PREAMBLE(24) + v3 ^= first; SIPROUND; SIPROUND; - return (v0 ^ v1) ^ (v2 ^ v3); + v0 ^= first; + v3 ^= second; + SIPROUND; + SIPROUND; + v0 ^= second; + v3 ^= third; + SIPROUND; + SIPROUND; + v0 ^= third; + POSTAMBLE } -EXPORT_SYMBOL(siphash24_unaligned); -#endif +EXPORT_SYMBOL(siphash_3qwords); + +/** + * siphash_4qwords - compute 64-bit siphash PRF value of 4 quad-words + * @first: first quadword + * @second: second quadword + * @third: third quadword + * @forth: forth quadword + * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT + */ +u64 siphash_4qwords(const u64 first, const u64 second, const u64 third, const u64 forth, const u8 key[SIPHASH_KEY_LEN]) +{ + PREAMBLE(32) + v3 ^= first; + SIPROUND; + SIPROUND; + v0 ^= first; + v3 ^= second; + SIPROUND; + SIPROUND; + v0 ^= second; + v3 ^= third; + SIPROUND; + SIPROUND; + v0 ^= third; + v3 ^= forth; + SIPROUND; + SIPROUND; + v0 ^= forth; + POSTAMBLE +} +EXPORT_SYMBOL(siphash_4qwords); diff --git a/lib/test_siphash.c b/lib/test_siphash.c index 444725c7834f..9925a325af35 100644 --- a/lib/test_siphash.c +++ b/lib/test_siphash.c @@ -68,6 +68,24 @@ static int __init siphash_test_init(void) ret = -EINVAL; } } + if (siphash_1qword(0x0706050403020100ULL, k) != test_vectors[8]) { + pr_info("self-test 1qword: FAIL\n"); + ret = -EINVAL; + } + if (siphash_2qwords(0x0706050403020100ULL, 0x0f0e0d0c0b0a0908ULL, k) != test_vectors[16]) { + pr_info("self-test 2qwords: FAIL\n"); + ret = -EINVAL; + } + if (siphash_3qwords(0x0706050403020100ULL, 0x0f0e0d0c0b0a0908ULL, + 0x1716151413121110ULL, k) != test_vectors[24]) { + pr_info("self-test 3qwords: FAIL\n"); + ret = -EINVAL; + } + if (siphash_4qwords(0x0706050403020100ULL, 0x0f0e0d0c0b0a0908ULL, + 0x1716151413121110ULL, 0x1f1e1d1c1b1a1918ULL, k) != test_vectors[32]) { + pr_info("self-test 4qwords: FAIL\n"); + ret = -EINVAL; + } if (!ret) pr_info("self-tests: pass\n"); return ret; -- 2.11.0 ^ permalink raw reply related [flat|nested] 70+ messages in thread
* [PATCH v4 3/4] secure_seq: use siphash instead of md5_transform 2016-12-15 1:46 ` [PATCH v4 1/4] " Jason A. Donenfeld 2016-12-15 1:46 ` [PATCH v4 2/4] siphash: add N[qd]word helpers Jason A. Donenfeld @ 2016-12-15 1:46 ` Jason A. Donenfeld 2016-12-15 1:46 ` [PATCH v4 4/4] random: use siphash instead of MD5 for get_random_int/long Jason A. Donenfeld 2016-12-15 4:23 ` [PATCH v4 1/4] siphash: add cryptographically secure hashtable function kbuild test robot 3 siblings, 0 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-15 1:46 UTC (permalink / raw) To: Netdev, kernel-hardening, LKML, linux-crypto Cc: Jason A. Donenfeld, Andi Kleen, David Miller, David Laight, Tom Herbert, Hannes Frederic Sowa This gives a clear speed and security improvement. Siphash is both faster and is more solid crypto than the aging MD5. Rather than manually filling MD5 buffers, for IPv6, we simply create a layout by a simple anonymous struct, for which gcc generates rather efficient code. For IPv4, we pass the values directly to the short input convenience functions. Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> Cc: Andi Kleen <ak@linux.intel.com> Cc: David Miller <davem@davemloft.net> Cc: David Laight <David.Laight@aculab.com> Cc: Tom Herbert <tom@herbertland.com> Cc: Hannes Frederic Sowa <hannes@stressinduktion.org> --- Changes from v3->v4: - For the IPv4 cases, we can now use the Ndwords helper functions, which make the calculation simpler and faster. - For the IPv6 cases, which still use the struct, we no longer pack the struct and instead simply pad until the nearest 64-bit size, so that it also avoids the slow branch for left-overs in siphash(). net/core/secure_seq.c | 133 ++++++++++++++++++++------------------------------ 1 file changed, 52 insertions(+), 81 deletions(-) diff --git a/net/core/secure_seq.c b/net/core/secure_seq.c index 88a8e429fc3e..8fed79932ec4 100644 --- a/net/core/secure_seq.c +++ b/net/core/secure_seq.c @@ -1,3 +1,5 @@ +/* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. */ + #include <linux/kernel.h> #include <linux/init.h> #include <linux/cryptohash.h> @@ -8,14 +10,14 @@ #include <linux/ktime.h> #include <linux/string.h> #include <linux/net.h> - +#include <linux/siphash.h> #include <net/secure_seq.h> #if IS_ENABLED(CONFIG_IPV6) || IS_ENABLED(CONFIG_INET) +#include <linux/in6.h> #include <net/tcp.h> -#define NET_SECRET_SIZE (MD5_MESSAGE_BYTES / 4) -static u32 net_secret[NET_SECRET_SIZE] ____cacheline_aligned; +static u8 net_secret[SIPHASH_KEY_LEN] __aligned(SIPHASH_ALIGNMENT); static __always_inline void net_secret_init(void) { @@ -44,44 +46,42 @@ static u32 seq_scale(u32 seq) u32 secure_tcpv6_sequence_number(const __be32 *saddr, const __be32 *daddr, __be16 sport, __be16 dport, u32 *tsoff) { - u32 secret[MD5_MESSAGE_BYTES / 4]; - u32 hash[MD5_DIGEST_WORDS]; - u32 i; - + const struct { + struct in6_addr saddr; + struct in6_addr daddr; + __be16 sport; + __be16 dport; + u32 padding; + } __aligned(SIPHASH_ALIGNMENT) combined = { + .saddr = *(struct in6_addr *)saddr, + .daddr = *(struct in6_addr *)daddr, + .sport = sport, + .dport = dport + }; + u64 hash; net_secret_init(); - memcpy(hash, saddr, 16); - for (i = 0; i < 4; i++) - secret[i] = net_secret[i] + (__force u32)daddr[i]; - secret[4] = net_secret[4] + - (((__force u16)sport << 16) + (__force u16)dport); - for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++) - secret[i] = net_secret[i]; - - md5_transform(hash, secret); - - *tsoff = sysctl_tcp_timestamps == 1 ? hash[1] : 0; - return seq_scale(hash[0]); + hash = siphash((const u8 *)&combined, sizeof(combined), net_secret); + *tsoff = sysctl_tcp_timestamps == 1 ? (hash >> 32) : 0; + return seq_scale(hash); } EXPORT_SYMBOL(secure_tcpv6_sequence_number); u32 secure_ipv6_port_ephemeral(const __be32 *saddr, const __be32 *daddr, __be16 dport) { - u32 secret[MD5_MESSAGE_BYTES / 4]; - u32 hash[MD5_DIGEST_WORDS]; - u32 i; - + const struct { + struct in6_addr saddr; + struct in6_addr daddr; + __be16 dport; + u16 padding1; + u32 padding2; + } __aligned(SIPHASH_ALIGNMENT) combined = { + .saddr = *(struct in6_addr *)saddr, + .daddr = *(struct in6_addr *)daddr, + .dport = dport + }; net_secret_init(); - memcpy(hash, saddr, 16); - for (i = 0; i < 4; i++) - secret[i] = net_secret[i] + (__force u32) daddr[i]; - secret[4] = net_secret[4] + (__force u32)dport; - for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++) - secret[i] = net_secret[i]; - - md5_transform(hash, secret); - - return hash[0]; + return siphash((const u8 *)&combined, sizeof(combined), net_secret); } EXPORT_SYMBOL(secure_ipv6_port_ephemeral); #endif @@ -91,33 +91,17 @@ EXPORT_SYMBOL(secure_ipv6_port_ephemeral); u32 secure_tcp_sequence_number(__be32 saddr, __be32 daddr, __be16 sport, __be16 dport, u32 *tsoff) { - u32 hash[MD5_DIGEST_WORDS]; - + u64 hash; net_secret_init(); - hash[0] = (__force u32)saddr; - hash[1] = (__force u32)daddr; - hash[2] = ((__force u16)sport << 16) + (__force u16)dport; - hash[3] = net_secret[15]; - - md5_transform(hash, net_secret); - - *tsoff = sysctl_tcp_timestamps == 1 ? hash[1] : 0; - return seq_scale(hash[0]); + hash = siphash_4dwords(saddr, daddr, sport, dport, net_secret); + *tsoff = sysctl_tcp_timestamps == 1 ? (hash >> 32) : 0; + return seq_scale(hash); } u32 secure_ipv4_port_ephemeral(__be32 saddr, __be32 daddr, __be16 dport) { - u32 hash[MD5_DIGEST_WORDS]; - net_secret_init(); - hash[0] = (__force u32)saddr; - hash[1] = (__force u32)daddr; - hash[2] = (__force u32)dport ^ net_secret[14]; - hash[3] = net_secret[15]; - - md5_transform(hash, net_secret); - - return hash[0]; + return siphash_4dwords(saddr, daddr, dport, 0, net_secret); } EXPORT_SYMBOL_GPL(secure_ipv4_port_ephemeral); #endif @@ -126,21 +110,11 @@ EXPORT_SYMBOL_GPL(secure_ipv4_port_ephemeral); u64 secure_dccp_sequence_number(__be32 saddr, __be32 daddr, __be16 sport, __be16 dport) { - u32 hash[MD5_DIGEST_WORDS]; u64 seq; - net_secret_init(); - hash[0] = (__force u32)saddr; - hash[1] = (__force u32)daddr; - hash[2] = ((__force u16)sport << 16) + (__force u16)dport; - hash[3] = net_secret[15]; - - md5_transform(hash, net_secret); - - seq = hash[0] | (((u64)hash[1]) << 32); + seq = siphash_4dwords(saddr, daddr, sport, dport, net_secret); seq += ktime_get_real_ns(); seq &= (1ull << 48) - 1; - return seq; } EXPORT_SYMBOL(secure_dccp_sequence_number); @@ -149,26 +123,23 @@ EXPORT_SYMBOL(secure_dccp_sequence_number); u64 secure_dccpv6_sequence_number(__be32 *saddr, __be32 *daddr, __be16 sport, __be16 dport) { - u32 secret[MD5_MESSAGE_BYTES / 4]; - u32 hash[MD5_DIGEST_WORDS]; + const struct { + struct in6_addr saddr; + struct in6_addr daddr; + __be16 sport; + __be16 dport; + u32 padding; + } __aligned(SIPHASH_ALIGNMENT) combined = { + .saddr = *(struct in6_addr *)saddr, + .daddr = *(struct in6_addr *)daddr, + .sport = sport, + .dport = dport + }; u64 seq; - u32 i; - net_secret_init(); - memcpy(hash, saddr, 16); - for (i = 0; i < 4; i++) - secret[i] = net_secret[i] + (__force u32)daddr[i]; - secret[4] = net_secret[4] + - (((__force u16)sport << 16) + (__force u16)dport); - for (i = 5; i < MD5_MESSAGE_BYTES / 4; i++) - secret[i] = net_secret[i]; - - md5_transform(hash, secret); - - seq = hash[0] | (((u64)hash[1]) << 32); + seq = siphash((const u8 *)&combined, sizeof(combined), net_secret); seq += ktime_get_real_ns(); seq &= (1ull << 48) - 1; - return seq; } EXPORT_SYMBOL(secure_dccpv6_sequence_number); -- 2.11.0 ^ permalink raw reply related [flat|nested] 70+ messages in thread
* [PATCH v4 4/4] random: use siphash instead of MD5 for get_random_int/long 2016-12-15 1:46 ` [PATCH v4 1/4] " Jason A. Donenfeld 2016-12-15 1:46 ` [PATCH v4 2/4] siphash: add N[qd]word helpers Jason A. Donenfeld 2016-12-15 1:46 ` [PATCH v4 3/4] secure_seq: use siphash instead of md5_transform Jason A. Donenfeld @ 2016-12-15 1:46 ` Jason A. Donenfeld 2016-12-15 4:23 ` [PATCH v4 1/4] siphash: add cryptographically secure hashtable function kbuild test robot 3 siblings, 0 replies; 70+ messages in thread From: Jason A. Donenfeld @ 2016-12-15 1:46 UTC (permalink / raw) To: Netdev, kernel-hardening, LKML, linux-crypto Cc: Jason A. Donenfeld, Jean-Philippe Aumasson, Ted Tso This duplicates the current algorithm for get_random_int/long, but uses siphash instead. This comes with several benefits. It's certainly faster and more cryptographically secure than MD5. This patch also separates hashed fields into three values instead of one, in order to increase diffusion. The previous MD5 algorithm used a per-cpu MD5 state, which caused successive calls to the function to chain upon each other. While it's not entirely clear that this kind of chaining is absolutely necessary when using a secure PRF like siphash, it can't hurt, and the timing of the call chain does add a degree of natural entropy. So, in keeping with this design, instead of the massive per-cpu 64-byte MD5 state, there is instead a per-cpu previously returned value for chaining. The speed benefits are substantial: | siphash | md5 | speedup | ------------------------------ get_random_long | 137130 | 415983 | 3.03x | get_random_int | 86384 | 343323 | 3.97x | Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com> Cc: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> Cc: Ted Tso <tytso@mit.edu> --- Changes from v3->v4: - Speedups by using the 3qwords function. drivers/char/random.c | 30 +++++++++++------------------- 1 file changed, 11 insertions(+), 19 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index d6876d506220..8e1d1cfface6 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -262,6 +262,7 @@ #include <linux/syscalls.h> #include <linux/completion.h> #include <linux/uuid.h> +#include <linux/siphash.h> #include <crypto/chacha20.h> #include <asm/processor.h> @@ -2042,7 +2043,7 @@ struct ctl_table random_table[] = { }; #endif /* CONFIG_SYSCTL */ -static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned; +static u8 random_int_secret[SIPHASH_KEY_LEN] __aligned(SIPHASH_ALIGNMENT); int random_int_secret_init(void) { @@ -2050,8 +2051,7 @@ int random_int_secret_init(void) return 0; } -static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash) - __aligned(sizeof(unsigned long)); +static DEFINE_PER_CPU(u64, get_random_int_chaining); /* * Get a random word for internal kernel use only. Similar to urandom but @@ -2061,19 +2061,15 @@ static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash) */ unsigned int get_random_int(void) { - __u32 *hash; unsigned int ret; + u64 *chaining; if (arch_get_random_int(&ret)) return ret; - hash = get_cpu_var(get_random_int_hash); - - hash[0] += current->pid + jiffies + random_get_entropy(); - md5_transform(hash, random_int_secret); - ret = hash[0]; - put_cpu_var(get_random_int_hash); - + chaining = &get_cpu_var(get_random_int_chaining); + ret = *chaining = siphash_3qwords(*chaining, jiffies, random_get_entropy() + current->pid, random_int_secret); + put_cpu_var(get_random_int_chaining); return ret; } EXPORT_SYMBOL(get_random_int); @@ -2083,19 +2079,15 @@ EXPORT_SYMBOL(get_random_int); */ unsigned long get_random_long(void) { - __u32 *hash; unsigned long ret; + u64 *chaining; if (arch_get_random_long(&ret)) return ret; - hash = get_cpu_var(get_random_int_hash); - - hash[0] += current->pid + jiffies + random_get_entropy(); - md5_transform(hash, random_int_secret); - ret = *(unsigned long *)hash; - put_cpu_var(get_random_int_hash); - + chaining = &get_cpu_var(get_random_int_chaining); + ret = *chaining = siphash_3qwords(*chaining, jiffies, random_get_entropy() + current->pid, random_int_secret); + put_cpu_var(get_random_int_chaining); return ret; } EXPORT_SYMBOL(get_random_long); -- 2.11.0 ^ permalink raw reply related [flat|nested] 70+ messages in thread
* Re: [PATCH v4 1/4] siphash: add cryptographically secure hashtable function 2016-12-15 1:46 ` [PATCH v4 1/4] " Jason A. Donenfeld ` (2 preceding siblings ...) 2016-12-15 1:46 ` [PATCH v4 4/4] random: use siphash instead of MD5 for get_random_int/long Jason A. Donenfeld @ 2016-12-15 4:23 ` kbuild test robot 3 siblings, 0 replies; 70+ messages in thread From: kbuild test robot @ 2016-12-15 4:23 UTC (permalink / raw) To: Jason A. Donenfeld Cc: kbuild-all, Netdev, kernel-hardening, LKML, linux-crypto, Jason A. Donenfeld, Jean-Philippe Aumasson, Daniel J . Bernstein, Linus Torvalds, Eric Biggers, David Laight [-- Attachment #1: Type: text/plain, Size: 6410 bytes --] Hi Jason, [auto build test ERROR on linus/master] [also build test ERROR on v4.9 next-20161215] [if your patch is applied to the wrong git tree, please drop us a note to help improve the system] url: https://github.com/0day-ci/linux/commits/Jason-A-Donenfeld/siphash-add-cryptographically-secure-hashtable-function/20161215-095213 config: ia64-allmodconfig (attached as .config) compiler: ia64-linux-gcc (GCC) 6.2.0 reproduce: wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross # save the attached .config to linux build tree make.cross ARCH=ia64 Note: the linux-review/Jason-A-Donenfeld/siphash-add-cryptographically-secure-hashtable-function/20161215-095213 HEAD 3e343f4316f94cded0d1384cf35957fd51dbbc28 builds fine. It only hurts bisectibility. All error/warnings (new ones prefixed by >>): In file included from include/linux/linkage.h:6:0, from include/linux/kernel.h:6, from lib/siphash.c:12: >> lib/siphash.c:152:15: error: 'siphash24_unaligned' undeclared here (not in a function) EXPORT_SYMBOL(siphash24_unaligned); ^ include/linux/export.h:58:16: note: in definition of macro '___EXPORT_SYMBOL' extern typeof(sym) sym; \ ^~~ >> lib/siphash.c:152:1: note: in expansion of macro 'EXPORT_SYMBOL' EXPORT_SYMBOL(siphash24_unaligned); ^~~~~~~~~~~~~ vim +/siphash24_unaligned +152 lib/siphash.c 6 * https://131002.net/siphash/ 7 * 8 * This implementation is specifically for SipHash2-4. 9 */ 10 11 #include <linux/siphash.h> > 12 #include <linux/kernel.h> 13 #include <asm/unaligned.h> 14 15 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64 16 #include <linux/dcache.h> 17 #include <asm/word-at-a-time.h> 18 #endif 19 20 static inline u16 le16_to_cpuvp(const void *p) 21 { 22 return le16_to_cpup(p); 23 } 24 static inline u32 le32_to_cpuvp(const void *p) 25 { 26 return le32_to_cpup(p); 27 } 28 static inline u64 le64_to_cpuvp(const void *p) 29 { 30 return le64_to_cpup(p); 31 } 32 33 #define SIPROUND \ 34 do { \ 35 v0 += v1; v1 = rol64(v1, 13); v1 ^= v0; v0 = rol64(v0, 32); \ 36 v2 += v3; v3 = rol64(v3, 16); v3 ^= v2; \ 37 v0 += v3; v3 = rol64(v3, 21); v3 ^= v0; \ 38 v2 += v1; v1 = rol64(v1, 17); v1 ^= v2; v2 = rol64(v2, 32); \ 39 } while(0) 40 41 /** 42 * siphash - compute 64-bit siphash PRF value 43 * @data: buffer to hash, must be aligned to SIPHASH_ALIGNMENT 44 * @size: size of @data 45 * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT 46 */ 47 u64 siphash(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN]) 48 { 49 u64 v0 = 0x736f6d6570736575ULL; 50 u64 v1 = 0x646f72616e646f6dULL; 51 u64 v2 = 0x6c7967656e657261ULL; 52 u64 v3 = 0x7465646279746573ULL; 53 u64 b = ((u64)len) << 56; 54 u64 k0 = le64_to_cpuvp(key); 55 u64 k1 = le64_to_cpuvp(key + sizeof(u64)); 56 u64 m; 57 const u8 *end = data + len - (len % sizeof(u64)); 58 const u8 left = len & (sizeof(u64) - 1); 59 v3 ^= k1; 60 v2 ^= k0; 61 v1 ^= k1; 62 v0 ^= k0; 63 for (; data != end; data += sizeof(u64)) { 64 m = le64_to_cpuvp(data); 65 v3 ^= m; 66 SIPROUND; 67 SIPROUND; 68 v0 ^= m; 69 } 70 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64 71 if (left) 72 b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) & bytemask_from_count(left))); 73 #else 74 switch (left) { 75 case 7: b |= ((u64)data[6]) << 48; 76 case 6: b |= ((u64)data[5]) << 40; 77 case 5: b |= ((u64)data[4]) << 32; 78 case 4: b |= le32_to_cpuvp(data); break; 79 case 3: b |= ((u64)data[2]) << 16; 80 case 2: b |= le16_to_cpuvp(data); break; 81 case 1: b |= data[0]; 82 } 83 #endif 84 v3 ^= b; 85 SIPROUND; 86 SIPROUND; 87 v0 ^= b; 88 v2 ^= 0xff; 89 SIPROUND; 90 SIPROUND; 91 SIPROUND; 92 SIPROUND; 93 return (v0 ^ v1) ^ (v2 ^ v3); 94 } 95 EXPORT_SYMBOL(siphash); 96 97 #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS 98 /** 99 * siphash - compute 64-bit siphash PRF value, without alignment requirements 100 * @data: buffer to hash 101 * @size: size of @data 102 * @key: key buffer of size SIPHASH_KEY_LEN, must be aligned to SIPHASH_ALIGNMENT 103 */ 104 u64 siphash_unaligned(const u8 *data, size_t len, const u8 key[SIPHASH_KEY_LEN]) 105 { 106 u64 v0 = 0x736f6d6570736575ULL; 107 u64 v1 = 0x646f72616e646f6dULL; 108 u64 v2 = 0x6c7967656e657261ULL; 109 u64 v3 = 0x7465646279746573ULL; 110 u64 b = ((u64)len) << 56; 111 u64 k0 = le64_to_cpuvp(key); 112 u64 k1 = le64_to_cpuvp(key + sizeof(u64)); 113 u64 m; 114 const u8 *end = data + len - (len % sizeof(u64)); 115 const u8 left = len & (sizeof(u64) - 1); 116 v3 ^= k1; 117 v2 ^= k0; 118 v1 ^= k1; 119 v0 ^= k0; 120 for (; data != end; data += sizeof(u64)) { 121 m = get_unaligned_le64(data); 122 v3 ^= m; 123 SIPROUND; 124 SIPROUND; 125 v0 ^= m; 126 } 127 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64 128 if (left) 129 b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) & bytemask_from_count(left))); 130 #else 131 switch (left) { 132 case 7: b |= ((u64)data[6]) << 48; 133 case 6: b |= ((u64)data[5]) << 40; 134 case 5: b |= ((u64)data[4]) << 32; 135 case 4: b |= get_unaligned_le32(data); break; 136 case 3: b |= ((u64)data[2]) << 16; 137 case 2: b |= get_unaligned_le16(data); break; 138 case 1: b |= data[0]; 139 } 140 #endif 141 v3 ^= b; 142 SIPROUND; 143 SIPROUND; 144 v0 ^= b; 145 v2 ^= 0xff; 146 SIPROUND; 147 SIPROUND; 148 SIPROUND; 149 SIPROUND; 150 return (v0 ^ v1) ^ (v2 ^ v3); 151 } > 152 EXPORT_SYMBOL(siphash24_unaligned); 153 #endif --- 0-DAY kernel test infrastructure Open Source Technology Center https://lists.01.org/pipermail/kbuild-all Intel Corporation [-- Attachment #2: .config.gz --] [-- Type: application/gzip, Size: 45649 bytes --] ^ permalink raw reply [flat|nested] 70+ messages in thread
end of thread, other threads:[~2016-12-18 0:06 UTC | newest] Thread overview: 70+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2016-12-14 3:59 [PATCH v2 1/4] siphash: add cryptographically secure hashtable function Jason A. Donenfeld 2016-12-14 3:59 ` [PATCH v2 2/4] siphash: add convenience functions for jhash converts Jason A. Donenfeld 2016-12-14 3:59 ` [PATCH v2 3/4] secure_seq: use siphash24 instead of md5_transform Jason A. Donenfeld 2016-12-14 12:53 ` Jason A. Donenfeld 2016-12-14 13:16 ` Hannes Frederic Sowa 2016-12-14 13:44 ` Jason A. Donenfeld 2016-12-14 14:47 ` David Laight 2016-12-14 17:49 ` Jason A. Donenfeld 2016-12-14 17:56 ` David Miller 2016-12-14 18:06 ` Jason A. Donenfeld 2016-12-14 19:22 ` Hannes Frederic Sowa 2016-12-14 19:38 ` Jason A. Donenfeld 2016-12-14 20:27 ` Hannes Frederic Sowa 2016-12-14 20:12 ` Tom Herbert 2016-12-14 21:01 ` Jason A. Donenfeld 2016-12-14 3:59 ` [PATCH v2 4/4] random: use siphash24 instead of md5 for get_random_int/long Jason A. Donenfeld 2016-12-14 11:21 ` [PATCH v2 1/4] siphash: add cryptographically secure hashtable function Hannes Frederic Sowa 2016-12-14 13:10 ` Jason A. Donenfeld 2016-12-14 15:09 ` Hannes Frederic Sowa 2016-12-14 19:47 ` Jason A. Donenfeld 2016-12-15 7:57 ` Herbert Xu 2016-12-15 8:15 ` [kernel-hardening] " Daniel Micay 2016-12-14 12:46 ` Jason A. Donenfeld 2016-12-14 22:03 ` Hannes Frederic Sowa 2016-12-14 23:29 ` Jason A. Donenfeld 2016-12-15 8:31 ` Hannes Frederic Sowa 2016-12-15 11:04 ` David Laight 2016-12-15 12:23 ` Hannes Frederic Sowa 2016-12-15 12:28 ` David Laight 2016-12-15 12:50 ` Hannes Frederic Sowa 2016-12-15 13:56 ` David Laight 2016-12-15 14:56 ` Hannes Frederic Sowa 2016-12-15 15:41 ` David Laight 2016-12-15 15:53 ` Hannes Frederic Sowa 2016-12-15 18:50 ` Jason A. Donenfeld 2016-12-15 20:31 ` Hannes Frederic Sowa 2016-12-15 20:43 ` Jason A. Donenfeld 2016-12-15 21:04 ` Peter Zijlstra 2016-12-15 21:09 ` Hannes Frederic Sowa 2016-12-15 21:17 ` Hannes Frederic Sowa 2016-12-15 21:09 ` Peter Zijlstra 2016-12-15 21:11 ` [kernel-hardening] " Jason A. Donenfeld 2016-12-15 21:14 ` Linus Torvalds 2016-12-14 18:46 ` [PATCH v3 1/3] " Jason A. Donenfeld 2016-12-14 18:46 ` [PATCH v3 2/3] secure_seq: use siphash24 instead of md5_transform Jason A. Donenfeld 2016-12-14 21:44 ` kbuild test robot 2016-12-14 18:46 ` [PATCH v3 3/3] random: use siphash24 instead of md5 for get_random_int/long Jason A. Donenfeld 2016-12-14 21:56 ` kbuild test robot 2016-12-14 21:57 ` kbuild test robot 2016-12-15 10:14 ` David Laight 2016-12-15 18:51 ` Jason A. Donenfeld 2016-12-14 19:18 ` [PATCH v3 1/3] siphash: add cryptographically secure hashtable function Tom Herbert 2016-12-14 19:35 ` Jason A. Donenfeld 2016-12-14 20:55 ` Jason A. Donenfeld 2016-12-14 21:35 ` Tom Herbert 2016-12-14 22:56 ` Jason A. Donenfeld 2016-12-14 23:14 ` Tom Herbert 2016-12-14 23:17 ` Jason A. Donenfeld 2016-12-18 0:06 ` Christian Kujau 2016-12-14 23:30 ` Linus Torvalds 2016-12-14 23:34 ` Jason A. Donenfeld 2016-12-15 0:10 ` Linus Torvalds 2016-12-15 10:22 ` David Laight 2016-12-14 21:15 ` kbuild test robot 2016-12-14 21:21 ` Jason A. Donenfeld 2016-12-15 1:46 ` [PATCH v4 1/4] " Jason A. Donenfeld 2016-12-15 1:46 ` [PATCH v4 2/4] siphash: add N[qd]word helpers Jason A. Donenfeld 2016-12-15 1:46 ` [PATCH v4 3/4] secure_seq: use siphash instead of md5_transform Jason A. Donenfeld 2016-12-15 1:46 ` [PATCH v4 4/4] random: use siphash instead of MD5 for get_random_int/long Jason A. Donenfeld 2016-12-15 4:23 ` [PATCH v4 1/4] siphash: add cryptographically secure hashtable function kbuild test robot
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).