Use siphash for hashtables

8 files changed, 315 insertions, 18 deletions

diff --git a/Makefile b/Makefile
index dc381c3..cca6b03 100644
--- a/Makefile
+++ b/Makefile
@@ -46,7 +46,7 @@ endif
 all: wg-dynamic-server wg-dynamic-client
 
 wg-dynamic-client: wg-dynamic-client.o netlink.o common.o ipm.o
-wg-dynamic-server: wg-dynamic-server.o netlink.o radix-trie.o common.o random.o lease.o ipm.o
+wg-dynamic-server: wg-dynamic-server.o netlink.o radix-trie.o common.o random.o lease.o ipm.o siphash.o
 
 ifneq ($(V),1)
 clean:
diff --git a/khash.h b/khash.h
index 445ee3d..0769711 100644
--- a/khash.h
+++ b/khash.h
@@ -129,6 +129,9 @@ int main() {
 #include <string.h>
 #include <limits.h>
 
+#include "random.h"
+#include "siphash.h"
+
 /* compiler specific configuration */
 
 #if UINT_MAX == 0xffffffffu
@@ -197,6 +200,7 @@ static const double __ac_HASH_UPPER = 0.77;
 		khint32_t *flags; \
 		khkey_t *keys; \
 		khval_t *vals; \
+		siphash_key_t siphash_key; \
 	} kh_##name##_t;
 
 #define __KHASH_PROTOTYPES(name, khkey_t, khval_t)	 					\
@@ -210,7 +214,10 @@ static const double __ac_HASH_UPPER = 0.77;
 
 #define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
 	SCOPE kh_##name##_t *kh_init_##name(void) {							\
