jedisct1/rust-sthash

Very fast cryptographic hashing for large messages.

STHash

STHash is a fast, keyed, cryptographic hash function designed to process large, possibly untrusted data.

The flipside is that using a secret key (or, in this implementation, a secret seed) is mandatory. This is not a general-purpose hash function.

A typical use of STHash is to compute keys for locally cached objects.

The construction relies on:

• A composition of two ϵ-almost-∆-universal functions, NH and Poly1305. See the Adiantum paper for a justification of this composition.
• The cSHAKE function as a XOF to derive the NH, Poly1305 and finalization keys, and KMAC to produce the final tag.

The current code is portable, written in safe Rust, and has a lot of room for optimization.

However, it is already consistently faster than optimized BLAKE2bp and BLAKE3 implementations on all common platforms.

You can expect future versions to be even faster.

Usage

use sthash::*;
use rand::{thread_rng, RngCore};

// This must be a random, secret seed.
let mut seed = [0u8; SEED_BYTES];
thread_rng().fill_bytes(&mut seed);

// The key constructor accepts an optional application name
// Different personalization strings produce different keys
// from the same `seed`.
let key = Key::from_seed(&seed, Some(b"Documentation example"));

// Another personalization string, such as the purpose of the
// `Hasher`, can be provided here as well.
let hasher = Hasher::new(key, None);

// Returns a 256-bit hash.
let h1 = hasher.hash(b"data");

// `Hasher` structures can safely be reused to hash more data.
let h2 = hasher.hash(b"data2");

Benchmarks

Measurements from the built-in benchmark, hashing 1 Mb data. Get your own data with the cargo bench command.

Comparison with BLAKE3 (from blake3)

Machine	BLAKE3 (μs)	STHash (μs)	Ratio
Apple M1, MacOS	646	119	5.4
AMD Zen2, Ubuntu	212	71	3.0
AMD Zen4 (Ryzen 7700), Ubuntu	148	61	2.4
Core i9 2.9Ghz, MacOS	226	86	2.6
ARMv8 (Freebox Delta), Debian Linux VM	3729	646	5.8

Comparison with BLAKE2bp (from blake2b-simd)

Machine	BLAKE2bp (μs)	STHash (μs)	Ratio
Core i9 2.9Ghz, MacOS	391	95	4.1
Core i7 2.8Ghz, MacOS	607	134	4.5
Xeon CPU E5-1650 v4 3.60GHz, Ubuntu Linux	479	130	3.7
Xeon CPU E3-1245 V2 3.40GHz, OpenBSD VM	2681	493	5.4
ARMv8 (Freebox Delta), Debian Linux VM	2949	668	4.4
ARMv8 (Raspberry Pi 4b), Raspbian	10496	3127	3.4
ARMv7 (Scaleway C1), Ubuntu Linux	29402	7871	3.7
ARMv7 (Raspberry Pi 3b), Raspbian	19596	4944	4
Atom C3955 2.10GHz (Scaleway Start1-XS), Linux	3709	886	4.2
AMD FX-6300, CentOS Linux	1812	737	2.5
AMD Zen4 (Ryzen 7700), Ubuntu	278	61	4.5

Comparison with HMAC-SHA2 (from rust-crypto)

Machine	HMAC-SHA512 (μs)	STHash (μs)	Ratio
Core i9 2.9Ghz, MacOS	2280	95	24
Core i7 2.8Ghz, MacOS	3233	134	24.1
Xeon CPU E5-1650 v4 3.60GHz, Ubuntu Linux	2600	130	20
Xeon CPU E3-1245 V2 3.40GHz, OpenBSD VM	6423	493	13
ARMv8 (Freebox Delta), Debian Linux VM	4587	668	6.9
ARMv8 (Raspberry Pi 4b), Raspbian	19864	3127	6.4
ARMv7 (Scaleway C1), Ubuntu Linux	167670	7871	21.3
ARMv7 (Raspberry Pi 3b), Raspbian	49309	4944	9.9
Atom C3955 2.10GHz (Scaleway Start1-XS), Linux	7052	886	8
AMD FX-6300, CentOS Linux	3700	737	5

Algorithm

Km || Kp || Kn ← cSHAKE128(seed, c1)

Hp ← Poly1305(Kp, NH(Kn, pad128(M)))

H ← KMAC(Km, c2, pad64(|M|) || Hp)

NH is instantiated with 4 passes and a stride of 2.

M is processed as 1 KB chunks, and the resulting NH hashes are compressed using Poly1305 after 16 hashes have been accumulated (≡ 16 KB of M have been processed).

c1 and c2 are personalization strings.

Kp represents the Poly1305 random secret. In this context, we don't need to perform the final addition with an encrypted nonce.

Values are encoded as little-endian.

References

• UMAC: Fast and Secure Message Authentication (J. Black, S.Halevi, H.Krawczyk, T.Krovetz, and P. Rogaway)
• The Poly1305-AES message authentication code (Daniel J. Bernstein)
• Adiantum: length-preserving encryption for entry-level processors (Paul Crowley and Eric Biggers)
• Short-output universal hash functions and their use in fast and secure data authentication (Yannick Seurin)

Thanks

This crate is based on work by Paul Crowley and Eric Biggers.

rust-sthash's Issues

Rc<HashInner> and Rayon

Many thanks for writing sthash -- it is a cool library. I would like to use sthash within Rayon to hash small blocks in parallel.

I have the problem that the Rc<HashInner> is not thread safe. Would you consider accepting a pull request that removes the Rc completely? As far as I can tell, this would make Clone less efficient but would make the Hasher thread safe without the overhead of adding an Arc.

I can see no mutation of HashInner and so I think this suggested change is possible.

Variant with Blake3 instead of Keccak

Blake3 could work both in MAC and XOF mode, therefore could be used instead of Keccak.

I understand, it will be other algorithm, but did you consider to create such version?