A very fast cryptographic hash function for large data.


Keywords
hash, crypto, cryptography, digest, fast, nhpoly1305, rust, uhf
License
ISC

Documentation

STHash

docs.rs

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

Thanks

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