[Openvpn-devel] [L] Change in openvpn[master]: Replace custom hash_func with siphash
"plaisthos \(Code Review\) via Openvpn-devel" <[email protected]>
| Newsgroups | net.sourceforge.lists.openvpn-devel |
|---|---|
| Message-ID | <2d10ca0de63b985d9404b4bc510d8252a0127085-EmailReplacePatchSet-HTML@gerrit.openvpn.net> |
Attention is currently required from: flichtenheld.
Hello flichtenheld,
I'd like you to reexamine a change. Please visit
http://gerrit.openvpn.net/c/openvpn/+/1573?usp=email
to look at the new patch set (#8).
The following approvals got outdated and were removed:
Code-Review-1 by flichtenheld
Change subject: Replace custom hash_func with siphash
......................................................................
Replace custom hash_func with siphash
Change-Id: I807f398903ac2047530800c29949793c6f4f0ec9
Signed-off-by: Arne Schwabe <[email protected]>
---
M CMakeLists.txt
M src/openvpn/Makefile.am
M src/openvpn/list.c
M src/openvpn/list.h
M src/openvpn/mroute.c
M src/openvpn/multi.c
A src/openvpn/siphash.c
M src/openvpn/siphash.h
M tests/unit_tests/openvpn/Makefile.am
M tests/unit_tests/openvpn/test_misc.c
10 files changed, 136 insertions(+), 211 deletions(-)
git pull ssh://gerrit.openvpn.net:29418/openvpn refs/changes/73/1573/8
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 25c3ea5..5081970 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -573,6 +573,7 @@
src/openvpn/sig.c
src/openvpn/sig.h
src/openvpn/siphash.h
+ src/openvpn/siphash.c
src/openvpn/siphash_openssl.c
src/openvpn/siphash_reference.c
src/openvpn/socket.c
@@ -838,7 +839,11 @@
src/openvpn/options_util.c
src/openvpn/ssl_util.c
src/openvpn/list.c
- )
+ src/openvpn/siphash.h
+ src/openvpn/siphash.c
+ src/openvpn/siphash_reference.c
+ src/openvpn/siphash_openssl.c
+ )
target_sources(test_ncp PRIVATE
src/openvpn/crypto_epoch.c
diff --git a/src/openvpn/Makefile.am b/src/openvpn/Makefile.am
index 08c8250..4cb93e9 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.c siphash.h \
+ siphash_reference.c \
siphash_openssl.c \
socket.c socket.h \
socket_util.c socket_util.h \
diff --git a/src/openvpn/list.c b/src/openvpn/list.c
index 83b42b6..c7b1303 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, void *ctx,
@@ -316,190 +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. [email protected]. 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); \
- }
-
-/**
- * Creates a context that allows to use the hash function (hash_func) and
- * @return a new context for the use with hash_func
- */
-void *
-hash_func_new_ctx(void)
-{
- uint32_t *ctx = malloc(sizeof(uint32_t));
- *ctx = (uint32_t)get_random();
- return ctx;
-}
-
-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 5835b87..d684530 100644
--- a/src/openvpn/list.h
+++ b/src/openvpn/list.h
@@ -100,10 +100,6 @@
void hash_iterator_free(struct hash_iterator *hi);
-uint64_t hash_func(const uint8_t *k, uint32_t length, uint32_t initval);
-
-void *hash_func_new_ctx(void);
-
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 89b3ecc..e32894b 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,9 +358,8 @@
uint64_t
mroute_addr_hash_function(const void *key, void *ctx)
{
- uint32_t *iv = ctx;
- return hash_func(mroute_addr_hash_ptr((const struct mroute_addr *)key),
- mroute_addr_hash_len((const struct mroute_addr *)key), *iv);
+ return siphash_hash_func(mroute_addr_hash_ptr((const struct mroute_addr *)key),
+ mroute_addr_hash_len((const struct mroute_addr *)key), ctx);
}
bool
diff --git a/src/openvpn/multi.c b/src/openvpn/multi.c
index 002293b..a64f3bc 100644
--- a/src/openvpn/multi.c
+++ b/src/openvpn/multi.c
@@ -23,6 +23,7 @@
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
+#include "siphash.h"
#ifdef HAVE_SYS_INOTIFY_H
#include <sys/inotify.h>
@@ -290,14 +291,14 @@
* to determine which client sent an incoming packet
* which is seen on the TCP/UDP socket.
*/
- m->hash = hash_init(t->options.real_hash_size, hash_func_new_ctx(), free,
+ m->hash = hash_init(t->options.real_hash_size, siphash_new_context(), siphash_free_context,
mroute_addr_hash_function, mroute_addr_compare_function);
/*
* Virtual address hash table. Used to determine
* which client to route a packet to.
*/
- m->vhash = hash_init(t->options.virtual_hash_size, hash_func_new_ctx(), free,
+ m->vhash = hash_init(t->options.virtual_hash_size, siphash_new_context(), siphash_free_context,
mroute_addr_hash_function, mroute_addr_compare_function);
#ifdef ENABLE_MANAGEMENT
diff --git a/src/openvpn/siphash.c b/src/openvpn/siphash.c
new file mode 100644
index 0000000..52a6a4e
--- /dev/null
+++ b/src/openvpn/siphash.c
@@ -0,0 +1,74 @@
+/*
+ * OpenVPN -- An application to securely tunnel IP networks
+ * over a single TCP/UDP port, with support for SSL/TLS-based
+ * session authentication and key exchange,
+ * packet encryption, packet authentication, and
+ * packet compression.
+ *
+ * Copyright (C) 2025 OpenVPN Inc <[email protected]>
+ * Copyright (C) 2025 Arne Schwabe <[email protected]>
+ *
+ *
+ * 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, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#elif defined(_MSC_VER)
+#include "config-msvc.h"
+#endif
+
+#include <stdlib.h>
+#include "syshead.h"
+#include "siphash.h"
+#include "buffer.h"
+#include "crypto.h"
+
+void *
+siphash_new_context(void)
+{
+ struct siphash_ctx *ctx;
+ ALLOC_OBJ_CLEAR(ctx, struct siphash_ctx);
+
+ prng_bytes(ctx->key, SIPHASH_KEY_SIZE);
+
+ siphash_cryptolib_init(8);
+ return ctx;
+}
+
+void
+siphash_free_context(void *ctx)
+{
+ struct siphash_ctx *sctx = ctx;
+
+ if (sctx->cryptlib_ctx)
+ {
+ siphash_cryptolib_uninit(sctx->cryptlib_ctx);
+ }
+ free(ctx);
+}
+
+uint64_t
+siphash_hash_func(const uint8_t *k, uint32_t length, void *ctx)
+{
+ struct siphash_ctx *sctx = ctx;
+
+ union
+ {
+ uint8_t out[8];
+ uint64_t hash;
+ } ret;
+ siphash(sctx, k, length, 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 07b087e..5464f90 100644
--- a/src/openvpn/siphash.h
+++ b/src/openvpn/siphash.h
@@ -25,8 +25,15 @@
/* siphash always uses 128-bit keys */
#define SIPHASH_KEY_SIZE 16
+struct siphash_ctx
+{
+ uint8_t key[SIPHASH_KEY_SIZE];
+ void *cryptlib_ctx;
+};
+
/* Prototypes for an implementation of SIPHASH in a crypto library */
+
/**
* Calculates SIPHASH using the crypto library function.
*/
@@ -68,17 +75,44 @@
siphash_cryptolib_available(void *sip_context);
static inline int
-siphash(void *ctx, const void *in, size_t inlen, const void *k,
- uint8_t *out, size_t outlen)
+siphash(void *ctx, const void *in, size_t inlen, uint8_t *out, size_t outlen)
{
- if (siphash_cryptolib_available(ctx))
+ struct siphash_ctx *sctx = ctx;
+ if (siphash_cryptolib_available(sctx->cryptlib_ctx))
{
- return siphash_cryptolib(ctx, in, inlen, k, out, outlen);
+ return siphash_cryptolib(ctx, in, inlen, sctx->key, out, outlen);
}
else
{
- return siphash_reference(in, inlen, k, out, outlen);
+ return siphash_reference(in, inlen, sctx->key, out, outlen);
}
}
+/**
+ * Allocates the resources for a siphash context and returns a pointer to
+ * this context. The context must be freed with siphash_free_context
+ */
+void *
+siphash_new_context(void);
+
+/**
+ * Releases the resources assigned to a siphash context
+ * @param ctx the context previously allocated by siphash_new_context
+ */
+void
+siphash_free_context(void *ctx);
+
+/**
+ * Wrapper of the siphash function to easily use it in the
+ * hash map.
+ *
+ * @param k the data to hash
+ * @param length length of the data to hash
+ * @param ctx the siphash context
+ * @return a unit64_t containing the result of the hashing
+ */
+uint64_t
+siphash_hash_func(const uint8_t *k, uint32_t length, void *ctx);
+
+
#endif /* ifndef SIPHASH_H */
\ No newline at end of file
diff --git a/tests/unit_tests/openvpn/Makefile.am b/tests/unit_tests/openvpn/Makefile.am
index 9e1e216..de18844 100644
--- a/tests/unit_tests/openvpn/Makefile.am
+++ b/tests/unit_tests/openvpn/Makefile.am
@@ -85,6 +85,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_openssl.c \
$(top_srcdir)/src/openvpn/siphash_reference.c
@@ -380,7 +381,10 @@
$(top_srcdir)/src/openvpn/ssl_util.c \
$(top_srcdir)/src/openvpn/win32-util.c \
$(top_srcdir)/src/openvpn/platform.c \
- $(top_srcdir)/src/openvpn/list.c
+ $(top_srcdir)/src/openvpn/list.c \
+ $(top_srcdir)/src/openvpn/siphash.c \
+ $(top_srcdir)/src/openvpn/siphash_openssl.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 7f22ad2..7df13506 100644
--- a/tests/unit_tests/openvpn/test_misc.c
+++ b/tests/unit_tests/openvpn/test_misc.c
@@ -32,6 +32,7 @@
#include <string.h>
#include <setjmp.h>
#include <cmocka.h>
+#include <siphash.h>
#include "ssl_util.h"
#include "options_util.h"
@@ -130,10 +131,9 @@
static uint64_t
word_hash_function(const void *key, void *ctx)
{
- uint32_t *iv = (uint32_t *)ctx;
const char *str = (const char *)key;
const uint32_t len = (uint32_t)strlen(str);
- return hash_func((const uint8_t *)str, len, *iv);
+ return siphash_hash_func((const uint8_t *)str, len, ctx);
}
static bool
@@ -176,8 +176,8 @@
* word frequency algorithm.
*/
struct gc_arena gc = gc_new();
- struct hash *hash = hash_init(10000, hash_func_new_ctx(), free, word_hash_function, word_compare_function);
- struct hash *nhash = hash_init(256, hash_func_new_ctx(), free, word_hash_function, word_compare_function);
+ struct hash *hash = hash_init(10000, siphash_new_context(), siphash_free_context, word_hash_function, word_compare_function);
+ struct hash *nhash = hash_init(256, siphash_new_context(), siphash_free_context, word_hash_function, word_compare_function);
printf("hash_init n_buckets=%u mask=0x%08x\n", hash->n_buckets, hash->mask);
--
To view, visit http://gerrit.openvpn.net/c/openvpn/+/1573?usp=email
To unsubscribe, or for help writing mail filters, visit http://gerrit.openvpn.net/settings?usp=email
Gerrit-MessageType: newpatchset
Gerrit-Project: openvpn
Gerrit-Branch: master
Gerrit-Change-Id: I807f398903ac2047530800c29949793c6f4f0ec9
Gerrit-Change-Number: 1573
Gerrit-PatchSet: 8
Gerrit-Owner: plaisthos <[email protected]>
Gerrit-Reviewer: flichtenheld <[email protected]>
Gerrit-CC: openvpn-devel <[email protected]>
Gerrit-Attention: flichtenheld <[email protected]>
_______________________________________________
Openvpn-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/openvpn-devel