From 360b9c8c8b4c4364b755dc0935f05e4ba4429cb0 Mon Sep 17 00:00:00 2001 From: Thomas Gschwantner Date: Sun, 8 Dec 2019 04:35:50 +0100 Subject: Use siphash for hashtables --- Makefile | 2 +- khash.h | 28 ++++---- lease.c | 5 +- random.c | 2 +- random.h | 3 + siphash.c | 204 ++++++++++++++++++++++++++++++++++++++++++++++++++++ siphash.h | 85 ++++++++++++++++++++++ wg-dynamic-server.c | 4 +- 8 files changed, 315 insertions(+), 18 deletions(-) create mode 100644 siphash.c create mode 100644 siphash.h 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 #include +#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 +#include #include +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 +#include +#include +#include + +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; -- cgit v1.2.3-59-g8ed1b