Re: [PATCH v4 1/4] siphash: add cryptographically secure hashtable function

[kbuild test robot]

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 
  > 12  #include 
13  #include 
14  
15  #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
16  #include 
17  #include 
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
   

[PATCH v4 1/4] siphash: add cryptographically secure hashtable function

[Jason A. Donenfeld]

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 
Cc: Jean-Philippe Aumasson 
Cc: Daniel J. Bernstein 
Cc: Linus Torvalds 
Cc: Eric Biggers 
Cc: David Laight 
---
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 ..d0bcca7b992b
--- /dev/null
+++ b/include/linux/siphash.h
@@ -0,0 +1,30 @@
+/* Copyright (C) 2016 Jason A. Donenfeld . 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 
+
+#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 ()
- and string () hash functions on boot
- (or module load).
+ Enable this option to test the kernel's integer (),
+ string (), and siphash ()
+ 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