Re: [PATCH v2] lib/hash: add siphash

["Mattias Rönnblom" <hofors@lysator.liu.se>]

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;
> +};