@@ -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
@@ -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 \
@@ -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<n; ++i) h = hash( k[i], len[i], h);
- *
- * By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
- * code any way you wish, private, educational, or commercial. It's free.
- *
- * See https://burtleburtle.net/bob/hash/evahash.html
- * Use for hash table lookup, or anything where one collision in 2^32 is
- * acceptable. Do NOT use for cryptographic purposes.
- *
- * --------------------------------------------------------------------
- *
- * mix -- mix 3 32-bit values reversibly.
- * For every delta with one or two bit set, and the deltas of all three
- * high bits or all three low bits, whether the original value of a,b,c
- * is almost all zero or is uniformly distributed,
- * If mix() is run forward or backward, at least 32 bits in a,b,c
- * have at least 1/4 probability of changing.
- * If mix() is run forward, every bit of c will change between 1/3 and
- * 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
- * mix() was built out of 36 single-cycle latency instructions in a
- * structure that could supported 2x parallelism, like so:
- * a -= b;
- * a -= c; x = (c>>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;
-}
@@ -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)
{
@@ -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
new file mode 100644
@@ -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 <sales@openvpn.net>
+ *
+ * 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 <https://www.gnu.org/licenses/>.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <stdlib.h>
+#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
@@ -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 */
@@ -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 \
@@ -32,6 +32,7 @@
#include <string.h>
#include <setjmp.h>
#include <cmocka.h>
+#include <siphash.h>
#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