* [PATCH v2] lib/hash: add siphash
2024-02-27 17:39 [PATCH] lib/hash: add SipHash function Stephen Hemminger
@ 2024-02-27 19:14 ` Stephen Hemminger
2024-02-27 21:57 ` Mattias Rönnblom
2024-02-29 0:32 ` [PATCH v3] " Stephen Hemminger
` (3 subsequent siblings)
4 siblings, 1 reply; 12+ messages in thread
From: Stephen Hemminger @ 2024-02-27 19:14 UTC (permalink / raw)
To: dev
Cc: Stephen Hemminger, Yipeng Wang, Sameh Gobriel, Bruce Richardson,
Vladimir Medvedkin
Add SipHash which is a fast and cryptographicly sound hash
created by Jean-Philippe Aumasson and Daniel J. Bernstein.
Siphash is widely used by Linux, FreeBSD, OpenBSD and other
projects because it is fast and resistant to DoS attacks.
This version is designed to be useful as alternative hash
with cuckoo hash in DPDK.
Implementation is based of the public domain and Creative
Common license reference version as well as some optimizations
from the GPL-2 or BSD-3 licensed version in Linux.
Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
---
v2 - fix non x86 accessor
app/test/test_hash_functions.c | 71 ++++++++++++++-
lib/hash/meson.build | 2 +
lib/hash/rte_siphash.c | 156 +++++++++++++++++++++++++++++++++
lib/hash/rte_siphash.h | 84 ++++++++++++++++++
lib/hash/version.map | 7 ++
5 files changed, 316 insertions(+), 4 deletions(-)
create mode 100644 lib/hash/rte_siphash.c
create mode 100644 lib/hash/rte_siphash.h
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 70820d1f1976..3bffbe4ed4ba 100644
--- a/app/test/test_hash_functions.c
+++ b/app/test/test_hash_functions.c
@@ -15,6 +15,7 @@
#include <rte_hash.h>
#include <rte_jhash.h>
#include <rte_hash_crc.h>
+#include <rte_siphash.h>
#include "test.h"
@@ -52,6 +53,42 @@ static uint32_t hash_values_crc[2][12] = {{
}
};
+static uint32_t hash_values_hsiphash[2][12] = {
+ {
+ 0x8e01e473, 0xc41e3669,
+ 0x813e4dbd, 0x7ebe2eea,
+ 0x33a5c5b7, 0xc910629b,
+ 0xba50237f, 0xbbc870c6,
+ 0x95124362, 0x850f8e0d,
+ 0x192ff266, 0xb41d8206,
+ }, {
+ 0x66200aa0, 0x769e7201,
+ 0x0e934d03, 0x96d7c892,
+ 0xb4643534, 0xcb758913,
+ 0x498b66e9, 0x116b4082,
+ 0x603030dc, 0x644b608b,
+ 0x74b29c27, 0x513f3a9c,
+ }
+};
+
+static uint64_t hash_values_siphash[2][12] = {
+ {
+ 0x8b5a0baa49fbc58d, 0x62c3506f27376c25,
+ 0xef7bdf3ee24abec8, 0xc72b1c24fc2f7938,
+ 0xc902632ed88f897f, 0xab631e00063006f5,
+ 0x7b821577565ea3a4, 0x8b19265d1c12cdc7,
+ 0x610e7ab6ada60b22, 0x3c6f1970dd62f235,
+ 0x4b8db19fd6940031, 0xa43827a530b08989,
+ }, {
+ 0x86e1bbae2893aaf1, 0x9c05614a696cda03,
+ 0x9ee31847083019c3, 0x600e860c97264e31,
+ 0xda8721038e4972bc, 0xfeedeb1b8bfe5d1e,
+ 0xb2d6388922af426f, 0x7d05b8e82e38cf30,
+ 0x439caa6ecd0b628d, 0x6d4c4ba6f3f2aed5,
+ 0x5622bb0da20658ff, 0x409d76de4adcd475,
+ }
+};
+
/*******************************************************************************
* Hash function performance test configuration section. Each performance test
* will be performed HASHTEST_ITERATIONS times.
@@ -61,9 +98,11 @@ static uint32_t hash_values_crc[2][12] = {{
*/
#define HASHTEST_ITERATIONS 1000000
#define MAX_KEYSIZE 64
-static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
-static uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
-static uint32_t hashtest_key_lens[] = {
+static const rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc, rte_hsiphash};
+static const uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
+static const uint64_t hashtest_initkeys[] = {0, UINT64_C(0xfeedc0dedeadbeef)};
+
+static const uint32_t hashtest_key_lens[] = {
1, 2, /* Unusual key sizes */
4, 8, 16, 32, 48, 64, /* standard key sizes */
9, /* IPv4 SRC + DST + protocol, unpadded */
@@ -85,6 +124,9 @@ get_hash_name(rte_hash_function f)
if (f == rte_hash_crc)
return "rte_hash_crc";
+ if (f == rte_hsiphash)
+ return "hsiphash";
+
return "UnknownHash";
}
@@ -126,6 +168,7 @@ run_hash_func_perf_tests(void)
printf(" Number of iterations for each test = %d\n",
HASHTEST_ITERATIONS);
printf("Hash Func. , Key Length (bytes), Initial value, Ticks/Op.\n");
+ fflush(stdout);
for (i = 0; i < RTE_DIM(hashtest_initvals); i++) {
for (j = 0; j < RTE_DIM(hashtest_key_lens); j++) {
@@ -147,13 +190,15 @@ verify_precalculated_hash_func_tests(void)
{
unsigned i, j;
uint8_t key[64];
- uint32_t hash;
for (i = 0; i < 64; i++)
key[i] = (uint8_t) i;
for (i = 0; i < RTE_DIM(hashtest_key_lens); i++) {
for (j = 0; j < RTE_DIM(hashtest_initvals); j++) {
+ uint32_t hash;
+ uint64_t shash;
+
hash = rte_jhash(key, hashtest_key_lens[i],
hashtest_initvals[j]);
if (hash != hash_values_jhash[j][i]) {
@@ -173,6 +218,24 @@ verify_precalculated_hash_func_tests(void)
hash_values_crc[j][i], hash);
return -1;
}
+
+ hash = rte_hsiphash(key, hashtest_key_lens[i], hashtest_initvals[j]);
+ if (hash != hash_values_hsiphash[j][i]) {
+ printf("Hsiphash for %u bytes with initial value 0x%x."
+ "Expected 0x%x, but got 0x%x\n",
+ hashtest_key_lens[i], hashtest_initvals[j],
+ hash_values_hsiphash[j][i], hash);
+ return -1;
+ }
+
+ shash = rte_siphash(key, hashtest_key_lens[i], hashtest_initkeys[j]);
+ if (shash != hash_values_siphash[j][i]) {
+ printf("siphash for %u bytes with initial %#"PRIx64"."
+ "Expected %#"PRIx64", but got %#"PRIx64"\n",
+ hashtest_key_lens[i], hashtest_initkeys[j],
+ hash_values_siphash[j][i], shash);
+ return -1;
+ }
}
}
diff --git a/lib/hash/meson.build b/lib/hash/meson.build
index 277eb9fa9366..913855124d2b 100644
--- a/lib/hash/meson.build
+++ b/lib/hash/meson.build
@@ -6,6 +6,7 @@ headers = files(
'rte_hash_crc.h',
'rte_hash.h',
'rte_jhash.h',
+ 'rte_siphash.h',
'rte_thash.h',
'rte_thash_gfni.h',
)
@@ -21,6 +22,7 @@ sources = files(
'rte_cuckoo_hash.c',
'rte_hash_crc.c',
'rte_fbk_hash.c',
+ 'rte_siphash.c',
'rte_thash.c',
'rte_thash_gfni.c',
)
diff --git a/lib/hash/rte_siphash.c b/lib/hash/rte_siphash.c
new file mode 100644
index 000000000000..75a350f27c19
--- /dev/null
+++ b/lib/hash/rte_siphash.c
@@ -0,0 +1,156 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ *
+ * Based on code reference code licensed as CC0 and MIT.
+ * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+ * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
+ */
+
+#include <stdint.h>
+
+#include <rte_common.h>
+#include "rte_siphash.h"
+
+static __rte_always_inline uint64_t
+rol64(uint64_t x, unsigned int b)
+{
+ return (x << b) | (x >> (64 - b));
+}
+
+#if defined(RTE_ARCH_X86)
+static __rte_always_inline uint64_t u8to64_le(const uint8_t *p)
+{
+ return *(const uint64_t *)p;
+}
+
+static __rte_always_inline uint32_t u8to32_le(const uint8_t *p)
+{
+ return *(const uint32_t *)p;
+}
+
+static __rte_always_inline uint16_t u8to16_le(const uint8_t *p)
+{
+ return *(const uint16_t *)p;
+}
+#else
+/* Portable version */
+static __rte_always_inline uint64_t u8to64_le(const uint8_t *p)
+{
+ return (uint64_t)p[0] | (uint64_t)p[1] << 8 |
+ (uint64_t)p[2] << 16 | (uint64_t)p[3] << 24 |
+ (uint64_t)p[4] << 32 | (uint64_t)p[5] << 40 |
+ (uint64_t)p[6] << 48 | (uint64_t)p[7] << 56;
+}
+
+static __rte_always_inline uint32_t u8to32_le(const uint8_t *p)
+{
+ return (uint32_t)p[0] | (uint32_t)p[1] << 8 |
+ (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24;
+}
+
+static __rte_always_inline uint16_t u8to16_le(const uint8_t *p)
+{
+ return (uint16_t)p[0] | (uint16_t)p[1] << 8;
+}
+#endif
+
+#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)
+
+/*
+ * Use a 64bit version of SipHash for both full and
+ * half versions, The difference is the number of rounds.
+ */
+static inline uint64_t
+siphash(const uint8_t *data, uint32_t len, uint64_t key[2],
+ const unsigned int cround, const unsigned int dround)
+{
+ const uint32_t left = len & 7;
+ const uint8_t *end = data + len - left;
+ unsigned int i;
+ uint64_t m;
+ uint64_t v0 = UINT64_C(0x736f6d6570736575);
+ uint64_t v1 = UINT64_C(0x646f72616e646f6d);
+ uint64_t v2 = UINT64_C(0x6c7967656e657261);
+ uint64_t v3 = UINT64_C(0x7465646279746573);
+ uint64_t b = (uint64_t)len << 56;
+
+ v3 ^= key[1];
+ v2 ^= key[0];
+ v1 ^= key[1];
+ v0 ^= key[0];
+
+ for (; data != end; data += 8) {
+ m = u8to64_le(data);
+ v3 ^= m;
+
+ for (i = 0; i < cround; i++)
+ SIPROUND;
+
+ v0 ^= m;
+ }
+
+ switch (left) {
+ case 7:
+ b |= ((uint64_t)end[6]) << 48;
+ /* fallthrough */
+ case 6:
+ b |= ((uint64_t)end[5]) << 40;
+ /* fallthrough */
+ case 5:
+ b |= ((uint64_t)end[4]) << 32;
+ /* fallthrough */
+ case 4:
+ b |= u8to32_le(end);
+ break;
+ case 3:
+ b |= ((uint64_t)end[2]) << 16;
+ /* fallthrough */
+ case 2:
+ b |= u8to16_le(end);
+ break;
+ case 1:
+ b |= data[0];
+ }
+
+ v3 ^= b;
+ for (i = 0; i < cround; i++)
+ SIPROUND;
+
+ v0 ^= b;
+ v2 ^= 0xff;
+
+ for (i = 0; i < dround; i++)
+ SIPROUND;
+
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
+
+uint64_t
+rte_siphash(const void *data, uint32_t len, uint64_t init_val)
+{
+ uint64_t key[2] = { init_val };
+
+ return siphash(data, len, key, 2, 4);
+}
+
+uint32_t
+rte_hsiphash(const void *data, uint32_t len, uint32_t init_val)
+{
+ uint64_t key[2] = { init_val };
+
+ return siphash(data, len, key, 1, 3);
+}
diff --git a/lib/hash/rte_siphash.h b/lib/hash/rte_siphash.h
new file mode 100644
index 000000000000..9ac417517f33
--- /dev/null
+++ b/lib/hash/rte_siphash.h
@@ -0,0 +1,84 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ *
+ * Based on code reference code licensed as CC0 and MIT.
+ * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+ * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
+ */
+
+#ifndef _RTE_SIPHASH_H
+#define _RTE_SIPHASH_H
+
+/**
+ * @file
+ *
+ * SipHash is a family of pseudorandom functions (PRFs) optimized for speed on short messages.
+ *
+ * SipHash was designed in 2012 by Jean-Philippe Aumasson and Daniel J. Bernstein as a defense
+ * against hash-flooding DoS attacks.
+ *
+ * SipHash is simpler and faster on short messages than previous cryptographic algorithms,
+ * such as MACs based on universal hashing.
+ * Competitive in performance with insecure non-cryptographic algorithms.
+ *
+ * Cryptographically secure, with no sign of weakness despite multiple cryptanalysis projects
+ * by leading cryptographers.
+ *
+ * Battle-tested, with successful integration in OSs (Linux kernel, OpenBSD, FreeBSD, FreeRTOS),
+ * languages (Perl, Python, Ruby, etc.), libraries (OpenSSL libcrypto, Sodium, etc.)
+ * and applications (Wireguard, Redis, etc.).
+ *
+ * As a secure pseudorandom function (a.k.a. keyed hash function), SipHash can also be used as
+ * a secure message authentication code (MAC). But SipHash is not a hash in the sense of
+ * general-purpose key-less hash function such as BLAKE3 or SHA-3.
+ * SipHash should therefore always be used with a secret key in order to be secure.
+ * siphash functions.
+ *
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdint.h>
+
+#include <rte_compat.h>
+
+/**
+ * Compute a SipHash-2-4
+ * uses a 64 bit key; does 2 compression rounds, and 4 finalization rounds.
+ *
+ * @param data
+ * Data to perform hash on.
+ * @param len
+ * How many bytes to use to calculate hash value.
+ * @param initval
+ * Value to initialise hash generator.
+ * @return
+ * 64bit calculated hash value.
+ */
+__rte_experimental
+uint64_t
+rte_siphash(const void *data, uint32_t len, uint64_t init_val);
+
+/**
+ * Compute Siphash-1-3;
+ * uses a 32 bit key; does 1 compression round, and 3 finalization rounds.
+ *
+ * @param data
+ * Data to perform hash on.
+ * @param len
+ * How many bytes to use to calculate hash value.
+ * @param initval
+ * Value to initialise hash generator.
+ * @return
+ * 32bit calculated hash value.
+ */
+__rte_experimental
+uint32_t
+rte_hsiphash(const void *data, uint32_t len, uint32_t init_val);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_SIPHASH_H */
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 6b2afebf6b46..16221fc1d8c7 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -48,3 +48,10 @@ DPDK_24 {
local: *;
};
+
+EXPERIMENTAL {
+ global:
+
+ rte_siphash;
+ rte_hsiphash;
+};
--
2.43.0
^ permalink raw reply [flat|nested] 12+ messages in thread* Re: [PATCH v2] lib/hash: add siphash
2024-02-27 19:14 ` [PATCH v2] lib/hash: add siphash Stephen Hemminger
@ 2024-02-27 21:57 ` Mattias Rönnblom
2024-02-27 22:34 ` Stephen Hemminger
0 siblings, 1 reply; 12+ messages in thread
From: Mattias Rönnblom @ 2024-02-27 21:57 UTC (permalink / raw)
To: Stephen Hemminger, dev
Cc: Yipeng Wang, Sameh Gobriel, Bruce Richardson, Vladimir Medvedkin
On 2024-02-27 20:14, Stephen Hemminger wrote:
> Add SipHash which is a fast and cryptographicly sound hash
> created by Jean-Philippe Aumasson and Daniel J. Bernstein.
> Siphash is widely used by Linux, FreeBSD, OpenBSD and other
> projects because it is fast and resistant to DoS attacks.
> This version is designed to be useful as alternative hash
> with cuckoo hash in DPDK.
>
> Implementation is based of the public domain and Creative
> Common license reference version as well as some optimizations
> from the GPL-2 or BSD-3 licensed version in Linux.
>
> Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
> ---
> v2 - fix non x86 accessor
>
> app/test/test_hash_functions.c | 71 ++++++++++++++-
> lib/hash/meson.build | 2 +
> lib/hash/rte_siphash.c | 156 +++++++++++++++++++++++++++++++++
> lib/hash/rte_siphash.h | 84 ++++++++++++++++++
> lib/hash/version.map | 7 ++
> 5 files changed, 316 insertions(+), 4 deletions(-)
> create mode 100644 lib/hash/rte_siphash.c
> create mode 100644 lib/hash/rte_siphash.h
>
> diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
> index 70820d1f1976..3bffbe4ed4ba 100644
> --- a/app/test/test_hash_functions.c
> +++ b/app/test/test_hash_functions.c
> @@ -15,6 +15,7 @@
> #include <rte_hash.h>
> #include <rte_jhash.h>
> #include <rte_hash_crc.h>
> +#include <rte_siphash.h>
>
> #include "test.h"
>
> @@ -52,6 +53,42 @@ static uint32_t hash_values_crc[2][12] = {{
> }
> };
>
> +static uint32_t hash_values_hsiphash[2][12] = {
> + {
> + 0x8e01e473, 0xc41e3669,
> + 0x813e4dbd, 0x7ebe2eea,
> + 0x33a5c5b7, 0xc910629b,
> + 0xba50237f, 0xbbc870c6,
> + 0x95124362, 0x850f8e0d,
> + 0x192ff266, 0xb41d8206,
> + }, {
> + 0x66200aa0, 0x769e7201,
> + 0x0e934d03, 0x96d7c892,
> + 0xb4643534, 0xcb758913,
> + 0x498b66e9, 0x116b4082,
> + 0x603030dc, 0x644b608b,
> + 0x74b29c27, 0x513f3a9c,
> + }
> +};
> +
> +static uint64_t hash_values_siphash[2][12] = {
> + {
> + 0x8b5a0baa49fbc58d, 0x62c3506f27376c25,
> + 0xef7bdf3ee24abec8, 0xc72b1c24fc2f7938,
> + 0xc902632ed88f897f, 0xab631e00063006f5,
> + 0x7b821577565ea3a4, 0x8b19265d1c12cdc7,
> + 0x610e7ab6ada60b22, 0x3c6f1970dd62f235,
> + 0x4b8db19fd6940031, 0xa43827a530b08989,
> + }, {
> + 0x86e1bbae2893aaf1, 0x9c05614a696cda03,
> + 0x9ee31847083019c3, 0x600e860c97264e31,
> + 0xda8721038e4972bc, 0xfeedeb1b8bfe5d1e,
> + 0xb2d6388922af426f, 0x7d05b8e82e38cf30,
> + 0x439caa6ecd0b628d, 0x6d4c4ba6f3f2aed5,
> + 0x5622bb0da20658ff, 0x409d76de4adcd475,
> + }
> +};
> +
> /*******************************************************************************
> * Hash function performance test configuration section. Each performance test
> * will be performed HASHTEST_ITERATIONS times.
> @@ -61,9 +98,11 @@ static uint32_t hash_values_crc[2][12] = {{
> */
> #define HASHTEST_ITERATIONS 1000000
> #define MAX_KEYSIZE 64
> -static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
> -static uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
> -static uint32_t hashtest_key_lens[] = {
> +static const rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc, rte_hsiphash};
> +static const uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
> +static const uint64_t hashtest_initkeys[] = {0, UINT64_C(0xfeedc0dedeadbeef)};
> +
> +static const uint32_t hashtest_key_lens[] = {
> 1, 2, /* Unusual key sizes */
> 4, 8, 16, 32, 48, 64, /* standard key sizes */
> 9, /* IPv4 SRC + DST + protocol, unpadded */
> @@ -85,6 +124,9 @@ get_hash_name(rte_hash_function f)
> if (f == rte_hash_crc)
> return "rte_hash_crc";
>
> + if (f == rte_hsiphash)
> + return "hsiphash";
> +
> return "UnknownHash";
> }
>
> @@ -126,6 +168,7 @@ run_hash_func_perf_tests(void)
> printf(" Number of iterations for each test = %d\n",
> HASHTEST_ITERATIONS);
> printf("Hash Func. , Key Length (bytes), Initial value, Ticks/Op.\n");
> + fflush(stdout);
>
> for (i = 0; i < RTE_DIM(hashtest_initvals); i++) {
> for (j = 0; j < RTE_DIM(hashtest_key_lens); j++) {
> @@ -147,13 +190,15 @@ verify_precalculated_hash_func_tests(void)
> {
> unsigned i, j;
> uint8_t key[64];
> - uint32_t hash;
>
> for (i = 0; i < 64; i++)
> key[i] = (uint8_t) i;
>
> for (i = 0; i < RTE_DIM(hashtest_key_lens); i++) {
> for (j = 0; j < RTE_DIM(hashtest_initvals); j++) {
> + uint32_t hash;
> + uint64_t shash;
> +
> hash = rte_jhash(key, hashtest_key_lens[i],
> hashtest_initvals[j]);
> if (hash != hash_values_jhash[j][i]) {
> @@ -173,6 +218,24 @@ verify_precalculated_hash_func_tests(void)
> hash_values_crc[j][i], hash);
> return -1;
> }
> +
> + hash = rte_hsiphash(key, hashtest_key_lens[i], hashtest_initvals[j]);
> + if (hash != hash_values_hsiphash[j][i]) {
> + printf("Hsiphash for %u bytes with initial value 0x%x."
> + "Expected 0x%x, but got 0x%x\n",
> + hashtest_key_lens[i], hashtest_initvals[j],
> + hash_values_hsiphash[j][i], hash);
> + return -1;
> + }
> +
> + shash = rte_siphash(key, hashtest_key_lens[i], hashtest_initkeys[j]);
> + if (shash != hash_values_siphash[j][i]) {
> + printf("siphash for %u bytes with initial %#"PRIx64"."
> + "Expected %#"PRIx64", but got %#"PRIx64"\n",
> + hashtest_key_lens[i], hashtest_initkeys[j],
> + hash_values_siphash[j][i], shash);
> + return -1;
> + }
> }
> }
>
> diff --git a/lib/hash/meson.build b/lib/hash/meson.build
> index 277eb9fa9366..913855124d2b 100644
> --- a/lib/hash/meson.build
> +++ b/lib/hash/meson.build
> @@ -6,6 +6,7 @@ headers = files(
> 'rte_hash_crc.h',
> 'rte_hash.h',
> 'rte_jhash.h',
> + 'rte_siphash.h',
> 'rte_thash.h',
> 'rte_thash_gfni.h',
> )
> @@ -21,6 +22,7 @@ sources = files(
> 'rte_cuckoo_hash.c',
> 'rte_hash_crc.c',
> 'rte_fbk_hash.c',
> + 'rte_siphash.c',
> 'rte_thash.c',
> 'rte_thash_gfni.c',
> )
> diff --git a/lib/hash/rte_siphash.c b/lib/hash/rte_siphash.c
> new file mode 100644
> index 000000000000..75a350f27c19
> --- /dev/null
> +++ b/lib/hash/rte_siphash.c
> @@ -0,0 +1,156 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + *
> + * Based on code reference code licensed as CC0 and MIT.
> + * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
> + * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
> + */
> +
> +#include <stdint.h>
> +
> +#include <rte_common.h>
> +#include "rte_siphash.h"
> +
> +static __rte_always_inline uint64_t
> +rol64(uint64_t x, unsigned int b)
> +{
> + return (x << b) | (x >> (64 - b));
> +}
> +
> +#if defined(RTE_ARCH_X86)
> +static __rte_always_inline uint64_t u8to64_le(const uint8_t *p)
> +{
> + return *(const uint64_t *)p;
> +}
> +
> +static __rte_always_inline uint32_t u8to32_le(const uint8_t *p)
> +{
> + return *(const uint32_t *)p;
> +}
> +
> +static __rte_always_inline uint16_t u8to16_le(const uint8_t *p)
> +{
> + return *(const uint16_t *)p;
> +}
> +#else
> +/* Portable version */
> +static __rte_always_inline uint64_t u8to64_le(const uint8_t *p)
> +{
> + return (uint64_t)p[0] | (uint64_t)p[1] << 8 |
> + (uint64_t)p[2] << 16 | (uint64_t)p[3] << 24 |
> + (uint64_t)p[4] << 32 | (uint64_t)p[5] << 40 |
> + (uint64_t)p[6] << 48 | (uint64_t)p[7] << 56;
> +}
> +
The portable and x86 version will compile to the same thing on x86.
A simpler implementation would be
static __rte_always_inline uint64_t
u8to64_le(const uint8_t *p)
{
uint64_t w;
memcpy(&w, p, sizeof(w));
return rte_cpu_to_le(w);
}
...which probably also compiles to the same code.
Do you want the same hash value on big and little endian, or why the
conversion?
> +static __rte_always_inline uint32_t u8to32_le(const uint8_t *p)
> +{
> + return (uint32_t)p[0] | (uint32_t)p[1] << 8 |
> + (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24;
> +}
> +
> +static __rte_always_inline uint16_t u8to16_le(const uint8_t *p)
> +{
> + return (uint16_t)p[0] | (uint16_t)p[1] << 8;
> +}
> +#endif
> +
> +#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)
> +
> +/*
> + * Use a 64bit version of SipHash for both full and
> + * half versions, The difference is the number of rounds.
> + */
> +static inline uint64_t
> +siphash(const uint8_t *data, uint32_t len, uint64_t key[2],
> + const unsigned int cround, const unsigned int dround)
> +{
> + const uint32_t left = len & 7;
> + const uint8_t *end = data + len - left;
> + unsigned int i;
> + uint64_t m;
> + uint64_t v0 = UINT64_C(0x736f6d6570736575);
> + uint64_t v1 = UINT64_C(0x646f72616e646f6d);
> + uint64_t v2 = UINT64_C(0x6c7967656e657261);
> + uint64_t v3 = UINT64_C(0x7465646279746573);
> + uint64_t b = (uint64_t)len << 56;
> +
> + v3 ^= key[1];
> + v2 ^= key[0];
> + v1 ^= key[1];
> + v0 ^= key[0];
> +
> + for (; data != end; data += 8) {
> + m = u8to64_le(data);
> + v3 ^= m;
> +
> + for (i = 0; i < cround; i++)
> + SIPROUND;
> +
> + v0 ^= m;
> + }
> +
> + switch (left) {
> + case 7:
> + b |= ((uint64_t)end[6]) << 48;
> + /* fallthrough */
> + case 6:
> + b |= ((uint64_t)end[5]) << 40;
> + /* fallthrough */
> + case 5:
> + b |= ((uint64_t)end[4]) << 32;
> + /* fallthrough */
> + case 4:
> + b |= u8to32_le(end);
> + break;
> + case 3:
> + b |= ((uint64_t)end[2]) << 16;
> + /* fallthrough */
> + case 2:
> + b |= u8to16_le(end);
> + break;
> + case 1:
> + b |= data[0];
> + }
> +
> + v3 ^= b;
> + for (i = 0; i < cround; i++)
> + SIPROUND;
> +
> + v0 ^= b;
> + v2 ^= 0xff;
> +
> + for (i = 0; i < dround; i++)
> + SIPROUND;
> +
> + return (v0 ^ v1) ^ (v2 ^ v3);
> +}
> +
> +uint64_t
> +rte_siphash(const void *data, uint32_t len, uint64_t init_val)
> +{
> + uint64_t key[2] = { init_val };
> +
> + return siphash(data, len, key, 2, 4);
> +}
> +
> +uint32_t
> +rte_hsiphash(const void *data, uint32_t len, uint32_t init_val)
> +{
> + uint64_t key[2] = { init_val };
> +
> + return siphash(data, len, key, 1, 3);
> +}
> diff --git a/lib/hash/rte_siphash.h b/lib/hash/rte_siphash.h
> new file mode 100644
> index 000000000000..9ac417517f33
> --- /dev/null
> +++ b/lib/hash/rte_siphash.h
> @@ -0,0 +1,84 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + *
> + * Based on code reference code licensed as CC0 and MIT.
> + * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
> + * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
> + */
> +
> +#ifndef _RTE_SIPHASH_H
> +#define _RTE_SIPHASH_H
> +
> +/**
> + * @file
> + *
> + * SipHash is a family of pseudorandom functions (PRFs) optimized for speed on short messages.
> + *
> + * SipHash was designed in 2012 by Jean-Philippe Aumasson and Daniel J. Bernstein as a defense
> + * against hash-flooding DoS attacks.
> + *
> + * SipHash is simpler and faster on short messages than previous cryptographic algorithms,
> + * such as MACs based on universal hashing.
> + * Competitive in performance with insecure non-cryptographic algorithms.
> + *
> + * Cryptographically secure, with no sign of weakness despite multiple cryptanalysis projects
> + * by leading cryptographers.
> + *
> + * Battle-tested, with successful integration in OSs (Linux kernel, OpenBSD, FreeBSD, FreeRTOS),
> + * languages (Perl, Python, Ruby, etc.), libraries (OpenSSL libcrypto, Sodium, etc.)
> + * and applications (Wireguard, Redis, etc.).
> + *
> + * As a secure pseudorandom function (a.k.a. keyed hash function), SipHash can also be used as
> + * a secure message authentication code (MAC). But SipHash is not a hash in the sense of
> + * general-purpose key-less hash function such as BLAKE3 or SHA-3.
> + * SipHash should therefore always be used with a secret key in order to be secure.
> + * siphash functions.
> + *
> + */
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +#include <stdint.h>
> +
> +#include <rte_compat.h>
> +
> +/**
> + * Compute a SipHash-2-4
> + * uses a 64 bit key; does 2 compression rounds, and 4 finalization rounds.
> + *
> + * @param data
> + * Data to perform hash on.
> + * @param len
> + * How many bytes to use to calculate hash value.
> + * @param initval
> + * Value to initialise hash generator.
> + * @return
> + * 64bit calculated hash value.
> + */
> +__rte_experimental
> +uint64_t
> +rte_siphash(const void *data, uint32_t len, uint64_t init_val);
> +
> +/**
> + * Compute Siphash-1-3;
> + * uses a 32 bit key; does 1 compression round, and 3 finalization rounds.
> + *
> + * @param data
> + * Data to perform hash on.
> + * @param len
> + * How many bytes to use to calculate hash value.
> + * @param initval
> + * Value to initialise hash generator.
> + * @return
> + * 32bit calculated hash value.
> + */
> +__rte_experimental
> +uint32_t
> +rte_hsiphash(const void *data, uint32_t len, uint32_t init_val);
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* _RTE_SIPHASH_H */
> diff --git a/lib/hash/version.map b/lib/hash/version.map
> index 6b2afebf6b46..16221fc1d8c7 100644
> --- a/lib/hash/version.map
> +++ b/lib/hash/version.map
> @@ -48,3 +48,10 @@ DPDK_24 {
>
> local: *;
> };
> +
> +EXPERIMENTAL {
> + global:
> +
> + rte_siphash;
> + rte_hsiphash;
> +};
^ permalink raw reply [flat|nested] 12+ messages in thread* Re: [PATCH v2] lib/hash: add siphash
2024-02-27 21:57 ` Mattias Rönnblom
@ 2024-02-27 22:34 ` Stephen Hemminger
0 siblings, 0 replies; 12+ messages in thread
From: Stephen Hemminger @ 2024-02-27 22:34 UTC (permalink / raw)
To: Mattias Rönnblom
Cc: dev, Yipeng Wang, Sameh Gobriel, Bruce Richardson, Vladimir Medvedkin
On Tue, 27 Feb 2024 22:57:06 +0100
Mattias Rönnblom <hofors@lysator.liu.se> wrote:
> The portable and x86 version will compile to the same thing on x86.
>
> A simpler implementation would be
>
> static __rte_always_inline uint64_t
> u8to64_le(const uint8_t *p)
> {
> uint64_t w;
> memcpy(&w, p, sizeof(w));
> return rte_cpu_to_le(w);
> }
>
> ...which probably also compiles to the same code.
>
> Do you want the same hash value on big and little endian, or why the
> conversion?
I am following what other implementations do here. The reference implementation
does it off of little endian. And so does FreeBSD and Linux.
The shift version comes from the reference version.
Your right, with -O3 both get optimized away.
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH v3] lib/hash: add siphash
2024-02-27 17:39 [PATCH] lib/hash: add SipHash function Stephen Hemminger
2024-02-27 19:14 ` [PATCH v2] lib/hash: add siphash Stephen Hemminger
@ 2024-02-29 0:32 ` Stephen Hemminger
2024-05-29 15:47 ` [PATCH v4] " Stephen Hemminger
` (2 subsequent siblings)
4 siblings, 0 replies; 12+ messages in thread
From: Stephen Hemminger @ 2024-02-29 0:32 UTC (permalink / raw)
To: dev
Cc: Stephen Hemminger, Yipeng Wang, Sameh Gobriel, Bruce Richardson,
Vladimir Medvedkin
Add SipHash which is a fast and cryptographicly sound hash
created by Jean-Philippe Aumasson and Daniel J. Bernstein.
Siphash is widely used by Linux, FreeBSD, OpenBSD and other
projects because it is fast and resistant to DoS attacks.
This version is designed to be useful as alternative hash
with cuckoo hash in DPDK.
Implementation is based of the public domain and Creative
Common license reference version as well as some optimizations
from the GPL-2 or BSD-3 licensed version in Linux.
Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
---
v3 - unroll the rounds to get 3% speedup
use memcpy to avoid having x86 only code
app/test/test_hash_functions.c | 71 ++++++++++++-
lib/hash/meson.build | 2 +
lib/hash/rte_siphash.c | 176 +++++++++++++++++++++++++++++++++
lib/hash/rte_siphash.h | 86 ++++++++++++++++
lib/hash/version.map | 7 ++
5 files changed, 338 insertions(+), 4 deletions(-)
create mode 100644 lib/hash/rte_siphash.c
create mode 100644 lib/hash/rte_siphash.h
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 70820d1f1976..3bffbe4ed4ba 100644
--- a/app/test/test_hash_functions.c
+++ b/app/test/test_hash_functions.c
@@ -15,6 +15,7 @@
#include <rte_hash.h>
#include <rte_jhash.h>
#include <rte_hash_crc.h>
+#include <rte_siphash.h>
#include "test.h"
@@ -52,6 +53,42 @@ static uint32_t hash_values_crc[2][12] = {{
}
};
+static uint32_t hash_values_hsiphash[2][12] = {
+ {
+ 0x8e01e473, 0xc41e3669,
+ 0x813e4dbd, 0x7ebe2eea,
+ 0x33a5c5b7, 0xc910629b,
+ 0xba50237f, 0xbbc870c6,
+ 0x95124362, 0x850f8e0d,
+ 0x192ff266, 0xb41d8206,
+ }, {
+ 0x66200aa0, 0x769e7201,
+ 0x0e934d03, 0x96d7c892,
+ 0xb4643534, 0xcb758913,
+ 0x498b66e9, 0x116b4082,
+ 0x603030dc, 0x644b608b,
+ 0x74b29c27, 0x513f3a9c,
+ }
+};
+
+static uint64_t hash_values_siphash[2][12] = {
+ {
+ 0x8b5a0baa49fbc58d, 0x62c3506f27376c25,
+ 0xef7bdf3ee24abec8, 0xc72b1c24fc2f7938,
+ 0xc902632ed88f897f, 0xab631e00063006f5,
+ 0x7b821577565ea3a4, 0x8b19265d1c12cdc7,
+ 0x610e7ab6ada60b22, 0x3c6f1970dd62f235,
+ 0x4b8db19fd6940031, 0xa43827a530b08989,
+ }, {
+ 0x86e1bbae2893aaf1, 0x9c05614a696cda03,
+ 0x9ee31847083019c3, 0x600e860c97264e31,
+ 0xda8721038e4972bc, 0xfeedeb1b8bfe5d1e,
+ 0xb2d6388922af426f, 0x7d05b8e82e38cf30,
+ 0x439caa6ecd0b628d, 0x6d4c4ba6f3f2aed5,
+ 0x5622bb0da20658ff, 0x409d76de4adcd475,
+ }
+};
+
/*******************************************************************************
* Hash function performance test configuration section. Each performance test
* will be performed HASHTEST_ITERATIONS times.
@@ -61,9 +98,11 @@ static uint32_t hash_values_crc[2][12] = {{
*/
#define HASHTEST_ITERATIONS 1000000
#define MAX_KEYSIZE 64
-static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
-static uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
-static uint32_t hashtest_key_lens[] = {
+static const rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc, rte_hsiphash};
+static const uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
+static const uint64_t hashtest_initkeys[] = {0, UINT64_C(0xfeedc0dedeadbeef)};
+
+static const uint32_t hashtest_key_lens[] = {
1, 2, /* Unusual key sizes */
4, 8, 16, 32, 48, 64, /* standard key sizes */
9, /* IPv4 SRC + DST + protocol, unpadded */
@@ -85,6 +124,9 @@ get_hash_name(rte_hash_function f)
if (f == rte_hash_crc)
return "rte_hash_crc";
+ if (f == rte_hsiphash)
+ return "hsiphash";
+
return "UnknownHash";
}
@@ -126,6 +168,7 @@ run_hash_func_perf_tests(void)
printf(" Number of iterations for each test = %d\n",
HASHTEST_ITERATIONS);
printf("Hash Func. , Key Length (bytes), Initial value, Ticks/Op.\n");
+ fflush(stdout);
for (i = 0; i < RTE_DIM(hashtest_initvals); i++) {
for (j = 0; j < RTE_DIM(hashtest_key_lens); j++) {
@@ -147,13 +190,15 @@ verify_precalculated_hash_func_tests(void)
{
unsigned i, j;
uint8_t key[64];
- uint32_t hash;
for (i = 0; i < 64; i++)
key[i] = (uint8_t) i;
for (i = 0; i < RTE_DIM(hashtest_key_lens); i++) {
for (j = 0; j < RTE_DIM(hashtest_initvals); j++) {
+ uint32_t hash;
+ uint64_t shash;
+
hash = rte_jhash(key, hashtest_key_lens[i],
hashtest_initvals[j]);
if (hash != hash_values_jhash[j][i]) {
@@ -173,6 +218,24 @@ verify_precalculated_hash_func_tests(void)
hash_values_crc[j][i], hash);
return -1;
}
+
+ hash = rte_hsiphash(key, hashtest_key_lens[i], hashtest_initvals[j]);
+ if (hash != hash_values_hsiphash[j][i]) {
+ printf("Hsiphash for %u bytes with initial value 0x%x."
+ "Expected 0x%x, but got 0x%x\n",
+ hashtest_key_lens[i], hashtest_initvals[j],
+ hash_values_hsiphash[j][i], hash);
+ return -1;
+ }
+
+ shash = rte_siphash(key, hashtest_key_lens[i], hashtest_initkeys[j]);
+ if (shash != hash_values_siphash[j][i]) {
+ printf("siphash for %u bytes with initial %#"PRIx64"."
+ "Expected %#"PRIx64", but got %#"PRIx64"\n",
+ hashtest_key_lens[i], hashtest_initkeys[j],
+ hash_values_siphash[j][i], shash);
+ return -1;
+ }
}
}
diff --git a/lib/hash/meson.build b/lib/hash/meson.build
index 277eb9fa9366..913855124d2b 100644
--- a/lib/hash/meson.build
+++ b/lib/hash/meson.build
@@ -6,6 +6,7 @@ headers = files(
'rte_hash_crc.h',
'rte_hash.h',
'rte_jhash.h',
+ 'rte_siphash.h',
'rte_thash.h',
'rte_thash_gfni.h',
)
@@ -21,6 +22,7 @@ sources = files(
'rte_cuckoo_hash.c',
'rte_hash_crc.c',
'rte_fbk_hash.c',
+ 'rte_siphash.c',
'rte_thash.c',
'rte_thash_gfni.c',
)
diff --git a/lib/hash/rte_siphash.c b/lib/hash/rte_siphash.c
new file mode 100644
index 000000000000..85f0c54c280e
--- /dev/null
+++ b/lib/hash/rte_siphash.c
@@ -0,0 +1,176 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ *
+ * Based on code reference code licensed as CC0 and MIT.
+ * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+ * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+#include <rte_byteorder.h>
+#include <rte_common.h>
+
+#include "rte_siphash.h"
+
+static __rte_always_inline uint64_t
+rol64(uint64_t x, unsigned int b)
+{
+ return (x << b) | (x >> (64 - b));
+}
+
+static __rte_always_inline uint64_t u8to64_le(const uint8_t *p)
+{
+ uint64_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_64(w);
+}
+
+static __rte_always_inline uint32_t u8to32_le(const uint8_t *p)
+{
+ uint32_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_32(w);
+}
+
+static __rte_always_inline uint16_t u8to16_le(const uint8_t *p)
+{
+ uint16_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_16(w);
+}
+
+
+/*
+ * Use a 64bit version of SipHash for both full and
+ * half versions, The difference is the number of rounds.
+ */
+#define PREAMBLE(len) \
+ uint64_t v0 = UINT64_C(0x736f6d6570736575); \
+ uint64_t v1 = UINT64_C(0x646f72616e646f6d); \
+ uint64_t v2 = UINT64_C(0x6c7967656e657261); \
+ uint64_t v3 = UINT64_C(0x7465646279746573); \
+ uint64_t b = (uint64_t)len << 56; \
+ v2 ^= init_val; \
+ v0 ^= init_val
+
+#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)
+
+uint64_t
+rte_siphash(const void *key, uint32_t len, uint64_t init_val)
+{
+ const uint8_t *data = key;
+ const uint32_t left = len & 7;
+ const uint8_t *end = data + (len - left);
+
+ PREAMBLE(len);
+
+ for (; data != end; data += 8) {
+ uint64_t m = u8to64_le(data);
+ v3 ^= m;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= m;
+ }
+
+ switch (left) {
+ case 7:
+ b |= ((uint64_t)end[6]) << 48; /* fallthrough */
+ case 6:
+ b |= ((uint64_t)end[5]) << 40; /* fallthrough */
+ case 5:
+ b |= ((uint64_t)end[4]) << 32; /* fallthrough */
+ case 4:
+ b |= u8to32_le(data);
+ break;
+ case 3:
+ b |= ((uint64_t)end[2]) << 16; /* fallthrough */
+ case 2:
+ b |= u8to16_le(data);
+ break;
+ case 1:
+ b |= data[0];
+ }
+
+ v3 ^= b;
+ SIPROUND;
+ SIPROUND;
+
+ v0 ^= b;
+ v2 ^= 0xff;
+
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
+
+uint32_t
+rte_hsiphash(const void *key, uint32_t len, uint32_t init_val)
+{
+ const uint8_t *data = key;
+ const uint32_t left = len & 7;
+ const uint8_t *end = data + (len - left);
+
+ PREAMBLE(len);
+
+ for (; data != end; data += 8) {
+ uint64_t m = u8to64_le(data);
+ v3 ^= m;
+ SIPROUND;
+ v0 ^= m;
+ }
+
+
+
+ switch (left) {
+ case 7:
+ b |= ((uint64_t)end[6]) << 48; /* fallthrough */
+ case 6:
+ b |= ((uint64_t)end[5]) << 40; /* fallthrough */
+ case 5:
+ b |= ((uint64_t)end[4]) << 32; /* fallthrough */
+ case 4:
+ b |= u8to32_le(data);
+ break;
+ case 3:
+ b |= ((uint64_t)end[2]) << 16; /* fallthrough */
+ case 2:
+ b |= u8to16_le(data);
+ break;
+ case 1:
+ b |= data[0];
+ }
+
+ v3 ^= b;
+ SIPROUND;
+
+ v0 ^= b;
+ v2 ^= 0xff;
+
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
diff --git a/lib/hash/rte_siphash.h b/lib/hash/rte_siphash.h
new file mode 100644
index 000000000000..d9fbbe2e9275
--- /dev/null
+++ b/lib/hash/rte_siphash.h
@@ -0,0 +1,86 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ *
+ * Based on code reference code licensed as CC0 and MIT.
+ * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+ * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
+ */
+
+#ifndef _RTE_SIPHASH_H
+#define _RTE_SIPHASH_H
+
+/**
+ * @file
+ *
+ * SipHash is a family of pseudorandom functions (PRFs) optimized for speed on short messages.
+ *
+ * SipHash was designed in 2012 by Jean-Philippe Aumasson and Daniel J. Bernstein as a defense
+ * against hash-flooding DoS attacks.
+ *
+ * SipHash is simpler and faster on short messages than previous cryptographic algorithms,
+ * such as MACs based on universal hashing.
+ * Competitive in performance with insecure non-cryptographic algorithms.
+ *
+ * Cryptographically secure, with no sign of weakness despite multiple cryptanalysis projects
+ * by leading cryptographers.
+ *
+ * Battle-tested, with successful integration in OSs (Linux kernel, OpenBSD, FreeBSD, FreeRTOS),
+ * languages (Perl, Python, Ruby, etc.), libraries (OpenSSL libcrypto, Sodium, etc.)
+ * and applications (Wireguard, Redis, etc.).
+ *
+ * As a secure pseudorandom function (a.k.a. keyed hash function), SipHash can also be used as
+ * a secure message authentication code (MAC). But SipHash is not a hash in the sense of
+ * general-purpose key-less hash function such as BLAKE3 or SHA-3.
+ * SipHash should therefore always be used with a secret key in order to be secure.
+ * siphash functions.
+ *
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdint.h>
+
+#include <rte_compat.h>
+
+/**
+ * Compute a SipHash-2-4.
+ * This version is the original version described in the reference version.
+ * It uses a 64 bit key; does 2 compression rounds, and 4 finalization rounds.
+ *
+ * @param data
+ * Data to perform hash on.
+ * @param len
+ * How many bytes to use to calculate hash value.
+ * @param init_val
+ * Value to initialize hash generator.
+ * @return
+ * 64bit calculated hash value.
+ */
+__rte_experimental
+uint64_t
+rte_siphash(const void *data, uint32_t len, uint64_t init_val);
+
+/**
+ * Compute Siphash-1-3.
+ * This is the faster version which is used by Linux and other OS's.
+ * It uses a 32 bit key; does 1 compression round, and 3 finalization rounds.
+ *
+ * @param data
+ * Data to perform hash on.
+ * @param len
+ * How many bytes to use to calculate hash value.
+ * @param init_val
+ * Value to initialize hash generator.
+ * @return
+ * 32bit calculated hash value.
+ */
+__rte_experimental
+uint32_t
+rte_hsiphash(const void *data, uint32_t len, uint32_t init_val);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_SIPHASH_H */
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 6b2afebf6b46..16221fc1d8c7 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -48,3 +48,10 @@ DPDK_24 {
local: *;
};
+
+EXPERIMENTAL {
+ global:
+
+ rte_siphash;
+ rte_hsiphash;
+};
--
2.43.0
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH v4] lib/hash: add siphash
2024-02-27 17:39 [PATCH] lib/hash: add SipHash function Stephen Hemminger
2024-02-27 19:14 ` [PATCH v2] lib/hash: add siphash Stephen Hemminger
2024-02-29 0:32 ` [PATCH v3] " Stephen Hemminger
@ 2024-05-29 15:47 ` Stephen Hemminger
2024-06-17 14:58 ` [PATCH v5] " Stephen Hemminger
2024-08-01 15:31 ` [PATCH v6] " Stephen Hemminger
4 siblings, 0 replies; 12+ messages in thread
From: Stephen Hemminger @ 2024-05-29 15:47 UTC (permalink / raw)
To: dev
Cc: Stephen Hemminger, Yipeng Wang, Sameh Gobriel, Bruce Richardson,
Vladimir Medvedkin
The existing hash functions in DPDK are not cryptographically
secure and can be subject to carefully crafted packets causing
DoS attack.
Add SipHash which is a fast and cryptographicly sound hash
created by Jean-Philippe Aumasson and Daniel J. Bernstein.
Siphash is widely used by Linux, FreeBSD, OpenBSD and other
projects because it is fast and resistant to DoS attacks.
This version is designed to be useful as alternative hash
with cuckoo hash in DPDK.
Implementation is based of the public domain and Creative
Common license reference version as well as some optimizations
from the GPL-2 or BSD-3 licensed version in Linux.
Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
---
v4 - rebase
- allow 128 bit init value for siphash
app/test/test_hash_functions.c | 75 +++++++++++++-
lib/hash/meson.build | 2 +
lib/hash/rte_siphash.c | 176 +++++++++++++++++++++++++++++++++
lib/hash/rte_siphash.h | 87 ++++++++++++++++
lib/hash/version.map | 8 ++
5 files changed, 344 insertions(+), 4 deletions(-)
create mode 100644 lib/hash/rte_siphash.c
create mode 100644 lib/hash/rte_siphash.h
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 70820d1f19..be992348f7 100644
--- a/app/test/test_hash_functions.c
+++ b/app/test/test_hash_functions.c
@@ -15,6 +15,7 @@
#include <rte_hash.h>
#include <rte_jhash.h>
#include <rte_hash_crc.h>
+#include <rte_siphash.h>
#include "test.h"
@@ -52,6 +53,42 @@ static uint32_t hash_values_crc[2][12] = {{
}
};
+static uint32_t hash_values_hsiphash[2][12] = {
+ {
+ 0x8e01e473, 0xc41e3669,
+ 0x813e4dbd, 0x7ebe2eea,
+ 0x33a5c5b7, 0xc910629b,
+ 0xba50237f, 0xbbc870c6,
+ 0x95124362, 0x850f8e0d,
+ 0x192ff266, 0xb41d8206,
+ }, {
+ 0x66200aa0, 0x769e7201,
+ 0x0e934d03, 0x96d7c892,
+ 0xb4643534, 0xcb758913,
+ 0x498b66e9, 0x116b4082,
+ 0x603030dc, 0x644b608b,
+ 0x74b29c27, 0x513f3a9c,
+ }
+};
+
+static uint64_t hash_values_siphash[2][12] = {
+ {
+ 0x8b5a0baa49fbc58d, 0x62c3506f27376c25,
+ 0xef7bdf3ee24abec8, 0xc72b1c24fc2f7938,
+ 0xc902632ed88f897f, 0xab631e00063006f5,
+ 0x7b821577565ea3a4, 0x8b19265d1c12cdc7,
+ 0x610e7ab6ada60b22, 0x3c6f1970dd62f235,
+ 0x4b8db19fd6940031, 0xa43827a530b08989,
+ }, {
+ 0x86e1bbae2893aaf1, 0x9c05614a696cda03,
+ 0x9ee31847083019c3, 0x600e860c97264e31,
+ 0xda8721038e4972bc, 0xfeedeb1b8bfe5d1e,
+ 0xb2d6388922af426f, 0x7d05b8e82e38cf30,
+ 0x439caa6ecd0b628d, 0x6d4c4ba6f3f2aed5,
+ 0x5622bb0da20658ff, 0x409d76de4adcd475,
+ }
+};
+
/*******************************************************************************
* Hash function performance test configuration section. Each performance test
* will be performed HASHTEST_ITERATIONS times.
@@ -61,9 +98,14 @@ static uint32_t hash_values_crc[2][12] = {{
*/
#define HASHTEST_ITERATIONS 1000000
#define MAX_KEYSIZE 64
-static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
-static uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
-static uint32_t hashtest_key_lens[] = {
+static const rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc, rte_hsiphash};
+static const uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
+static const uint64_t hashtest_initkeys[][2] = {
+ { 0, 0, },
+ { UINT64_C(0xfeedc0dedeadbeef), 0 },
+};
+
+static const uint32_t hashtest_key_lens[] = {
1, 2, /* Unusual key sizes */
4, 8, 16, 32, 48, 64, /* standard key sizes */
9, /* IPv4 SRC + DST + protocol, unpadded */
@@ -85,6 +127,9 @@ get_hash_name(rte_hash_function f)
if (f == rte_hash_crc)
return "rte_hash_crc";
+ if (f == rte_hsiphash)
+ return "hsiphash";
+
return "UnknownHash";
}
@@ -126,6 +171,7 @@ run_hash_func_perf_tests(void)
printf(" Number of iterations for each test = %d\n",
HASHTEST_ITERATIONS);
printf("Hash Func. , Key Length (bytes), Initial value, Ticks/Op.\n");
+ fflush(stdout);
for (i = 0; i < RTE_DIM(hashtest_initvals); i++) {
for (j = 0; j < RTE_DIM(hashtest_key_lens); j++) {
@@ -147,13 +193,15 @@ verify_precalculated_hash_func_tests(void)
{
unsigned i, j;
uint8_t key[64];
- uint32_t hash;
for (i = 0; i < 64; i++)
key[i] = (uint8_t) i;
for (i = 0; i < RTE_DIM(hashtest_key_lens); i++) {
for (j = 0; j < RTE_DIM(hashtest_initvals); j++) {
+ uint32_t hash;
+ uint64_t shash;
+
hash = rte_jhash(key, hashtest_key_lens[i],
hashtest_initvals[j]);
if (hash != hash_values_jhash[j][i]) {
@@ -173,6 +221,25 @@ verify_precalculated_hash_func_tests(void)
hash_values_crc[j][i], hash);
return -1;
}
+
+ hash = rte_hsiphash(key, hashtest_key_lens[i], hashtest_initvals[j]);
+ if (hash != hash_values_hsiphash[j][i]) {
+ printf("Hsiphash for %u bytes with initial value 0x%x."
+ "Expected 0x%x, but got 0x%x\n",
+ hashtest_key_lens[i], hashtest_initvals[j],
+ hash_values_hsiphash[j][i], hash);
+ return -1;
+ }
+
+ shash = rte_siphash(key, hashtest_key_lens[i], hashtest_initkeys[j]);
+ if (shash != hash_values_siphash[j][i]) {
+ printf("siphash for %u bytes with initial { %#" PRIx64 ", %#" PRIx64 "}."
+ "Expected %#"PRIx64", but got %#"PRIx64"\n",
+ hashtest_key_lens[i],
+ hashtest_initkeys[j][0], hashtest_initkeys[j][1],
+ hash_values_siphash[j][i], shash);
+ return -1;
+ }
}
}
diff --git a/lib/hash/meson.build b/lib/hash/meson.build
index 277eb9fa93..913855124d 100644
--- a/lib/hash/meson.build
+++ b/lib/hash/meson.build
@@ -6,6 +6,7 @@ headers = files(
'rte_hash_crc.h',
'rte_hash.h',
'rte_jhash.h',
+ 'rte_siphash.h',
'rte_thash.h',
'rte_thash_gfni.h',
)
@@ -21,6 +22,7 @@ sources = files(
'rte_cuckoo_hash.c',
'rte_hash_crc.c',
'rte_fbk_hash.c',
+ 'rte_siphash.c',
'rte_thash.c',
'rte_thash_gfni.c',
)
diff --git a/lib/hash/rte_siphash.c b/lib/hash/rte_siphash.c
new file mode 100644
index 0000000000..1b609fddeb
--- /dev/null
+++ b/lib/hash/rte_siphash.c
@@ -0,0 +1,176 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ *
+ * Based on code reference code licensed as CC0 and MIT.
+ * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+ * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+#include <rte_byteorder.h>
+#include <rte_common.h>
+
+#include "rte_siphash.h"
+
+static __rte_always_inline uint64_t
+rol64(uint64_t x, unsigned int b)
+{
+ return (x << b) | (x >> (64 - b));
+}
+
+static __rte_always_inline uint64_t u8to64_le(const uint8_t *p)
+{
+ uint64_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_64(w);
+}
+
+static __rte_always_inline uint32_t u8to32_le(const uint8_t *p)
+{
+ uint32_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_32(w);
+}
+
+static __rte_always_inline uint16_t u8to16_le(const uint8_t *p)
+{
+ uint16_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_16(w);
+}
+
+
+/*
+ * Use a 64bit version of SipHash for both full and
+ * half versions, The difference is the number of rounds.
+ */
+#define PREAMBLE(len, key0, key1) \
+ uint64_t v0 = UINT64_C(0x736f6d6570736575); \
+ uint64_t v1 = UINT64_C(0x646f72616e646f6d); \
+ uint64_t v2 = UINT64_C(0x6c7967656e657261); \
+ uint64_t v3 = UINT64_C(0x7465646279746573); \
+ uint64_t b = (uint64_t)len << 56; \
+ v3 ^= key1; \
+ v2 ^= key0; \
+ v1 ^= key1; \
+ v0 ^= key0
+
+#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)
+
+uint64_t
+rte_siphash(const void *key, uint32_t len, const uint64_t init[2])
+{
+ const uint8_t *data = key;
+ const uint32_t left = len & 7;
+ const uint8_t *end = data + (len - left);
+
+ PREAMBLE(len, init[0], init[1]);
+
+ for (; data != end; data += 8) {
+ uint64_t m = u8to64_le(data);
+ v3 ^= m;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= m;
+ }
+
+ switch (left) {
+ case 7:
+ b |= ((uint64_t)end[6]) << 48; /* fallthrough */
+ case 6:
+ b |= ((uint64_t)end[5]) << 40; /* fallthrough */
+ case 5:
+ b |= ((uint64_t)end[4]) << 32; /* fallthrough */
+ case 4:
+ b |= u8to32_le(data);
+ break;
+ case 3:
+ b |= ((uint64_t)end[2]) << 16; /* fallthrough */
+ case 2:
+ b |= u8to16_le(data);
+ break;
+ case 1:
+ b |= data[0];
+ }
+
+ v3 ^= b;
+ SIPROUND;
+ SIPROUND;
+
+ v0 ^= b;
+ v2 ^= 0xff;
+
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
+
+uint32_t
+rte_hsiphash(const void *key, uint32_t len, uint32_t init_val)
+{
+ const uint8_t *data = key;
+ const uint32_t left = len & 7;
+ const uint8_t *end = data + (len - left);
+
+ PREAMBLE(len, init_val, 0);
+
+ for (; data != end; data += 8) {
+ uint64_t m = u8to64_le(data);
+ v3 ^= m;
+ SIPROUND;
+ v0 ^= m;
+ }
+
+ switch (left) {
+ case 7:
+ b |= ((uint64_t)end[6]) << 48; /* fallthrough */
+ case 6:
+ b |= ((uint64_t)end[5]) << 40; /* fallthrough */
+ case 5:
+ b |= ((uint64_t)end[4]) << 32; /* fallthrough */
+ case 4:
+ b |= u8to32_le(data);
+ break;
+ case 3:
+ b |= ((uint64_t)end[2]) << 16; /* fallthrough */
+ case 2:
+ b |= u8to16_le(data);
+ break;
+ case 1:
+ b |= data[0];
+ }
+
+ v3 ^= b;
+ SIPROUND;
+
+ v0 ^= b;
+ v2 ^= 0xff;
+
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
diff --git a/lib/hash/rte_siphash.h b/lib/hash/rte_siphash.h
new file mode 100644
index 0000000000..964e374f44
--- /dev/null
+++ b/lib/hash/rte_siphash.h
@@ -0,0 +1,87 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ *
+ * Based on code reference code licensed as CC0 and MIT.
+ * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+ * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
+ */
+
+#ifndef _RTE_SIPHASH_H
+#define _RTE_SIPHASH_H
+
+/**
+ * @file
+ *
+ * SipHash is a family of pseudorandom functions (PRFs) optimized for speed on short messages.
+ *
+ * SipHash was designed in 2012 by Jean-Philippe Aumasson and Daniel J. Bernstein as a defense
+ * against hash-flooding DoS attacks.
+ *
+ * SipHash is simpler and faster on short messages than previous cryptographic algorithms,
+ * such as MACs based on universal hashing.
+ * Competitive in performance with insecure non-cryptographic algorithms.
+ *
+ * Cryptographically secure, with no sign of weakness despite multiple cryptanalysis projects
+ * by leading cryptographers.
+ *
+ * Battle-tested, with successful integration in OSs (Linux kernel, OpenBSD, FreeBSD, FreeRTOS),
+ * languages (Perl, Python, Ruby, etc.), libraries (OpenSSL libcrypto, Sodium, etc.)
+ * and applications (Wireguard, Redis, etc.).
+ *
+ * As a secure pseudorandom function (a.k.a. keyed hash function), SipHash can also be used as
+ * a secure message authentication code (MAC). But SipHash is not a hash in the sense of
+ * general-purpose key-less hash function such as BLAKE3 or SHA-3.
+ * SipHash should therefore always be used with a secret key in order to be secure.
+ * siphash functions.
+ *
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdint.h>
+
+#include <rte_compat.h>
+
+/**
+ * Compute a SipHash-2-4.
+ * This version is the original version described in the reference version.
+ * It uses a 64 bit key; does 2 compression rounds, and 4 finalization rounds.
+ *
+ * @param data
+ * Data to perform hash on.
+ * @param len
+ * How many bytes to use to calculate hash value.
+ * @param init_vals
+ * 128-bit value to initialize hash generator.
+ * @return
+ * 64bit calculated hash value.
+ */
+__rte_experimental
+uint64_t
+rte_siphash(const void *data, uint32_t len, const uint64_t init_vals[2]);
+
+/**
+ * Compute Siphash-1-3.
+ * This is the faster version which is used by Linux and other OS's.
+ * It uses a 32 bit key; does 1 compression round, and 3 finalization rounds.
+ * The function can be used with in hash_parameters with rte_hash_create().
+ *
+ * @param data
+ * Data to perform hash on.
+ * @param len
+ * How many bytes to use to calculate hash value.
+ * @param init_val
+ * Value to initialize hash generator.
+ * @return
+ * 32bit calculated hash value.
+ */
+__rte_experimental
+uint32_t
+rte_hsiphash(const void *data, uint32_t len, uint32_t init_val);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_SIPHASH_H */
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 6f4bcdb71b..6c3b0ad52b 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -47,6 +47,14 @@ DPDK_24 {
local: *;
};
+EXPERIMENTAL {
+ global:
+
+ # added in 24.07
+ rte_siphash;
+ rte_hsiphash;
+};
+
INTERNAL {
global:
--
2.43.0
^ permalink raw reply [flat|nested] 12+ messages in thread* [PATCH v5] lib/hash: add siphash
2024-02-27 17:39 [PATCH] lib/hash: add SipHash function Stephen Hemminger
` (2 preceding siblings ...)
2024-05-29 15:47 ` [PATCH v4] " Stephen Hemminger
@ 2024-06-17 14:58 ` Stephen Hemminger
2024-06-19 14:24 ` Thomas Monjalon
2024-08-01 15:31 ` [PATCH v6] " Stephen Hemminger
4 siblings, 1 reply; 12+ messages in thread
From: Stephen Hemminger @ 2024-06-17 14:58 UTC (permalink / raw)
To: dev; +Cc: Stephen Hemminger
The existing hash functions in DPDK are not cryptographically
secure and can be subject to carefully crafted packets causing
DoS attack.
Add SipHash which is a fast and cryptographicly sound hash
created by Jean-Philippe Aumasson and Daniel J. Bernstein.
Siphash is widely used by Linux, FreeBSD, OpenBSD and other
projects because it is fast and resistant to DoS attacks.
This version is designed to be useful as alternative hash
with cuckoo hash in DPDK.
Implementation is based of the public domain and Creative
Common license reference version as well as some optimizations
from the GPL-2 or BSD-3 licensed version in Linux.
Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
---
v5 - fix long line
app/test/test_hash_functions.c | 75 +++++++++++++-
lib/hash/meson.build | 2 +
lib/hash/rte_siphash.c | 176 +++++++++++++++++++++++++++++++++
lib/hash/rte_siphash.h | 87 ++++++++++++++++
lib/hash/version.map | 8 ++
5 files changed, 344 insertions(+), 4 deletions(-)
create mode 100644 lib/hash/rte_siphash.c
create mode 100644 lib/hash/rte_siphash.h
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 70820d1f19..010839eeb7 100644
--- a/app/test/test_hash_functions.c
+++ b/app/test/test_hash_functions.c
@@ -15,6 +15,7 @@
#include <rte_hash.h>
#include <rte_jhash.h>
#include <rte_hash_crc.h>
+#include <rte_siphash.h>
#include "test.h"
@@ -52,6 +53,42 @@ static uint32_t hash_values_crc[2][12] = {{
}
};
+static uint32_t hash_values_hsiphash[2][12] = {
+ {
+ 0x8e01e473, 0xc41e3669,
+ 0x813e4dbd, 0x7ebe2eea,
+ 0x33a5c5b7, 0xc910629b,
+ 0xba50237f, 0xbbc870c6,
+ 0x95124362, 0x850f8e0d,
+ 0x192ff266, 0xb41d8206,
+ }, {
+ 0x66200aa0, 0x769e7201,
+ 0x0e934d03, 0x96d7c892,
+ 0xb4643534, 0xcb758913,
+ 0x498b66e9, 0x116b4082,
+ 0x603030dc, 0x644b608b,
+ 0x74b29c27, 0x513f3a9c,
+ }
+};
+
+static uint64_t hash_values_siphash[2][12] = {
+ {
+ 0x8b5a0baa49fbc58d, 0x62c3506f27376c25,
+ 0xef7bdf3ee24abec8, 0xc72b1c24fc2f7938,
+ 0xc902632ed88f897f, 0xab631e00063006f5,
+ 0x7b821577565ea3a4, 0x8b19265d1c12cdc7,
+ 0x610e7ab6ada60b22, 0x3c6f1970dd62f235,
+ 0x4b8db19fd6940031, 0xa43827a530b08989,
+ }, {
+ 0x86e1bbae2893aaf1, 0x9c05614a696cda03,
+ 0x9ee31847083019c3, 0x600e860c97264e31,
+ 0xda8721038e4972bc, 0xfeedeb1b8bfe5d1e,
+ 0xb2d6388922af426f, 0x7d05b8e82e38cf30,
+ 0x439caa6ecd0b628d, 0x6d4c4ba6f3f2aed5,
+ 0x5622bb0da20658ff, 0x409d76de4adcd475,
+ }
+};
+
/*******************************************************************************
* Hash function performance test configuration section. Each performance test
* will be performed HASHTEST_ITERATIONS times.
@@ -61,9 +98,14 @@ static uint32_t hash_values_crc[2][12] = {{
*/
#define HASHTEST_ITERATIONS 1000000
#define MAX_KEYSIZE 64
-static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
-static uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
-static uint32_t hashtest_key_lens[] = {
+static const rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc, rte_hsiphash};
+static const uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
+static const uint64_t hashtest_initkeys[][2] = {
+ { 0, 0, },
+ { UINT64_C(0xfeedc0dedeadbeef), 0 },
+};
+
+static const uint32_t hashtest_key_lens[] = {
1, 2, /* Unusual key sizes */
4, 8, 16, 32, 48, 64, /* standard key sizes */
9, /* IPv4 SRC + DST + protocol, unpadded */
@@ -85,6 +127,9 @@ get_hash_name(rte_hash_function f)
if (f == rte_hash_crc)
return "rte_hash_crc";
+ if (f == rte_hsiphash)
+ return "hsiphash";
+
return "UnknownHash";
}
@@ -126,6 +171,7 @@ run_hash_func_perf_tests(void)
printf(" Number of iterations for each test = %d\n",
HASHTEST_ITERATIONS);
printf("Hash Func. , Key Length (bytes), Initial value, Ticks/Op.\n");
+ fflush(stdout);
for (i = 0; i < RTE_DIM(hashtest_initvals); i++) {
for (j = 0; j < RTE_DIM(hashtest_key_lens); j++) {
@@ -147,13 +193,15 @@ verify_precalculated_hash_func_tests(void)
{
unsigned i, j;
uint8_t key[64];
- uint32_t hash;
for (i = 0; i < 64; i++)
key[i] = (uint8_t) i;
for (i = 0; i < RTE_DIM(hashtest_key_lens); i++) {
for (j = 0; j < RTE_DIM(hashtest_initvals); j++) {
+ uint32_t hash;
+ uint64_t shash;
+
hash = rte_jhash(key, hashtest_key_lens[i],
hashtest_initvals[j]);
if (hash != hash_values_jhash[j][i]) {
@@ -173,6 +221,25 @@ verify_precalculated_hash_func_tests(void)
hash_values_crc[j][i], hash);
return -1;
}
+
+ hash = rte_hsiphash(key, hashtest_key_lens[i], hashtest_initvals[j]);
+ if (hash != hash_values_hsiphash[j][i]) {
+ printf("Hsiphash for %u bytes with initial value 0x%x."
+ "Expected 0x%x, but got 0x%x\n",
+ hashtest_key_lens[i], hashtest_initvals[j],
+ hash_values_hsiphash[j][i], hash);
+ return -1;
+ }
+
+ shash = rte_siphash(key, hashtest_key_lens[i], hashtest_initkeys[j]);
+ if (shash != hash_values_siphash[j][i]) {
+ printf("siphash for %u bytes initial %#"PRIx64", %#"PRIx64"."
+ "Expected %#"PRIx64", but got %#"PRIx64"\n",
+ hashtest_key_lens[i],
+ hashtest_initkeys[j][0], hashtest_initkeys[j][1],
+ hash_values_siphash[j][i], shash);
+ return -1;
+ }
}
}
diff --git a/lib/hash/meson.build b/lib/hash/meson.build
index 277eb9fa93..913855124d 100644
--- a/lib/hash/meson.build
+++ b/lib/hash/meson.build
@@ -6,6 +6,7 @@ headers = files(
'rte_hash_crc.h',
'rte_hash.h',
'rte_jhash.h',
+ 'rte_siphash.h',
'rte_thash.h',
'rte_thash_gfni.h',
)
@@ -21,6 +22,7 @@ sources = files(
'rte_cuckoo_hash.c',
'rte_hash_crc.c',
'rte_fbk_hash.c',
+ 'rte_siphash.c',
'rte_thash.c',
'rte_thash_gfni.c',
)
diff --git a/lib/hash/rte_siphash.c b/lib/hash/rte_siphash.c
new file mode 100644
index 0000000000..1b609fddeb
--- /dev/null
+++ b/lib/hash/rte_siphash.c
@@ -0,0 +1,176 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ *
+ * Based on code reference code licensed as CC0 and MIT.
+ * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+ * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+#include <rte_byteorder.h>
+#include <rte_common.h>
+
+#include "rte_siphash.h"
+
+static __rte_always_inline uint64_t
+rol64(uint64_t x, unsigned int b)
+{
+ return (x << b) | (x >> (64 - b));
+}
+
+static __rte_always_inline uint64_t u8to64_le(const uint8_t *p)
+{
+ uint64_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_64(w);
+}
+
+static __rte_always_inline uint32_t u8to32_le(const uint8_t *p)
+{
+ uint32_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_32(w);
+}
+
+static __rte_always_inline uint16_t u8to16_le(const uint8_t *p)
+{
+ uint16_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_16(w);
+}
+
+
+/*
+ * Use a 64bit version of SipHash for both full and
+ * half versions, The difference is the number of rounds.
+ */
+#define PREAMBLE(len, key0, key1) \
+ uint64_t v0 = UINT64_C(0x736f6d6570736575); \
+ uint64_t v1 = UINT64_C(0x646f72616e646f6d); \
+ uint64_t v2 = UINT64_C(0x6c7967656e657261); \
+ uint64_t v3 = UINT64_C(0x7465646279746573); \
+ uint64_t b = (uint64_t)len << 56; \
+ v3 ^= key1; \
+ v2 ^= key0; \
+ v1 ^= key1; \
+ v0 ^= key0
+
+#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)
+
+uint64_t
+rte_siphash(const void *key, uint32_t len, const uint64_t init[2])
+{
+ const uint8_t *data = key;
+ const uint32_t left = len & 7;
+ const uint8_t *end = data + (len - left);
+
+ PREAMBLE(len, init[0], init[1]);
+
+ for (; data != end; data += 8) {
+ uint64_t m = u8to64_le(data);
+ v3 ^= m;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= m;
+ }
+
+ switch (left) {
+ case 7:
+ b |= ((uint64_t)end[6]) << 48; /* fallthrough */
+ case 6:
+ b |= ((uint64_t)end[5]) << 40; /* fallthrough */
+ case 5:
+ b |= ((uint64_t)end[4]) << 32; /* fallthrough */
+ case 4:
+ b |= u8to32_le(data);
+ break;
+ case 3:
+ b |= ((uint64_t)end[2]) << 16; /* fallthrough */
+ case 2:
+ b |= u8to16_le(data);
+ break;
+ case 1:
+ b |= data[0];
+ }
+
+ v3 ^= b;
+ SIPROUND;
+ SIPROUND;
+
+ v0 ^= b;
+ v2 ^= 0xff;
+
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
+
+uint32_t
+rte_hsiphash(const void *key, uint32_t len, uint32_t init_val)
+{
+ const uint8_t *data = key;
+ const uint32_t left = len & 7;
+ const uint8_t *end = data + (len - left);
+
+ PREAMBLE(len, init_val, 0);
+
+ for (; data != end; data += 8) {
+ uint64_t m = u8to64_le(data);
+ v3 ^= m;
+ SIPROUND;
+ v0 ^= m;
+ }
+
+ switch (left) {
+ case 7:
+ b |= ((uint64_t)end[6]) << 48; /* fallthrough */
+ case 6:
+ b |= ((uint64_t)end[5]) << 40; /* fallthrough */
+ case 5:
+ b |= ((uint64_t)end[4]) << 32; /* fallthrough */
+ case 4:
+ b |= u8to32_le(data);
+ break;
+ case 3:
+ b |= ((uint64_t)end[2]) << 16; /* fallthrough */
+ case 2:
+ b |= u8to16_le(data);
+ break;
+ case 1:
+ b |= data[0];
+ }
+
+ v3 ^= b;
+ SIPROUND;
+
+ v0 ^= b;
+ v2 ^= 0xff;
+
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
diff --git a/lib/hash/rte_siphash.h b/lib/hash/rte_siphash.h
new file mode 100644
index 0000000000..964e374f44
--- /dev/null
+++ b/lib/hash/rte_siphash.h
@@ -0,0 +1,87 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ *
+ * Based on code reference code licensed as CC0 and MIT.
+ * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+ * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
+ */
+
+#ifndef _RTE_SIPHASH_H
+#define _RTE_SIPHASH_H
+
+/**
+ * @file
+ *
+ * SipHash is a family of pseudorandom functions (PRFs) optimized for speed on short messages.
+ *
+ * SipHash was designed in 2012 by Jean-Philippe Aumasson and Daniel J. Bernstein as a defense
+ * against hash-flooding DoS attacks.
+ *
+ * SipHash is simpler and faster on short messages than previous cryptographic algorithms,
+ * such as MACs based on universal hashing.
+ * Competitive in performance with insecure non-cryptographic algorithms.
+ *
+ * Cryptographically secure, with no sign of weakness despite multiple cryptanalysis projects
+ * by leading cryptographers.
+ *
+ * Battle-tested, with successful integration in OSs (Linux kernel, OpenBSD, FreeBSD, FreeRTOS),
+ * languages (Perl, Python, Ruby, etc.), libraries (OpenSSL libcrypto, Sodium, etc.)
+ * and applications (Wireguard, Redis, etc.).
+ *
+ * As a secure pseudorandom function (a.k.a. keyed hash function), SipHash can also be used as
+ * a secure message authentication code (MAC). But SipHash is not a hash in the sense of
+ * general-purpose key-less hash function such as BLAKE3 or SHA-3.
+ * SipHash should therefore always be used with a secret key in order to be secure.
+ * siphash functions.
+ *
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdint.h>
+
+#include <rte_compat.h>
+
+/**
+ * Compute a SipHash-2-4.
+ * This version is the original version described in the reference version.
+ * It uses a 64 bit key; does 2 compression rounds, and 4 finalization rounds.
+ *
+ * @param data
+ * Data to perform hash on.
+ * @param len
+ * How many bytes to use to calculate hash value.
+ * @param init_vals
+ * 128-bit value to initialize hash generator.
+ * @return
+ * 64bit calculated hash value.
+ */
+__rte_experimental
+uint64_t
+rte_siphash(const void *data, uint32_t len, const uint64_t init_vals[2]);
+
+/**
+ * Compute Siphash-1-3.
+ * This is the faster version which is used by Linux and other OS's.
+ * It uses a 32 bit key; does 1 compression round, and 3 finalization rounds.
+ * The function can be used with in hash_parameters with rte_hash_create().
+ *
+ * @param data
+ * Data to perform hash on.
+ * @param len
+ * How many bytes to use to calculate hash value.
+ * @param init_val
+ * Value to initialize hash generator.
+ * @return
+ * 32bit calculated hash value.
+ */
+__rte_experimental
+uint32_t
+rte_hsiphash(const void *data, uint32_t len, uint32_t init_val);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_SIPHASH_H */
diff --git a/lib/hash/version.map b/lib/hash/version.map
index 6f4bcdb71b..6c3b0ad52b 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -47,6 +47,14 @@ DPDK_24 {
local: *;
};
+EXPERIMENTAL {
+ global:
+
+ # added in 24.07
+ rte_siphash;
+ rte_hsiphash;
+};
+
INTERNAL {
global:
--
2.43.0
^ permalink raw reply [flat|nested] 12+ messages in thread* Re: [PATCH v5] lib/hash: add siphash
2024-06-17 14:58 ` [PATCH v5] " Stephen Hemminger
@ 2024-06-19 14:24 ` Thomas Monjalon
0 siblings, 0 replies; 12+ messages in thread
From: Thomas Monjalon @ 2024-06-19 14:24 UTC (permalink / raw)
To: Stephen Hemminger
Cc: dev, Yipeng Wang, Sameh Gobriel, Bruce Richardson, Vladimir Medvedkin
Hash lib maintainers are not Cc'ed, adding them for review.
17/06/2024 16:58, Stephen Hemminger:
> The existing hash functions in DPDK are not cryptographically
> secure and can be subject to carefully crafted packets causing
> DoS attack.
>
> Add SipHash which is a fast and cryptographicly sound hash
> created by Jean-Philippe Aumasson and Daniel J. Bernstein.
> Siphash is widely used by Linux, FreeBSD, OpenBSD and other
> projects because it is fast and resistant to DoS attacks.
> This version is designed to be useful as alternative hash
> with cuckoo hash in DPDK.
>
> Implementation is based of the public domain and Creative
> Common license reference version as well as some optimizations
> from the GPL-2 or BSD-3 licensed version in Linux.
>
> Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH v6] lib/hash: add siphash
2024-02-27 17:39 [PATCH] lib/hash: add SipHash function Stephen Hemminger
` (3 preceding siblings ...)
2024-06-17 14:58 ` [PATCH v5] " Stephen Hemminger
@ 2024-08-01 15:31 ` Stephen Hemminger
2024-10-16 15:48 ` Medvedkin, Vladimir
4 siblings, 1 reply; 12+ messages in thread
From: Stephen Hemminger @ 2024-08-01 15:31 UTC (permalink / raw)
To: dev
Cc: Stephen Hemminger, Yipeng Wang, Sameh Gobriel, Bruce Richardson,
Vladimir Medvedkin
The existing hash functions in DPDK are not cryptographically
secure and can be subject to carefully crafted packets causing
DoS attack.
Add SipHash which is a fast and cryptographicly sound hash
created by Jean-Philippe Aumasson and Daniel J. Bernstein.
Siphash is widely used by Linux, FreeBSD, OpenBSD and other
projects because it is fast and resistant to DoS attacks.
This version is designed to be useful as alternative hash
with cuckoo hash in DPDK.
Implementation is based of the public domain and Creative
Common license reference version as well as some optimizations
from the GPL-2 or BSD-3 licensed version in Linux.
Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
---
v6 - rebase to 24.07
app/test/test_hash_functions.c | 75 +++++++++++++-
lib/hash/meson.build | 2 +
lib/hash/rte_siphash.c | 176 +++++++++++++++++++++++++++++++++
lib/hash/rte_siphash.h | 87 ++++++++++++++++
lib/hash/version.map | 4 +
5 files changed, 340 insertions(+), 4 deletions(-)
create mode 100644 lib/hash/rte_siphash.c
create mode 100644 lib/hash/rte_siphash.h
diff --git a/app/test/test_hash_functions.c b/app/test/test_hash_functions.c
index 70820d1f19..010839eeb7 100644
--- a/app/test/test_hash_functions.c
+++ b/app/test/test_hash_functions.c
@@ -15,6 +15,7 @@
#include <rte_hash.h>
#include <rte_jhash.h>
#include <rte_hash_crc.h>
+#include <rte_siphash.h>
#include "test.h"
@@ -52,6 +53,42 @@ static uint32_t hash_values_crc[2][12] = {{
}
};
+static uint32_t hash_values_hsiphash[2][12] = {
+ {
+ 0x8e01e473, 0xc41e3669,
+ 0x813e4dbd, 0x7ebe2eea,
+ 0x33a5c5b7, 0xc910629b,
+ 0xba50237f, 0xbbc870c6,
+ 0x95124362, 0x850f8e0d,
+ 0x192ff266, 0xb41d8206,
+ }, {
+ 0x66200aa0, 0x769e7201,
+ 0x0e934d03, 0x96d7c892,
+ 0xb4643534, 0xcb758913,
+ 0x498b66e9, 0x116b4082,
+ 0x603030dc, 0x644b608b,
+ 0x74b29c27, 0x513f3a9c,
+ }
+};
+
+static uint64_t hash_values_siphash[2][12] = {
+ {
+ 0x8b5a0baa49fbc58d, 0x62c3506f27376c25,
+ 0xef7bdf3ee24abec8, 0xc72b1c24fc2f7938,
+ 0xc902632ed88f897f, 0xab631e00063006f5,
+ 0x7b821577565ea3a4, 0x8b19265d1c12cdc7,
+ 0x610e7ab6ada60b22, 0x3c6f1970dd62f235,
+ 0x4b8db19fd6940031, 0xa43827a530b08989,
+ }, {
+ 0x86e1bbae2893aaf1, 0x9c05614a696cda03,
+ 0x9ee31847083019c3, 0x600e860c97264e31,
+ 0xda8721038e4972bc, 0xfeedeb1b8bfe5d1e,
+ 0xb2d6388922af426f, 0x7d05b8e82e38cf30,
+ 0x439caa6ecd0b628d, 0x6d4c4ba6f3f2aed5,
+ 0x5622bb0da20658ff, 0x409d76de4adcd475,
+ }
+};
+
/*******************************************************************************
* Hash function performance test configuration section. Each performance test
* will be performed HASHTEST_ITERATIONS times.
@@ -61,9 +98,14 @@ static uint32_t hash_values_crc[2][12] = {{
*/
#define HASHTEST_ITERATIONS 1000000
#define MAX_KEYSIZE 64
-static rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc};
-static uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
-static uint32_t hashtest_key_lens[] = {
+static const rte_hash_function hashtest_funcs[] = {rte_jhash, rte_hash_crc, rte_hsiphash};
+static const uint32_t hashtest_initvals[] = {0, 0xdeadbeef};
+static const uint64_t hashtest_initkeys[][2] = {
+ { 0, 0, },
+ { UINT64_C(0xfeedc0dedeadbeef), 0 },
+};
+
+static const uint32_t hashtest_key_lens[] = {
1, 2, /* Unusual key sizes */
4, 8, 16, 32, 48, 64, /* standard key sizes */
9, /* IPv4 SRC + DST + protocol, unpadded */
@@ -85,6 +127,9 @@ get_hash_name(rte_hash_function f)
if (f == rte_hash_crc)
return "rte_hash_crc";
+ if (f == rte_hsiphash)
+ return "hsiphash";
+
return "UnknownHash";
}
@@ -126,6 +171,7 @@ run_hash_func_perf_tests(void)
printf(" Number of iterations for each test = %d\n",
HASHTEST_ITERATIONS);
printf("Hash Func. , Key Length (bytes), Initial value, Ticks/Op.\n");
+ fflush(stdout);
for (i = 0; i < RTE_DIM(hashtest_initvals); i++) {
for (j = 0; j < RTE_DIM(hashtest_key_lens); j++) {
@@ -147,13 +193,15 @@ verify_precalculated_hash_func_tests(void)
{
unsigned i, j;
uint8_t key[64];
- uint32_t hash;
for (i = 0; i < 64; i++)
key[i] = (uint8_t) i;
for (i = 0; i < RTE_DIM(hashtest_key_lens); i++) {
for (j = 0; j < RTE_DIM(hashtest_initvals); j++) {
+ uint32_t hash;
+ uint64_t shash;
+
hash = rte_jhash(key, hashtest_key_lens[i],
hashtest_initvals[j]);
if (hash != hash_values_jhash[j][i]) {
@@ -173,6 +221,25 @@ verify_precalculated_hash_func_tests(void)
hash_values_crc[j][i], hash);
return -1;
}
+
+ hash = rte_hsiphash(key, hashtest_key_lens[i], hashtest_initvals[j]);
+ if (hash != hash_values_hsiphash[j][i]) {
+ printf("Hsiphash for %u bytes with initial value 0x%x."
+ "Expected 0x%x, but got 0x%x\n",
+ hashtest_key_lens[i], hashtest_initvals[j],
+ hash_values_hsiphash[j][i], hash);
+ return -1;
+ }
+
+ shash = rte_siphash(key, hashtest_key_lens[i], hashtest_initkeys[j]);
+ if (shash != hash_values_siphash[j][i]) {
+ printf("siphash for %u bytes initial %#"PRIx64", %#"PRIx64"."
+ "Expected %#"PRIx64", but got %#"PRIx64"\n",
+ hashtest_key_lens[i],
+ hashtest_initkeys[j][0], hashtest_initkeys[j][1],
+ hash_values_siphash[j][i], shash);
+ return -1;
+ }
}
}
diff --git a/lib/hash/meson.build b/lib/hash/meson.build
index 277eb9fa93..913855124d 100644
--- a/lib/hash/meson.build
+++ b/lib/hash/meson.build
@@ -6,6 +6,7 @@ headers = files(
'rte_hash_crc.h',
'rte_hash.h',
'rte_jhash.h',
+ 'rte_siphash.h',
'rte_thash.h',
'rte_thash_gfni.h',
)
@@ -21,6 +22,7 @@ sources = files(
'rte_cuckoo_hash.c',
'rte_hash_crc.c',
'rte_fbk_hash.c',
+ 'rte_siphash.c',
'rte_thash.c',
'rte_thash_gfni.c',
)
diff --git a/lib/hash/rte_siphash.c b/lib/hash/rte_siphash.c
new file mode 100644
index 0000000000..1b609fddeb
--- /dev/null
+++ b/lib/hash/rte_siphash.c
@@ -0,0 +1,176 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ *
+ * Based on code reference code licensed as CC0 and MIT.
+ * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+ * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+#include <rte_byteorder.h>
+#include <rte_common.h>
+
+#include "rte_siphash.h"
+
+static __rte_always_inline uint64_t
+rol64(uint64_t x, unsigned int b)
+{
+ return (x << b) | (x >> (64 - b));
+}
+
+static __rte_always_inline uint64_t u8to64_le(const uint8_t *p)
+{
+ uint64_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_64(w);
+}
+
+static __rte_always_inline uint32_t u8to32_le(const uint8_t *p)
+{
+ uint32_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_32(w);
+}
+
+static __rte_always_inline uint16_t u8to16_le(const uint8_t *p)
+{
+ uint16_t w;
+
+ memcpy(&w, p, sizeof(w));
+ return rte_cpu_to_le_16(w);
+}
+
+
+/*
+ * Use a 64bit version of SipHash for both full and
+ * half versions, The difference is the number of rounds.
+ */
+#define PREAMBLE(len, key0, key1) \
+ uint64_t v0 = UINT64_C(0x736f6d6570736575); \
+ uint64_t v1 = UINT64_C(0x646f72616e646f6d); \
+ uint64_t v2 = UINT64_C(0x6c7967656e657261); \
+ uint64_t v3 = UINT64_C(0x7465646279746573); \
+ uint64_t b = (uint64_t)len << 56; \
+ v3 ^= key1; \
+ v2 ^= key0; \
+ v1 ^= key1; \
+ v0 ^= key0
+
+#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)
+
+uint64_t
+rte_siphash(const void *key, uint32_t len, const uint64_t init[2])
+{
+ const uint8_t *data = key;
+ const uint32_t left = len & 7;
+ const uint8_t *end = data + (len - left);
+
+ PREAMBLE(len, init[0], init[1]);
+
+ for (; data != end; data += 8) {
+ uint64_t m = u8to64_le(data);
+ v3 ^= m;
+ SIPROUND;
+ SIPROUND;
+ v0 ^= m;
+ }
+
+ switch (left) {
+ case 7:
+ b |= ((uint64_t)end[6]) << 48; /* fallthrough */
+ case 6:
+ b |= ((uint64_t)end[5]) << 40; /* fallthrough */
+ case 5:
+ b |= ((uint64_t)end[4]) << 32; /* fallthrough */
+ case 4:
+ b |= u8to32_le(data);
+ break;
+ case 3:
+ b |= ((uint64_t)end[2]) << 16; /* fallthrough */
+ case 2:
+ b |= u8to16_le(data);
+ break;
+ case 1:
+ b |= data[0];
+ }
+
+ v3 ^= b;
+ SIPROUND;
+ SIPROUND;
+
+ v0 ^= b;
+ v2 ^= 0xff;
+
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
+
+uint32_t
+rte_hsiphash(const void *key, uint32_t len, uint32_t init_val)
+{
+ const uint8_t *data = key;
+ const uint32_t left = len & 7;
+ const uint8_t *end = data + (len - left);
+
+ PREAMBLE(len, init_val, 0);
+
+ for (; data != end; data += 8) {
+ uint64_t m = u8to64_le(data);
+ v3 ^= m;
+ SIPROUND;
+ v0 ^= m;
+ }
+
+ switch (left) {
+ case 7:
+ b |= ((uint64_t)end[6]) << 48; /* fallthrough */
+ case 6:
+ b |= ((uint64_t)end[5]) << 40; /* fallthrough */
+ case 5:
+ b |= ((uint64_t)end[4]) << 32; /* fallthrough */
+ case 4:
+ b |= u8to32_le(data);
+ break;
+ case 3:
+ b |= ((uint64_t)end[2]) << 16; /* fallthrough */
+ case 2:
+ b |= u8to16_le(data);
+ break;
+ case 1:
+ b |= data[0];
+ }
+
+ v3 ^= b;
+ SIPROUND;
+
+ v0 ^= b;
+ v2 ^= 0xff;
+
+ SIPROUND;
+ SIPROUND;
+ SIPROUND;
+
+ return (v0 ^ v1) ^ (v2 ^ v3);
+}
diff --git a/lib/hash/rte_siphash.h b/lib/hash/rte_siphash.h
new file mode 100644
index 0000000000..964e374f44
--- /dev/null
+++ b/lib/hash/rte_siphash.h
@@ -0,0 +1,87 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ *
+ * Based on code reference code licensed as CC0 and MIT.
+ * Copyright (c) 2012-2022 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+ * Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
+ */
+
+#ifndef _RTE_SIPHASH_H
+#define _RTE_SIPHASH_H
+
+/**
+ * @file
+ *
+ * SipHash is a family of pseudorandom functions (PRFs) optimized for speed on short messages.
+ *
+ * SipHash was designed in 2012 by Jean-Philippe Aumasson and Daniel J. Bernstein as a defense
+ * against hash-flooding DoS attacks.
+ *
+ * SipHash is simpler and faster on short messages than previous cryptographic algorithms,
+ * such as MACs based on universal hashing.
+ * Competitive in performance with insecure non-cryptographic algorithms.
+ *
+ * Cryptographically secure, with no sign of weakness despite multiple cryptanalysis projects
+ * by leading cryptographers.
+ *
+ * Battle-tested, with successful integration in OSs (Linux kernel, OpenBSD, FreeBSD, FreeRTOS),
+ * languages (Perl, Python, Ruby, etc.), libraries (OpenSSL libcrypto, Sodium, etc.)
+ * and applications (Wireguard, Redis, etc.).
+ *
+ * As a secure pseudorandom function (a.k.a. keyed hash function), SipHash can also be used as
+ * a secure message authentication code (MAC). But SipHash is not a hash in the sense of
+ * general-purpose key-less hash function such as BLAKE3 or SHA-3.
+ * SipHash should therefore always be used with a secret key in order to be secure.
+ * siphash functions.
+ *
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdint.h>
+
+#include <rte_compat.h>
+
+/**
+ * Compute a SipHash-2-4.
+ * This version is the original version described in the reference version.
+ * It uses a 64 bit key; does 2 compression rounds, and 4 finalization rounds.
+ *
+ * @param data
+ * Data to perform hash on.
+ * @param len
+ * How many bytes to use to calculate hash value.
+ * @param init_vals
+ * 128-bit value to initialize hash generator.
+ * @return
+ * 64bit calculated hash value.
+ */
+__rte_experimental
+uint64_t
+rte_siphash(const void *data, uint32_t len, const uint64_t init_vals[2]);
+
+/**
+ * Compute Siphash-1-3.
+ * This is the faster version which is used by Linux and other OS's.
+ * It uses a 32 bit key; does 1 compression round, and 3 finalization rounds.
+ * The function can be used with in hash_parameters with rte_hash_create().
+ *
+ * @param data
+ * Data to perform hash on.
+ * @param len
+ * How many bytes to use to calculate hash value.
+ * @param init_val
+ * Value to initialize hash generator.
+ * @return
+ * 32bit calculated hash value.
+ */
+__rte_experimental
+uint32_t
+rte_hsiphash(const void *data, uint32_t len, uint32_t init_val);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_SIPHASH_H */
diff --git a/lib/hash/version.map b/lib/hash/version.map
index d348dd9196..5b8b342645 100644
--- a/lib/hash/version.map
+++ b/lib/hash/version.map
@@ -59,4 +59,8 @@ EXPERIMENTAL {
# added in 24.07
rte_hash_rcu_qsbr_dq_reclaim;
+
+ # added in 24.11
+ rte_siphash;
+ rte_hsiphash;
};
--
2.43.0
^ permalink raw reply [flat|nested] 12+ messages in thread* Re: [PATCH v6] lib/hash: add siphash
2024-08-01 15:31 ` [PATCH v6] " Stephen Hemminger
@ 2024-10-16 15:48 ` Medvedkin, Vladimir
2024-10-16 17:07 ` Stephen Hemminger
0 siblings, 1 reply; 12+ messages in thread
From: Medvedkin, Vladimir @ 2024-10-16 15:48 UTC (permalink / raw)
To: Stephen Hemminger, dev; +Cc: Wang, Yipeng1, Gobriel, Sameh, Richardson, Bruce
Hi Stephen,
Thanks for introducing this hash function.
I have just a few nits:
On 01/08/2024 16:31, Stephen Hemminger wrote:
> The existing hash functions in DPDK are not cryptographically
> secure and can be subject to carefully crafted packets causing
> DoS attack.
Currently in DPDK we have 3 hash functions, 2 of them can be used with
our cuckoo hash table implementation:
1. CRC - Very weak, do not use with hash table if you don't fully
control all keys to install into a hash table.
2. Toeplitz - keyed hash function, not used with hash tables, fastest if
you have GFNI, level of diffusion fully depends on the hash key, weak
against differential crypto analysis. Technically may be used with hash
tables in number of usecases.
3. Jenkins hash (lookup3) - and here I can not say that it is not secure
and it is subject to collisions. I'm not aware on any successful attacks
on it, it has a great diffusion (see https://doi.org/10.1002/spe.2179).
It is also keyed with the same size of the key as rte_hsiphash().
So I won't agree with this sentence.
>
> Add SipHash which is a fast and cryptographicly sound hash
> created by Jean-Philippe Aumasson and Daniel J. Bernstein.
> Siphash is widely used by Linux, FreeBSD, OpenBSD and other
> projects because it is fast and resistant to DoS attacks.
> This version is designed to be useful as alternative hash
> with cuckoo hash in DPDK.
>
> Implementation is based of the public domain and Creative
> Common license reference version as well as some optimizations
> from the GPL-2 or BSD-3 licensed version in Linux.
>
> Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
> ---
> v6 - rebase to 24.07
>
> app/test/test_hash_functions.c | 75 +++++++++++++-
> lib/hash/meson.build | 2 +
> lib/hash/rte_siphash.c | 176 +++++++++++++++++++++++++++++++++
> lib/hash/rte_siphash.h | 87 ++++++++++++++++
> lib/hash/version.map | 4 +
> 5 files changed, 340 insertions(+), 4 deletions(-)
> create mode 100644 lib/hash/rte_siphash.c
> create mode 100644 lib/hash/rte_siphash.h
<snip>
> + return (v0 ^ v1) ^ (v2 ^ v3);
do we need parentheses here? XOR is associative and commutative, the
compiler must figure out by itself in which order it will be better to
add them together
<snip>
Also please add release notes.
Apart from it - LGTM.
Acked-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
--
Regards,
Vladimir
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH v6] lib/hash: add siphash
2024-10-16 15:48 ` Medvedkin, Vladimir
@ 2024-10-16 17:07 ` Stephen Hemminger
2024-10-16 18:06 ` Medvedkin, Vladimir
0 siblings, 1 reply; 12+ messages in thread
From: Stephen Hemminger @ 2024-10-16 17:07 UTC (permalink / raw)
To: Medvedkin, Vladimir; +Cc: dev, Wang, Yipeng1, Gobriel, Sameh, Richardson, Bruce
On Wed, 16 Oct 2024 16:48:12 +0100
"Medvedkin, Vladimir" <vladimir.medvedkin@intel.com> wrote:
> Hi Stephen,
>
> Thanks for introducing this hash function.
>
> I have just a few nits:
>
> On 01/08/2024 16:31, Stephen Hemminger wrote:
> > The existing hash functions in DPDK are not cryptographically
> > secure and can be subject to carefully crafted packets causing
> > DoS attack.
> Currently in DPDK we have 3 hash functions, 2 of them can be used with
> our cuckoo hash table implementation:
>
> 1. CRC - Very weak, do not use with hash table if you don't fully
> control all keys to install into a hash table.
>
> 2. Toeplitz - keyed hash function, not used with hash tables, fastest if
> you have GFNI, level of diffusion fully depends on the hash key, weak
> against differential crypto analysis. Technically may be used with hash
> tables in number of usecases.
>
> 3. Jenkins hash (lookup3) - and here I can not say that it is not secure
> and it is subject to collisions. I'm not aware on any successful attacks
> on it, it has a great diffusion (see https://doi.org/10.1002/spe.2179).
> It is also keyed with the same size of the key as rte_hsiphash().
>
> So I won't agree with this sentence.
I am not a crypto or hash expert. This text is based on the statements
by the original author of siphash who does have such expertise.
See the wikipedia page: https://en.wikipedia.org/wiki/SipHash
and the original paper:
https://web.archive.org/web/20170327151630/https://131002.net/siphash/siphash.pdf
The problem is that Jenkins and Toeplitz
"were designed to have a close-to-uniform distribution, not to
meet any particular cryptographic goals"
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH v6] lib/hash: add siphash
2024-10-16 17:07 ` Stephen Hemminger
@ 2024-10-16 18:06 ` Medvedkin, Vladimir
0 siblings, 0 replies; 12+ messages in thread
From: Medvedkin, Vladimir @ 2024-10-16 18:06 UTC (permalink / raw)
To: Stephen Hemminger; +Cc: dev, Wang, Yipeng1, Gobriel, Sameh, Richardson, Bruce
[-- Attachment #1: Type: text/plain, Size: 2843 bytes --]
On 16/10/2024 18:07, Stephen Hemminger wrote:
> On Wed, 16 Oct 2024 16:48:12 +0100
> "Medvedkin, Vladimir"<vladimir.medvedkin@intel.com> wrote:
>
>> Hi Stephen,
>>
>> Thanks for introducing this hash function.
>>
>> I have just a few nits:
>>
>> On 01/08/2024 16:31, Stephen Hemminger wrote:
>>> The existing hash functions in DPDK are not cryptographically
>>> secure and can be subject to carefully crafted packets causing
>>> DoS attack.
>> Currently in DPDK we have 3 hash functions, 2 of them can be used with
>> our cuckoo hash table implementation:
>>
>> 1. CRC - Very weak, do not use with hash table if you don't fully
>> control all keys to install into a hash table.
>>
>> 2. Toeplitz - keyed hash function, not used with hash tables, fastest if
>> you have GFNI, level of diffusion fully depends on the hash key, weak
>> against differential crypto analysis. Technically may be used with hash
>> tables in number of usecases.
>>
>> 3. Jenkins hash (lookup3) - and here I can not say that it is not secure
>> and it is subject to collisions. I'm not aware on any successful attacks
>> on it, it has a great diffusion (seehttps://doi.org/10.1002/spe.2179).
>> It is also keyed with the same size of the key as rte_hsiphash().
>>
>> So I won't agree with this sentence.
> I am not a crypto or hash expert. This text is based on the statements
> by the original author of siphash who does have such expertise.
> See the wikipedia page:https://en.wikipedia.org/wiki/SipHash
> and the original paper:
> https://web.archive.org/web/20170327151630/https://131002.net/siphash/siphash.pdf
>
> The problem is that Jenkins and Toeplitz
> "were designed to have a close-to-uniform distribution, not to
> meet any particular cryptographic goals"
The original paper link isn't working, for review I used this:
https://www.aumasson.jp/siphash/siphash.pdf
Let me quote a bit more form this WP:
"Recent hash-table proposals such as Google’s CityHash [18] and Jenkins’
SpookyHash [21] provide very fast hashing of short strings, but these
functions were designed to have a close-to-uniform distribution, not to
meet any particular cryptographic goals. For example, collisions were
found in an initial version of CityHash128 [22], and the current version
is vulnerable to a practical key-recovery attack when 64-bit keys are used."
I haven't found anything about the lookup3 hash function, which is
different from the SpookyHash hash function implemented by Bob Jenkins.
IunderstandthatSipHashhasgoodcryptographicqualityandcanbeusedforMAC,buthereweare
talkingaboutNCHFthatare usedforhashtables,andinthiscasea
gooduniformdistributionof hashvaluesis veryimportant. Siphash has this
property, as does lookup3.
P.S. Regarding above mentioned collisions in CityHash128 - it seem the
problem was solved in 2015
--
Regards,
Vladimir
[-- Attachment #2: Type: text/html, Size: 9635 bytes --]
^ permalink raw reply [flat|nested] 12+ messages in thread