diff --git a/CMakeLists.txt b/CMakeLists.txt index ad7de6e..789c0d4 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -571,6 +571,7 @@ src/openvpn/shaper.h src/openvpn/sig.c src/openvpn/sig.h + src/openvpn/siphash.c src/openvpn/siphash.h src/openvpn/siphash_reference.c src/openvpn/socket.c @@ -838,6 +839,9 @@ src/openvpn/list.c src/openvpn/session_id.c src/openvpn/schedule.c + src/openvpn/siphash.h + src/openvpn/siphash.c + src/openvpn/siphash_reference.c ) target_sources(test_ncp PRIVATE diff --git a/src/openvpn/Makefile.am b/src/openvpn/Makefile.am index 1f77384..f5a7621 100644 --- a/src/openvpn/Makefile.am +++ b/src/openvpn/Makefile.am @@ -128,7 +128,8 @@ session_id.c session_id.h \ shaper.c shaper.h \ sig.c sig.h \ - siphash_reference.c siphash.h \ + siphash_reference.c \ + siphash.c siphash.h \ socket.c socket.h \ socket_util.c socket_util.h \ socks.c socks.h \ diff --git a/src/openvpn/list.c b/src/openvpn/list.c index e52c778..9e80761 100644 --- a/src/openvpn/list.c +++ b/src/openvpn/list.c @@ -31,9 +31,6 @@ #include "list.h" #include "crypto.h" -#include "misc.h" - -#include "memdbg.h" struct hash * hash_init(const uint32_t n_buckets, @@ -316,178 +313,3 @@ hi->last->key = NULL; hi->bucket_marked = true; } - - -/* - * -------------------------------------------------------------------- - * hash() -- hash a variable-length key into a 32-bit value - * k : the key (the unaligned variable-length array of bytes) - * len : the length of the key, counting by bytes - * level : can be any 4-byte value - * Returns a 32-bit value. Every bit of the key affects every bit of - * the return value. Every 1-bit and 2-bit delta achieves avalanche. - * About 36+6len instructions. - * - * #define hashsize(n) ((uint32_t)1<<(n)) - * #define hashmask(n) (hashsize(n)-1) - * - * The best hash table sizes are powers of 2. There is no need to do - * mod a prime (mod is sooo slow!). If you need less than 32 bits, - * use a bitmask. For example, if you need only 10 bits, do - * h = (h & hashmask(10)); - * In which case, the hash table should have hashsize(10) elements. - * - * If you are hashing n strings (uint8_t **)k, do it like this: - * for (i=0, h=0; i>13); - * b -= c; a ^= x; - * b -= a; x = (a<<8); - * c -= a; b ^= x; - * c -= b; x = (b>>13); - * ... - * Unfortunately, superscalar Pentiums and Sparcs can't take advantage - * of that parallelism. They've also turned some of those single-cycle - * latency instructions into multi-cycle latency instructions. Still, - * this is the fastest good hash I could find. There were about 2^^68 - * to choose from. I only looked at a billion or so. - * - * James Yonan Notes: - * - * This function is faster than it looks, and appears to be - * appropriate for our usage in OpenVPN which is primarily - * for hash-table based address lookup (IPv4, IPv6, and Ethernet MAC). - * NOTE: This function is never used for cryptographic purposes, only - * to produce evenly-distributed indexes into hash tables. - * - * Benchmark results: 11.39 machine cycles per byte on a P2 266Mhz, - * and 12.1 machine cycles per byte on a - * 2.2 Ghz P4 when hashing a 6 byte string. - * -------------------------------------------------------------------- - */ - -#define mix(a, b, c) \ - { \ - a -= b; \ - a -= c; \ - a ^= (c >> 13); \ - b -= c; \ - b -= a; \ - b ^= (a << 8); \ - c -= a; \ - c -= b; \ - c ^= (b >> 13); \ - a -= b; \ - a -= c; \ - a ^= (c >> 12); \ - b -= c; \ - b -= a; \ - b ^= (a << 16); \ - c -= a; \ - c -= b; \ - c ^= (b >> 5); \ - a -= b; \ - a -= c; \ - a ^= (c >> 3); \ - b -= c; \ - b -= a; \ - b ^= (a << 10); \ - c -= a; \ - c -= b; \ - c ^= (b >> 15); \ - } - -uint64_t -hash_func(const uint8_t *k, uint32_t length, uint32_t initval) -{ - uint32_t a, b, c, len; - - /* Set up the internal state */ - len = length; - a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */ - c = initval; /* the previous hash value */ - - /*---------------------------------------- handle most of the key */ - while (len >= 12) - { - a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16) + ((uint32_t)k[3] << 24)); - b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16) + ((uint32_t)k[7] << 24)); - c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16) + ((uint32_t)k[11] << 24)); - mix(a, b, c); - k += 12; - len -= 12; - } - - /*------------------------------------- handle the last 11 bytes */ - c += length; - switch (len) /* all the case statements fall through */ - { - case 11: - c += ((uint32_t)k[10] << 24); - /* Intentional [[fallthrough]]; */ - - case 10: - c += ((uint32_t)k[9] << 16); - /* Intentional [[fallthrough]]; */ - - case 9: - c += ((uint32_t)k[8] << 8); - /* Intentional [[fallthrough]]; */ - - /* the first byte of c is reserved for the length */ - case 8: - b += ((uint32_t)k[7] << 24); - /* Intentional [[fallthrough]]; */ - - case 7: - b += ((uint32_t)k[6] << 16); - /* Intentional [[fallthrough]]; */ - - case 6: - b += ((uint32_t)k[5] << 8); - /* Intentional [[fallthrough]]; */ - - case 5: - b += k[4]; - /* Intentional [[fallthrough]]; */ - - case 4: - a += ((uint32_t)k[3] << 24); - /* Intentional [[fallthrough]]; */ - - case 3: - a += ((uint32_t)k[2] << 16); - /* Intentional [[fallthrough]]; */ - - case 2: - a += ((uint32_t)k[1] << 8); - /* Intentional [[fallthrough]]; */ - - case 1: - a += k[0]; - /* case 0: nothing left to add */ - } - mix(a, b, c); - /*-------------------------------------- report the result */ - return c; -} diff --git a/src/openvpn/list.h b/src/openvpn/list.h index cbf1abf..55bc3c8 100644 --- a/src/openvpn/list.h +++ b/src/openvpn/list.h @@ -50,7 +50,7 @@ }; -#define HASH_KEY_LEN 4 +#define HASH_KEY_LEN 16 struct hash { @@ -103,8 +103,6 @@ void hash_iterator_free(struct hash_iterator *hi); -uint64_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval); - static inline uint64_t hash_value(const struct hash *hash, const void *key) { diff --git a/src/openvpn/mroute.c b/src/openvpn/mroute.c index a5179d0..edf8239 100644 --- a/src/openvpn/mroute.c +++ b/src/openvpn/mroute.c @@ -33,6 +33,7 @@ #include "socket_util.h" #include "memdbg.h" +#include "siphash.h" void mroute_addr_init(struct mroute_addr *addr) @@ -357,8 +358,8 @@ uint64_t mroute_addr_hash_function(const void *key, const uint8_t hash_key[HASH_KEY_LEN]) { - return hash_func(mroute_addr_hash_ptr((const struct mroute_addr *)key), - mroute_addr_hash_len((const struct mroute_addr *)key), *(uint32_t *)hash_key); + return siphash_hash_func(mroute_addr_hash_ptr((const struct mroute_addr *)key), + mroute_addr_hash_len((const struct mroute_addr *)key), hash_key); } bool diff --git a/src/openvpn/siphash.c b/src/openvpn/siphash.c new file mode 100644 index 0000000..e31b708 --- /dev/null +++ b/src/openvpn/siphash.c @@ -0,0 +1,49 @@ +/* + * OpenVPN -- An application to securely tunnel IP networks + * over a single UDP port, with support for SSL/TLS-based + * session authentication and key exchange, + * packet encryption, packet authentication, and + * packet compression. + * + * Copyright (C) 2002-2026 OpenVPN Inc + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, see . + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include "syshead.h" +#include "siphash.h" +#include "buffer.h" +#include "crypto.h" +#include "list.h" + +static_assert(SIPHASH_KEY_SIZE <= HASH_KEY_LEN, "hash map key size must be at least the same as siphash key size"); + +uint64_t +siphash_hash_func(const uint8_t *k, uint32_t length, const uint8_t hash_key[SIPHASH_KEY_SIZE]) +{ + /* This is not endian-safe but we only care about local hashes here + * and reversing the byte does not make the hash functions any + * weaker or less usable */ + union + { + uint8_t out[8]; + uint64_t hash; + } ret; + siphash(k, length, hash_key, ret.out, sizeof(ret.out)); + return ret.hash; +} \ No newline at end of file diff --git a/src/openvpn/siphash.h b/src/openvpn/siphash.h index 462175c..26516e1 100644 --- a/src/openvpn/siphash.h +++ b/src/openvpn/siphash.h @@ -87,4 +87,15 @@ prng_bytes(key, SIPHASH_KEY_SIZE); } +/** + * Wrapper of the siphash function to be able to use it in the + * hash map. + * + * @param k the data to hash + * @param length length of the data to hash + * @param hash_key the siphash key + * @return a uint64_t containing the result of the hashing + */ +uint64_t +siphash_hash_func(const uint8_t *k, uint32_t length, const uint8_t hash_key[SIPHASH_KEY_SIZE]); #endif /* ifndef SIPHASH_H */ diff --git a/tests/unit_tests/openvpn/Makefile.am b/tests/unit_tests/openvpn/Makefile.am index f2c7a0d..6db611e 100644 --- a/tests/unit_tests/openvpn/Makefile.am +++ b/tests/unit_tests/openvpn/Makefile.am @@ -86,6 +86,7 @@ $(top_srcdir)/src/openvpn/mtu.c \ $(top_srcdir)/src/openvpn/win32-util.c \ $(top_srcdir)/src/openvpn/mss.c \ + $(top_srcdir)/src/openvpn/siphash.c \ $(top_srcdir)/src/openvpn/siphash_reference.c dhcp_testdriver_CFLAGS = -I$(top_srcdir)/src/openvpn -I$(top_srcdir)/src/compat @TEST_CFLAGS@ -DDHCP_UNIT_TEST @@ -383,7 +384,9 @@ $(top_srcdir)/src/openvpn/platform.c \ $(top_srcdir)/src/openvpn/list.c \ $(top_srcdir)/src/openvpn/otime.c \ - $(top_srcdir)/src/openvpn/schedule.c + $(top_srcdir)/src/openvpn/schedule.c \ + $(top_srcdir)/src/openvpn/siphash.c \ + $(top_srcdir)/src/openvpn/siphash_reference.c push_update_msg_testdriver_CFLAGS = -I$(top_srcdir)/src/openvpn \ -I$(top_srcdir)/src/compat \ diff --git a/tests/unit_tests/openvpn/test_misc.c b/tests/unit_tests/openvpn/test_misc.c index 3ebbfc1..5f03860 100644 --- a/tests/unit_tests/openvpn/test_misc.c +++ b/tests/unit_tests/openvpn/test_misc.c @@ -32,6 +32,7 @@ #include #include #include +#include #include "ssl_util.h" #include "options_util.h" @@ -135,7 +136,7 @@ { const char *str = (const char *)key; const uint32_t len = (uint32_t)strlen(str); - return hash_func((const uint8_t *)str, len, *(uint32_t *)(hash_key)); + return siphash_hash_func((const uint8_t *)str, len, hash_key); } static bool