From patchwork Fri Dec 9 18:36:59 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Jason A. Donenfeld" X-Patchwork-Id: 9468915 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id B4D82607D8 for ; Fri, 9 Dec 2016 18:37:52 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id AB0FE28643 for ; Fri, 9 Dec 2016 18:37:52 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 9FE902865C; Fri, 9 Dec 2016 18:37:52 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-3.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_MED, T_DKIM_INVALID, URI_HEX autolearn=ham version=3.3.1 Received: from mother.openwall.net (mother.openwall.net [195.42.179.200]) by mail.wl.linuxfoundation.org (Postfix) with SMTP id B031F28643 for ; Fri, 9 Dec 2016 18:37:50 +0000 (UTC) Received: (qmail 27713 invoked by uid 550); 9 Dec 2016 18:37:48 -0000 Mailing-List: contact kernel-hardening-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: kernel-hardening@lists.openwall.com Delivered-To: mailing list kernel-hardening@lists.openwall.com Received: (qmail 27686 invoked from network); 9 Dec 2016 18:37:46 -0000 DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=zx2c4.com; h=from:to:cc :subject:date:message-id; s=mail; bh=3lqok0C7A06w3EN9JbjfOxFGHBo =; b=Tw52GhUjnWpU0DHXi1FeEmcFpMKN2ienqdSf4EkWpTBnLum7090xmnFuvIO IaKkIQabQguqW8Sm4w7uCuHWAAwlhUU2QMlUwtYx4VqZMP6HqgMvZgaoNeffLGd7 qj8PzmOni8PRr4ga8dJ+yzRD+XrMKQqhJ8gkXSMl7YXJ4+9CSpOPl74pOLTc50TZ 2dGsh0HTcmhI0M59hQcUwnx+Jt8Dkilxau3vaEZe71Z4xyFTWrf7UXWqvIUBaThh xpV2LZ66JhbVG3DVGHjXcs6RgyhYxQk8yL4xewFthrYmlXcjXj53uGWC74+iajG8 3H2cGccng8hXlQvx40SaEbG7ZTA== From: "Jason A. Donenfeld" To: linux-kernel@vger.kernel.org, kernel-hardening@lists.openwall.com, linux-crypto@vger.kernel.org, rusty@rustcorp.com.au, torvalds@linux-foundation.org Cc: "Jason A. Donenfeld" , Jean-Philippe Aumasson , "Daniel J . Bernstein" Date: Fri, 9 Dec 2016 19:36:59 +0100 Message-Id: <20161209183659.25727-1-Jason@zx2c4.com> X-Mailer: git-send-email 2.11.0 Subject: [kernel-hardening] [PATCH] siphash: add cryptographically secure hashtable function X-Virus-Scanned: ClamAV using ClamSMTP 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 Cc: Jean-Philippe Aumasson Cc: Daniel J. Bernstein --- include/linux/siphash.h | 18 ++++++ lib/Makefile | 3 +- lib/siphash.c | 163 ++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 183 insertions(+), 1 deletion(-) create mode 100644 include/linux/siphash.h create mode 100644 lib/siphash.c diff --git a/include/linux/siphash.h b/include/linux/siphash.h new file mode 100644 index 000000000000..485c2101cc7d --- /dev/null +++ b/include/linux/siphash.h @@ -0,0 +1,18 @@ +/* Copyright (C) 2016 Jason A. Donenfeld + * + * SipHash: a fast short-input PRF + * https://131002.net/siphash/ + */ + +#ifndef _LINUX_SIPHASH_H +#define _LINUX_SIPHASH_H + +#include + +enum siphash24_lengths { + SIPHASH24_KEY_LEN = 16 +}; + +uint64_t siphash24(const uint8_t *data, size_t len, const uint8_t key[SIPHASH24_KEY_LEN]); + +#endif /* _LINUX_SIPHASH_H */ diff --git a/lib/Makefile b/lib/Makefile index 50144a3aeebd..d224337b0d01 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -22,7 +22,8 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ sha1.o chacha20.o md5.o irq_regs.o argv_split.o \ flex_proportions.o ratelimit.o show_mem.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ - earlycpio.o seq_buf.o nmi_backtrace.o nodemask.o win_minmax.o + earlycpio.o seq_buf.o siphash.o \ + nmi_backtrace.o nodemask.o win_minmax.o lib-$(CONFIG_MMU) += ioremap.o lib-$(CONFIG_SMP) += cpumask.o diff --git a/lib/siphash.c b/lib/siphash.c new file mode 100644 index 000000000000..022d86f04b9b --- /dev/null +++ b/lib/siphash.c @@ -0,0 +1,163 @@ +/* Copyright (C) 2015-2016 Jason A. Donenfeld + * Copyright (C) 2012-2014 Jean-Philippe Aumasson + * Copyright (C) 2012-2014 Daniel J. Bernstein + * + * SipHash: a fast short-input PRF + * https://131002.net/siphash/ + */ + +#include +#include +#include + +#define ROTL(x,b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) +#define U8TO64(p) le64_to_cpu(*(__le64 *)(p)) + +#define SIPROUND \ + do { \ + v0 += v1; v1 = ROTL(v1, 13); v1 ^= v0; v0 = ROTL(v0, 32); \ + v2 += v3; v3 = ROTL(v3, 16); v3 ^= v2; \ + v0 += v3; v3 = ROTL(v3, 21); v3 ^= v0; \ + v2 += v1; v1 = ROTL(v1, 17); v1 ^= v2; v2 = ROTL(v2, 32); \ + } while(0) + +__attribute__((optimize("unroll-loops"))) +uint64_t siphash24(const uint8_t *data, size_t len, const uint8_t key[SIPHASH24_KEY_LEN]) +{ + uint64_t v0 = 0x736f6d6570736575ULL; + uint64_t v1 = 0x646f72616e646f6dULL; + uint64_t v2 = 0x6c7967656e657261ULL; + uint64_t v3 = 0x7465646279746573ULL; + uint64_t b; + uint64_t k0 = U8TO64(key); + uint64_t k1 = U8TO64(key + sizeof(uint64_t)); + uint64_t m; + const uint8_t *end = data + len - (len % sizeof(uint64_t)); + const uint8_t left = len & (sizeof(uint64_t) - 1); + b = ((uint64_t)len) << 56; + v3 ^= k1; + v2 ^= k0; + v1 ^= k1; + v0 ^= k0; + for (; data != end; data += sizeof(uint64_t)) { + m = U8TO64(data); + v3 ^= m; + SIPROUND; + SIPROUND; + v0 ^= m; + } + switch (left) { + case 7: b |= ((uint64_t)data[6]) << 48; + case 6: b |= ((uint64_t)data[5]) << 40; + case 5: b |= ((uint64_t)data[4]) << 32; + case 4: b |= ((uint64_t)data[3]) << 24; + case 3: b |= ((uint64_t)data[2]) << 16; + case 2: b |= ((uint64_t)data[1]) << 8; + case 1: b |= ((uint64_t)data[0]); break; + case 0: break; + } + v3 ^= b; + SIPROUND; + SIPROUND; + v0 ^= b; + v2 ^= 0xff; + SIPROUND; + SIPROUND; + SIPROUND; + SIPROUND; + b = (v0 ^ v1) ^ (v2 ^ v3); + return (__force uint64_t)cpu_to_le64(b); +} +EXPORT_SYMBOL(siphash24); + +#ifdef DEBUG +static const uint8_t test_vectors[64][8] = { + { 0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72 }, + { 0xfd, 0x67, 0xdc, 0x93, 0xc5, 0x39, 0xf8, 0x74 }, + { 0x5a, 0x4f, 0xa9, 0xd9, 0x09, 0x80, 0x6c, 0x0d }, + { 0x2d, 0x7e, 0xfb, 0xd7, 0x96, 0x66, 0x67, 0x85 }, + { 0xb7, 0x87, 0x71, 0x27, 0xe0, 0x94, 0x27, 0xcf }, + { 0x8d, 0xa6, 0x99, 0xcd, 0x64, 0x55, 0x76, 0x18 }, + { 0xce, 0xe3, 0xfe, 0x58, 0x6e, 0x46, 0xc9, 0xcb }, + { 0x37, 0xd1, 0x01, 0x8b, 0xf5, 0x00, 0x02, 0xab }, + { 0x62, 0x24, 0x93, 0x9a, 0x79, 0xf5, 0xf5, 0x93 }, + { 0xb0, 0xe4, 0xa9, 0x0b, 0xdf, 0x82, 0x00, 0x9e }, + { 0xf3, 0xb9, 0xdd, 0x94, 0xc5, 0xbb, 0x5d, 0x7a }, + { 0xa7, 0xad, 0x6b, 0x22, 0x46, 0x2f, 0xb3, 0xf4 }, + { 0xfb, 0xe5, 0x0e, 0x86, 0xbc, 0x8f, 0x1e, 0x75 }, + { 0x90, 0x3d, 0x84, 0xc0, 0x27, 0x56, 0xea, 0x14 }, + { 0xee, 0xf2, 0x7a, 0x8e, 0x90, 0xca, 0x23, 0xf7 }, + { 0xe5, 0x45, 0xbe, 0x49, 0x61, 0xca, 0x29, 0xa1 }, + { 0xdb, 0x9b, 0xc2, 0x57, 0x7f, 0xcc, 0x2a, 0x3f }, + { 0x94, 0x47, 0xbe, 0x2c, 0xf5, 0xe9, 0x9a, 0x69 }, + { 0x9c, 0xd3, 0x8d, 0x96, 0xf0, 0xb3, 0xc1, 0x4b }, + { 0xbd, 0x61, 0x79, 0xa7, 0x1d, 0xc9, 0x6d, 0xbb }, + { 0x98, 0xee, 0xa2, 0x1a, 0xf2, 0x5c, 0xd6, 0xbe }, + { 0xc7, 0x67, 0x3b, 0x2e, 0xb0, 0xcb, 0xf2, 0xd0 }, + { 0x88, 0x3e, 0xa3, 0xe3, 0x95, 0x67, 0x53, 0x93 }, + { 0xc8, 0xce, 0x5c, 0xcd, 0x8c, 0x03, 0x0c, 0xa8 }, + { 0x94, 0xaf, 0x49, 0xf6, 0xc6, 0x50, 0xad, 0xb8 }, + { 0xea, 0xb8, 0x85, 0x8a, 0xde, 0x92, 0xe1, 0xbc }, + { 0xf3, 0x15, 0xbb, 0x5b, 0xb8, 0x35, 0xd8, 0x17 }, + { 0xad, 0xcf, 0x6b, 0x07, 0x63, 0x61, 0x2e, 0x2f }, + { 0xa5, 0xc9, 0x1d, 0xa7, 0xac, 0xaa, 0x4d, 0xde }, + { 0x71, 0x65, 0x95, 0x87, 0x66, 0x50, 0xa2, 0xa6 }, + { 0x28, 0xef, 0x49, 0x5c, 0x53, 0xa3, 0x87, 0xad }, + { 0x42, 0xc3, 0x41, 0xd8, 0xfa, 0x92, 0xd8, 0x32 }, + { 0xce, 0x7c, 0xf2, 0x72, 0x2f, 0x51, 0x27, 0x71 }, + { 0xe3, 0x78, 0x59, 0xf9, 0x46, 0x23, 0xf3, 0xa7 }, + { 0x38, 0x12, 0x05, 0xbb, 0x1a, 0xb0, 0xe0, 0x12 }, + { 0xae, 0x97, 0xa1, 0x0f, 0xd4, 0x34, 0xe0, 0x15 }, + { 0xb4, 0xa3, 0x15, 0x08, 0xbe, 0xff, 0x4d, 0x31 }, + { 0x81, 0x39, 0x62, 0x29, 0xf0, 0x90, 0x79, 0x02 }, + { 0x4d, 0x0c, 0xf4, 0x9e, 0xe5, 0xd4, 0xdc, 0xca }, + { 0x5c, 0x73, 0x33, 0x6a, 0x76, 0xd8, 0xbf, 0x9a }, + { 0xd0, 0xa7, 0x04, 0x53, 0x6b, 0xa9, 0x3e, 0x0e }, + { 0x92, 0x59, 0x58, 0xfc, 0xd6, 0x42, 0x0c, 0xad }, + { 0xa9, 0x15, 0xc2, 0x9b, 0xc8, 0x06, 0x73, 0x18 }, + { 0x95, 0x2b, 0x79, 0xf3, 0xbc, 0x0a, 0xa6, 0xd4 }, + { 0xf2, 0x1d, 0xf2, 0xe4, 0x1d, 0x45, 0x35, 0xf9 }, + { 0x87, 0x57, 0x75, 0x19, 0x04, 0x8f, 0x53, 0xa9 }, + { 0x10, 0xa5, 0x6c, 0xf5, 0xdf, 0xcd, 0x9a, 0xdb }, + { 0xeb, 0x75, 0x09, 0x5c, 0xcd, 0x98, 0x6c, 0xd0 }, + { 0x51, 0xa9, 0xcb, 0x9e, 0xcb, 0xa3, 0x12, 0xe6 }, + { 0x96, 0xaf, 0xad, 0xfc, 0x2c, 0xe6, 0x66, 0xc7 }, + { 0x72, 0xfe, 0x52, 0x97, 0x5a, 0x43, 0x64, 0xee }, + { 0x5a, 0x16, 0x45, 0xb2, 0x76, 0xd5, 0x92, 0xa1 }, + { 0xb2, 0x74, 0xcb, 0x8e, 0xbf, 0x87, 0x87, 0x0a }, + { 0x6f, 0x9b, 0xb4, 0x20, 0x3d, 0xe7, 0xb3, 0x81 }, + { 0xea, 0xec, 0xb2, 0xa3, 0x0b, 0x22, 0xa8, 0x7f }, + { 0x99, 0x24, 0xa4, 0x3c, 0xc1, 0x31, 0x57, 0x24 }, + { 0xbd, 0x83, 0x8d, 0x3a, 0xaf, 0xbf, 0x8d, 0xb7 }, + { 0x0b, 0x1a, 0x2a, 0x32, 0x65, 0xd5, 0x1a, 0xea }, + { 0x13, 0x50, 0x79, 0xa3, 0x23, 0x1c, 0xe6, 0x60 }, + { 0x93, 0x2b, 0x28, 0x46, 0xe4, 0xd7, 0x06, 0x66 }, + { 0xe1, 0x91, 0x5f, 0x5c, 0xb1, 0xec, 0xa4, 0x6c }, + { 0xf3, 0x25, 0x96, 0x5c, 0xa1, 0x6d, 0x62, 0x9f }, + { 0x57, 0x5f, 0xf2, 0x8e, 0x60, 0x38, 0x1b, 0xe5 }, + { 0x72, 0x45, 0x06, 0xeb, 0x4c, 0x32, 0x8a, 0x95 } +}; + +static int siphash24_selftest(void) +{ + uint8_t in[64], k[16], i; + uint64_t out; + int ret = 0; + + for (i = 0; i < 16; ++i) + k[i] = i; + + for (i = 0; i < 64; ++i) { + in[i] = i; + out = siphash24(in, i, k); + if (memcmp(&out, test_vectors[i], 8)) { + printk(KERN_INFO "siphash24: self-test %u: FAIL\n", i + 1); + ret = -1; + } + } + if (!ret) + printk(KERN_INFO "siphash24: self-tests: pass\n"); + return ret; +} +__initcall(siphash24_selftest); +#endif