Non-cryptographic

SipHash

A small, fast, keyed pseudo-random function designed by Jean-Philippe Aumasson and Daniel J. Bernstein in 2012. SipHash is the hash-table defender of choice: fast enough to use in hot inner loops, but secure enough that an attacker who can submit chosen keys cannot construct collisions without first stealing the per-table seed.

SipHash-c-d

• SipHash-2-4 , 2 c-rounds per block, 4 d-rounds at finalization. The standard variant.
• SipHash-1-3 , faster, slightly less margin; used by some language runtimes when the host is trusted.
• SipHashx-4-8 , 128-bit output, sometimes the default for content addressing.

At a glance

The hash-flooding problem it solves

Throughout 2011–2013 it became clear that any web server using a non-keyed hash function as the back-end of a hash-table-keyed-by-user- input was DoS-able: an attacker who knows the hash function can submit thousands of inputs that all collide, forcing the hash table into worst-case O(n²) behavior. Murmur, FNV, and CRC32 were all affected. The standard fix is to seed the hash with a per-process random key. SipHash is designed precisely so that an attacker who does not know the key cannot find colliding inputs.

Where it is used

• Python dict (since CPython 3.4) , PYTHONHASHSEED ↔ SipHash key.
• Ruby Hash, Perl hash, Rust std HashMap (via RandomState).
• Redis, memcached, HAProxy, nginx (internal).
• FreeBSD, OpenBSD, Linux kernels , net-stack flow lookups, namespace dentries.
• libsodium , crypto_shorthash.

Internal structure

SipHash maintains four 64-bit words. The compression step does a couple of ARX rounds (typical mix of additions, rotations, XORs) across the four words, with the input absorbed via XOR before and after. Two final rounds use chosen rotation patterns to spread the last input’s influence over the entire state. Outputs are taken from the state at the end.

Try it

SipHash is not in the in-browser hasher (hash-wasm targets cryptographic and checksum algos); add it from any of the linked reference implementations to verify outputs.

References

• Aumasson & Bernstein , SipHash: a fast short-input PRF (INDOCRYPT 2012)
• SipHash homepage
• MurmurHash3 (the predecessor SipHash was designed to replace)