MurmurHash

MurmurHash3

The current version is MurmurHash3, which yields a 32-bit or 128-bit hash value. When using 128-bits, the x86 and x64 versions do not produce the same values, as the algorithms are optimized for their respective platforms.

MurmurHash2

The older MurmurHash2 yields a 32-bit or 64-bit value. Slower versions of MurmurHash2 are available for big-endian and aligned-only machines. The MurmurHash2A variant adds the Merkle–Damgård construction so that it can be called incrementally. There are two variants which generate 64-bit values; MurmurHash64A, which is optimized for 64-bit processors, and MurmurHash64B, for 32-bit ones. MurmurHash2-160 generates the 160-bit hash, and MurmurHash1 is obsolete.

Implementations

The canonical implementation is in C++, but there are efficient ports for a variety of popular languages, including Python, C, Go, C#, D, Perl, Ruby, Rust, PHP, Common Lisp, Haskell, Clojure, Scala, Java, Erlang, and JavaScript, together with an online version.

It has been adopted into a number of open-source projects, most notably libstdc++ (ver 4.6), nginx (ver 1.0.1), Rubinius, libmemcached (the C driver for Memcached), npm (nodejs package manager), maatkit, Hadoop, Kyoto Cabinet, RaptorDB, OlegDB, Cassandra, Solr, vowpal wabbit,Elasticsearch, and Guava.

Vulnerabilities

Hash functions can be vulnerable to attack if a user can choose input data in such as way to intentionally cause hash collisions. Jean-Philippe Aumasson and Daniel J. Bernstein were able to show that even implementations of MurmurHash using a randomized seed are vulnerable to so-called HashDoS attacks. With the use of differential cryptanalysis they were able to generate inputs that would lead to a hash collision. The authors of the attack recommend to use their own SipHash instead.

Algorithm

Murmur3_32(key, len, seed) // Note: In this version, all integer arithmetic is performed with unsigned 32 bit integers. // In the case of overflow, the result is constrained by the application of modulo 2 32 arithmetic. c1 ← 0xcc9e2d51 c2 ← 0x1b873593 r1 ← 15 r2 ← 13 m ← 5 n ← 0xe6546b64 hash ← seed for each fourByteChunk of key k ← fourByteChunk k ← k × c1 k ← (k ROL r1) k ← k × c2 hash ← hash XOR k hash ← (hash ROL r2) hash ← hash × m + n with any remainingBytesInKey remainingBytes ← SwapToLittleEndian(remainingBytesInKey) // Note: Endian swapping is only necessary on big-endian machines. // The purpose is to place the meaningful digits towards the low end of the value, // so that these digits have the greatest potential to affect the low range digits // in the subsequent multiplication. Consider that locating the meaningful digits // in the high range would produce a greater effect upon the high digits of the // multiplication, and notably, that such high digits are likely to be discarded // by the modulo arithmetic under overflow. We don't want that. remainingBytes ← remainingBytes × c1 remainingBytes ← (remainingBytes ROL r1) remainingBytes ← remainingBytes × c2 hash ← hash XOR remainingBytes hash ← hash XOR len hash ← hash XOR (hash >> 16) hash ← hash × 0x85ebca6b hash ← hash XOR (hash >> 13) hash ← hash × 0xc2b2ae35 hash ← hash XOR (hash >> 16)

A sample C implementation follows (for little-endian CPUs)