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 seed = [u8; 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(data);

// `Hasher` structures can safely be reused to hash more data.
let h2 = hasher.hash(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), Rust 1.48.

Comparison with BLAKE2bp (from blake2b-simd), Rust 1.39.

Comparison with HMAC-SHA2 (from rust-crypto), Rust 1.39.

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.