HalftimeHash

Almost-universal string hashing for long inputs, from the HalftimeHash paper (2020).

This crate implements the four output widths from Section 4 of the paper as a #![no_std] Rust library. Each variant implements RustCrypto's UniversalHash trait and is optimized for throughput on large messages with SIMD (AVX-512, AVX2, SSE2 on x86-64; NEON on AArch64).

Features

• Four tag widths — 16, 24, 32, and 40 bytes with different almost-universality margins.
• Two keying modes — 32-byte master key with NH KDF (convenient), or external input entropy of arbitrary length (C++ reference style).
• Master keys — [Key32], [Key64], [Key128] (byte count); any key works with any variant.
• no_std — works without the standard library; requires alloc because tree-entropy expansion grows a dynamic word buffer (Vec/Arc) as input length increases. Memory use scales with O(log n) in the input size (tree depth), not with the full message.
• Runtime CPU dispatch on x86-64 (AVX-512 → AVX2 → SSE2 → scalar fallback).
• RustCrypto-compatible API — KeyInit, UniversalHash, one-shot digest.

When to use HalftimeHash

HalftimeHash is a universal hash, not a standalone MAC. It maps (key, message) → tag with strong almost-universality guarantees for long strings, but provides no confidentiality, no nonce handling, and no key commitment on its own.

Good fits:

• Long-message authentication where throughput dominates — bulk data, large records, log streams, file chunks, database pages.
• Custom authenticated-encryption or MAC-then-encrypt designs where you control the full protocol and combine a universal hash with a cipher and a nonce (as in the paper's AEAD construction).
• Tag-size tradeoffs — pick 16/24/32/40 bytes depending on your collision budget; wider tags give more security margin at some CPU cost.
• Experimental or research systems exploring high-throughput almost-universal hashing.

Poor fits — use something else:

• Standard AEAD (TLS, Noise, ChaCha20-Poly1305, AES-GCM) — Poly1305 and GHASH are the interoperable choices.
• Short messages (≤ a few KiB) — fixed setup cost favors Poly1305 and other lightweight MACs (see benchmarks below).
• Standalone message authentication without a surrounding AEAD or encrypt-then-MAC scheme — a universal hash alone is not a complete integrity mechanism.
• Side-channel–sensitive contexts — this implementation prioritizes SIMD throughput; it is not designed as a constant-time MAC like Poly1305.

Comparison with Poly1305

Poly1305 is the de facto universal hash in production AEAD (notably ChaCha20-Poly1305). It produces a 16-byte tag, has a 32-byte key, is fast on short inputs, and is widely audited. HalftimeHash24 produces a 24-byte tag and is designed to win on long strings.

Benchmarks below were measured with cargo bench --bench halftime on a single core of x86-64 (release, LTO). Both hashes receive identical random-looking input; HalftimeHash24 uses digest (one-shot).

Takeaway: Poly1305 stays ahead while the message is small enough that setup and per-block overhead matter. Beyond roughly tens of KiB, HalftimeHash's tree-based design amortizes its cost and pulls ahead; at 1 MiB it is about 7× faster than Poly1305 on the same hardware, while emitting a wider tag.

HalftimeHash16 is even faster on very long inputs (~35 GiB/s at 1 MiB in the same benchmark suite) with a 16-byte tag, at a lower almost-universality margin than HH24.

Variants

All variants accept the same master key types ([Key32], [Key64], [Key128]). Tag types are [Tag16] … [Tag40].

Keys and entropy

HalftimeHash needs a large stream of input entropy (random u64 words) that grows with message length — see Section 4.3 of the paper. This crate supports two ways to supply it:

Master key + NH KDF (default)

Pass a fixed master key ([Key32], [Key64], or [Key128]). The crate derives 32-byte seed material (NH fold for longer keys) and expands entropy on demand with NH — convenient when you only have a short secret key.

use halftime::{HalftimeHash24, Key32};

let key = Key32::from([0x42u8; 32]); // CSPRNG or KDF in production
let tag = HalftimeHash24::digest_master_key(&key, b"message");

[KeyInit] / HalftimeHash24::new accept a 32-byte RustCrypto key and use the same NH expansion.

External entropy (C++ reference style)

Supply a pre-generated &[u64] buffer, as in the C++ const uint64_t* entropy API. Size it with [HalftimeHash24::entropy_words_needed] (or the free function [entropy_words_needed]):

use halftime::HalftimeHash24;

let input = b"message to authenticate";
let need = HalftimeHash24::entropy_words_needed(input.len());
// Fill `entropy` from a CSPRNG in production (one u64 per word).
let entropy: Vec<u64> = vec![0; need];

let tag = HalftimeHash24::digest_with_entropy(&entropy, input).expect("entropy too short");

For incremental hashing with external entropy, call [HalftimeHash24::with_entropy_for] with your maximum expected message length.

Note: [HalftimeHash32] is the variant with a 32-byte tag; [Key32] is a 32-byte master key — different concepts.

Usage

One-shot digest

use halftime::{HalftimeHash24, Key32};

// In production, obtain these 32 bytes from a CSPRNG (e.g. `getrandom`) or a KDF (e.g. HKDF).
let key_bytes = [0x42u8; 32];
let key = Key32::from(key_bytes);

let tag = HalftimeHash24::digest_master_key(&key, b"message to authenticate");
assert_eq!(tag.as_slice().len(), HalftimeHash24::TAG_BYTES);

Incremental hashing

use halftime::{HalftimeHash24, Key32, universal_hash::UniversalHash};

// In production, obtain these 32 bytes from a CSPRNG (e.g. `getrandom`) or a KDF (e.g. HKDF).
let key_bytes = [0x42u8; 32];
let key = Key32::from(key_bytes);

let mut mac = HalftimeHash24::from_master_key(&key);
mac.update_padded(b"first chunk");
mac.update_padded(b"second chunk");
let tag = mac.finalize();

Choosing a variant

use halftime::{HalftimeHash16, HalftimeHash40, Key32};

// Same key type for every variant — the number is key bytes, not tag width.
let key = Key32::from([0x42u8; 32]);
let tag16 = HalftimeHash16::digest_master_key(&key, b"large blob"); // 16-byte tag, fastest
let tag40 = HalftimeHash40::digest_master_key(&key, b"large blob"); // 40-byte tag, strongest margin

Performance

Run the full suite:

cargo bench --bench halftime

Useful filters:

# Head-to-head vs Poly1305
cargo bench --bench halftime -- compare/HalftimeHash24_vs_Poly1305

# All variants at 256 KiB (paper comparison point)
cargo bench --bench halftime -- long_input/256KiB

# Single variant, long input only
cargo bench --bench halftime -- "HalftimeHash16/hash_only/1048576"

Platform notes

Force the portable scalar backend for testing:

RUSTFLAGS='--cfg halftime_backend="soft"' cargo build

Security notes

• HalftimeHash is almost-universal, not collision-resistant or a PRF. Treat tags as authentication values inside a proper AEAD or MAC scheme, not as general-purpose hashes.
• Generate keys from a CSPRNG or KDF — never use predictable placeholder bytes in production.
• Never reuse a (key, nonce) pair across different messages in an AEAD construction (same rule as Poly1305 in ChaCha20-Poly1305).
• Wider variants (HH32, HH40) increase the almost-universality margin at the cost of CPU time; match tag width to your threat model.
• This crate has not received the same level of public audit as Poly1305. Evaluate carefully before production deployment.

License

Licensed under either of:

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.