-		return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t));		\
+		kh_##name##_t *s = kcalloc(1, sizeof(kh_##name##_t));					\
+		if (!get_random_bytes((uint8_t *)&s->siphash_key, 16))				\
+			return NULL;									\
+		return s;										\
 	}																	\
 	SCOPE void kh_destroy_##name(kh_##name##_t *h)						\
 	{																	\
@@ -629,20 +636,13 @@ typedef const unsigned char *khwgkey_t;
 
 #define kh_wgkey_hash_equal(a, b) (memcmp(a, b, 32) == 0)
 
-static kh_inline khint_t __fnv_1a_32_hash(const unsigned char *wgkey)
-{
-	khint_t hash = 0x811c9dc5UL;
-	for (int i = 0; i < 32; ++i) {
-		hash ^= wgkey[i];
-		hash *= 16777619UL;
-	}
-	return hash;
-}
+#define __SIPHASH(key) ((khint32_t) siphash(key, 32, &h->siphash_key))
+#define __SIPHASH_u64(key) ((khint32_t) siphash_1u64(key, &h->siphash_key))
 
-#define KHASH_SET_INIT_WGKEY(name)										\
-	KHASH_INIT(name, khwgkey_t, char, 0, __fnv_1a_32_hash, kh_wgkey_hash_equal)
+#define KHASH_MAP_INIT_SECURE_INT64(name, khval_t)				\
+	KHASH_INIT(name, khint64_t, khval_t, 1, __SIPHASH_u64, kh_int64_hash_equal)
 
-#define KHASH_MAP_INIT_WGKEY(name, khval_t)								\
-	KHASH_INIT(name, khwgkey_t, khval_t, 1, __fnv_1a_32_hash, kh_wgkey_hash_equal)
+#define KHASH_MAP_INIT_SECURE_WGKEY(name, khval_t)				\
+	KHASH_INIT(name, khwgkey_t, khval_t, 1, __SIPHASH, kh_wgkey_hash_equal)
 
 #endif /* __AC_KHASH_H */
diff --git a/lease.c b/lease.c
index c6f13b3..fd51817 100644
--- a/lease.c
+++ b/lease.c
@@ -32,7 +32,7 @@ static struct ipns ipns;
 static time_t gexpires = TIME_T_MAX;
 static bool synchronized;
 
-KHASH_MAP_INIT_WGKEY(leaseht, struct wg_dynamic_lease *)
+KHASH_MAP_INIT_SECURE_WGKEY(leaseht, struct wg_dynamic_lease *)
 khash_t(leaseht) *leases_ht = NULL;
 
 static time_t get_monotonic_time()
@@ -67,6 +67,9 @@ void leases_init(const char *device_name, int interface_index, char *fname,
 
 	synchronized = false;
 	leases_ht = kh_init(leaseht);
+	if (!leases_ht)
+		fatal("kh_init()");
+
 	ipp_init(&ipns);
 
 	nlh = mnl_nlmsg_put_header(buf);
diff --git a/random.c b/random.c
index ba8acfe..e5982db 100644
--- a/random.c
+++ b/random.c
@@ -27,7 +27,7 @@
 #endif
 #endif
 
-static inline bool __attribute__((__warn_unused_result__))
+bool __attribute__((__warn_unused_result__))
 get_random_bytes(uint8_t *out, size_t len)
 {
 	ssize_t ret = 0;
diff --git a/random.h b/random.h
index 9654b2c..a6608da 100644
--- a/random.h
+++ b/random.h
@@ -6,8 +6,11 @@
 #ifndef __RANDOM_H__
 #define __RANDOM_H__
 
+#include <stdbool.h>
+#include <stddef.h>
 #include <stdint.h>
 
+bool get_random_bytes(uint8_t *out, size_t len);
 uint64_t random_u64();
 uint64_t random_bounded(uint64_t bound);
 
diff --git a/siphash.c b/siphash.c
new file mode 100644
index 0000000..63cc2c6
--- /dev/null
+++ b/siphash.c
@@ -0,0 +1,204 @@
+/* SPDX-License-Identifier: MIT
+ *
+ * Copyright (C) 2016-2019 WireGuard LLC. All Rights Reserved.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#include "siphash.h"
+
+static inline uint64_t rol64(uint64_t word, unsigned int shift)
+{
+	return (word << shift) | (word >> (64 - shift));
+}
+
+#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)
+
+#define PREAMBLE(len)                                                          \
+	uint64_t v0 = 0x736f6d6570736575ULL;                                   \
+	uint64_t v1 = 0x646f72616e646f6dULL;                                   \
+	uint64_t v2 = 0x6c7967656e657261ULL;                                   \
+	uint64_t v3 = 0x7465646279746573ULL;                                   \
+	uint64_t b = ((uint64_t)(len)) << 56;                                  \
+	v3 ^= key->key[1];                                                     \
+	v2 ^= key->key[0];                                                     \
+	v1 ^= key->key[1];                                                     \
+	v0 ^= key->key[0];
+
+#define POSTAMBLE                                                              \
+	v3 ^= b;                                                               \
+	SIPROUND;                                                              \
+	SIPROUND;                                                              \
+	v0 ^= b;                                                               \
+	v2 ^= 0xff;                                                            \
+	SIPROUND;                                                              \
+	SIPROUND;                                                              \
+	SIPROUND;                                                              \
+	SIPROUND;                                                              \
+	return (v0 ^ v1) ^ (v2 ^ v3);
+
+uint64_t __siphash_aligned(const void *data, size_t len,
+			   const siphash_key_t *key)
+{
+	const uint8_t *end = data + len - (len % sizeof(uint64_t));
+	const uint8_t left = len & (sizeof(uint64_t) - 1);
+	uint64_t m;
+	PREAMBLE(len)
+	for (; data != end; data += sizeof(uint64_t)) {
+		m = le64toh(*((uint64_t *)data));
+		v3 ^= m;
+		SIPROUND;
+		SIPROUND;
+		v0 ^= m;
+	}
+	switch (left) {
+	case 7:
+		b |= ((uint64_t)end[6]) << 48; /* fall through */
+	case 6:
+		b |= ((uint64_t)end[5]) << 40; /* fall through */
+	case 5:
+		b |= ((uint64_t)end[4]) << 32; /* fall through */
+	case 4:
+		b |= le32toh(*((uint32_t *)data));
+		break;
+	case 3:
+		b |= ((uint64_t)end[2]) << 16; /* fall through */
+	case 2:
+		b |= le16toh(*((uint16_t *)data));
+		break;
+	case 1:
+		b |= end[0];
+	}
+	POSTAMBLE
+}
+
+/**
+ * siphash_1u64 - compute 64-bit siphash PRF value of a u64
+ * @first: first u64
+ * @key: the siphash key
+ */
+uint64_t siphash_1u64(const uint64_t first, const siphash_key_t *key)
+{
+	PREAMBLE(8)
+	v3 ^= first;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= first;
+	POSTAMBLE
+}
+
+/**
+ * siphash_2u64 - compute 64-bit siphash PRF value of 2 u64
+ * @first: first u64
+ * @second: second u64
+ * @key: the siphash key
+ */
+uint64_t siphash_2u64(const uint64_t first, const uint64_t second,
+		      const siphash_key_t *key)
+{
+	PREAMBLE(16)
+	v3 ^= first;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= first;
+	v3 ^= second;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= second;
+	POSTAMBLE
+}
+
+/**
+ * siphash_3u64 - compute 64-bit siphash PRF value of 3 u64
+ * @first: first u64
+ * @second: second u64
+ * @third: third u64
+ * @key: the siphash key
+ */
+uint64_t siphash_3u64(const uint64_t first, const uint64_t second,
+		      const uint64_t third, const siphash_key_t *key)
+{
+	PREAMBLE(24)
+	v3 ^= first;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= first;
+	v3 ^= second;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= second;
+	v3 ^= third;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= third;
+	POSTAMBLE
+}
+
+/**
+ * siphash_4u64 - compute 64-bit siphash PRF value of 4 u64
+ * @first: first u64
+ * @second: second u64
+ * @third: third u64
+ * @forth: forth u64
+ * @key: the siphash key
+ */
+uint64_t siphash_4u64(const uint64_t first, const uint64_t second,
+		      const uint64_t third, const uint64_t forth,
+		      const siphash_key_t *key)
+{
+	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
+}
+
+uint64_t siphash_1u32(const uint32_t first, const siphash_key_t *key)
+{
+	PREAMBLE(4)
+	b |= first;
+	POSTAMBLE
+}
+
+uint64_t siphash_3u32(const uint32_t first, const uint32_t second,
+		      const uint32_t third, const siphash_key_t *key)
+{
+	uint64_t combined = (uint64_t)second << 32 | first;
+	PREAMBLE(12)
+	v3 ^= combined;
+	SIPROUND;
+	SIPROUND;
+	v0 ^= combined;
+	b |= third;
+	POSTAMBLE
+}
diff --git a/siphash.h b/siphash.h
new file mode 100644
index 0000000..8fefb31
--- /dev/null
+++ b/siphash.h
@@ -0,0 +1,85 @@
+/* SPDX-License-Identifier: MIT
+ *
+ * Copyright (C) 2016-2019 WireGuard LLC. All Rights Reserved.
+ *
+ * SipHash: a fast short-input PRF
+ * https://131002.net/siphash/
+ */
+
+#ifndef _LINUX_SIPHASH_H
+#define _LINUX_SIPHASH_H
+
+#ifndef _DEFAULT_SOURCE
+#define _DEFAULT_SOURCE
+#endif
+#include <endian.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stddef.h>
+
+typedef struct {
+	uint64_t key[2];
+} siphash_key_t;
+
+static inline bool siphash_key_is_zero(const siphash_key_t *key)
+{
+	return !(key->key[0] | key->key[1]);
+}
+
+uint64_t __siphash_aligned(const void *data, size_t len,
+			   const siphash_key_t *key);
+
+uint64_t siphash_1u64(const uint64_t a, const siphash_key_t *key);
+uint64_t siphash_2u64(const uint64_t a, const uint64_t b,
+		      const siphash_key_t *key);
+uint64_t siphash_3u64(const uint64_t a, const uint64_t b, const uint64_t c,
+		      const siphash_key_t *key);
+uint64_t siphash_4u64(const uint64_t a, const uint64_t b, const uint64_t c,
+		      const uint64_t d, const siphash_key_t *key);
+uint64_t siphash_1u32(const uint32_t a, const siphash_key_t *key);
+uint64_t siphash_3u32(const uint32_t a, const uint32_t b, const uint32_t c,
+		      const siphash_key_t *key);
+
+static inline uint64_t siphash_2u32(const uint32_t a, const uint32_t b,
+				    const siphash_key_t *key)
+{
+	return siphash_1u64((uint64_t)b << 32 | a, key);
+}
+static inline uint64_t siphash_4u32(const uint32_t a, const uint32_t b,
+				    const uint32_t c, const uint32_t d,
+				    const siphash_key_t *key)
+{
+	return siphash_2u64((uint64_t)b << 32 | a, (uint64_t)d << 32 | c, key);
+}
+
+static inline uint64_t ___siphash_aligned(const uint64_t *data, size_t len,
+					  const siphash_key_t *key)
+{
+	if (__builtin_constant_p(len) && len == 4)
+		return siphash_1u32(le32toh(*((const uint32_t *)data)), key);
+	if (__builtin_constant_p(len) && len == 8)
+		return siphash_1u64(le64toh(data[0]), key);
+	if (__builtin_constant_p(len) && len == 16)
+		return siphash_2u64(le64toh(data[0]), le64toh(data[1]), key);
+	if (__builtin_constant_p(len) && len == 24)
+		return siphash_3u64(le64toh(data[0]), le64toh(data[1]),
+				    le64toh(data[2]), key);
+	if (__builtin_constant_p(len) && len == 32)
+		return siphash_4u64(le64toh(data[0]), le64toh(data[1]),
+				    le64toh(data[2]), le64toh(data[3]), key);
+	return __siphash_aligned(data, len, key);
+}
+
+/**
+ * siphash - compute 64-bit siphash PRF value
+ * @data: buffer to hash
+ * @size: size of @data
+ * @key: the siphash key
+ */
+static inline uint64_t siphash(const void *data, size_t len,
+			       const siphash_key_t *key)
+{
+	return ___siphash_aligned(data, len, key);
+}
+
+#endif /* _LINUX_SIPHASH_H */
diff --git a/wg-dynamic-server.c b/wg-dynamic-server.c
index 7502aaa..566559b 100644
--- a/wg-dynamic-server.c
+++ b/wg-dynamic-server.c
@@ -40,7 +40,7 @@ static int sockfd = -1;
 static int epollfd = -1;
 static struct mnl_socket *nlsock = NULL;
 
-KHASH_MAP_INIT_INT64(allowedht, wg_key *)
+KHASH_MAP_INIT_SECURE_INT64(allowedht, wg_key *)
 khash_t(allowedht) * allowedips_ht;
 
 struct wg_dynamic_connection {
@@ -427,6 +427,8 @@ static void setup()
 		fatal("inet_pton()");
 
 	allowedips_ht = kh_init(allowedht);
+	if (!allowedips_ht)
+		fatal("kh_init()");
 
 	for (int i = 0; i < MAX_CONNECTIONS; ++i)
 		connections[i].fd = -1;