Szmer Hasz
MurmurHash to niekryptograficzna funkcja skrótu odpowiednia do ogólnego wyszukiwania opartego na hashowaniu. Został stworzony przez Austina Appleby'ego w 2008 roku i jest obecnie hostowany na GitHub wraz z pakietem testowym o nazwie „SMHasher”. Istnieje również w wielu wariantach, z których wszystkie zostały udostępnione w domenie publicznej. Nazwa pochodzi od dwóch podstawowych operacji, mnożenia (MU) i obracania (R), używanych w jej wewnętrznej pętli.
W przeciwieństwie do kryptograficznych funkcji skrótu , nie jest ona specjalnie zaprojektowana tak, aby była trudna do odwrócenia przez przeciwnika, przez co nie nadaje się do celów kryptograficznych.
Warianty
MurmurHash3
Obecna wersja to MurmurHash3, która daje 32-bitową lub 128-bitową wartość skrótu. W przypadku korzystania ze 128-bitów wersje x86 i x64 nie generują tych samych wartości, ponieważ algorytmy są zoptymalizowane pod kątem odpowiednich platform. MurmurHash3 został wydany wraz z SMHasher — zestawem testów funkcji skrótu.
MurmurHash2
MurmurHash2 daje wartość 32-bitową lub 64-bitową. Występował w wielu wariantach, w tym takich, które pozwalały na stopniowe mieszanie i wersje wyrównane lub neutralne.
- MurmurHash2 (32-bitowy, x86) — Oryginalna wersja; zawiera wadę, która w niektórych przypadkach osłabia kolizję.
- MurmurHash2A (32-bitowy, x86) - Naprawiono wariant wykorzystujący konstrukcję Merkle – Damgård . Nieco wolniej.
- CMurmurHash2A (32-bitowy, x86) — MurmurHash2A, ale działa przyrostowo.
- MurmurHashNeutral2 (32-bitowy, x86) — wolniejszy, ale endian i wyrównanie neutralne.
- MurmurHashAligned2 (32-bitowy, x86) — wolniejszy, ale odczyty wyrównane (bezpieczniejsze na niektórych platformach).
- MurmurHash64A (64-bitowy, x64) — oryginalna wersja 64-bitowa. Zoptymalizowany pod kątem arytmetyki 64-bitowej.
- MurmurHash64B (64-bitowy, x86) — wersja 64-bitowa zoptymalizowana pod kątem platform 32-bitowych. To nie jest prawdziwy 64-bitowy skrót z powodu niewystarczającego wymieszania pasków.
Osoba, która pierwotnie znalazła lukę [ wymagane wyjaśnienie ] w MurmurHash2, stworzyła nieoficjalną 160-bitową wersję MurmurHash2 o nazwie MurmurHash2_160.
MurmurHash1
Oryginalny MurmurHash został stworzony jako próba stworzenia funkcji szybszej niż Lookup3 . Chociaż odniósł sukces, nie został dokładnie przetestowany i nie był w stanie zapewnić 64-bitowych skrótów, jak w Lookup3. Miał raczej elegancki wygląd, który później został zbudowany w MurmurHash2, łącząc multiplikatywny skrót (podobny do funkcji skrótu Fowlera – Nolla – Vo ) z Xorshift .
Implementacje
Implementacja kanoniczna jest w C++ , ale istnieją wydajne porty dla różnych popularnych języków, w tym Python , C , Go , C# , D , Lua , Perl , Ruby , Rust , PHP , Common Lisp , Haskell , Elm , Clojure , Scala , Java , Erlang , Swift , Object Pascal , Kotlin i JavaScript .
Został przyjęty w wielu projektach open source, w szczególności libstdc++ (wersja 4.6), nginx (wersja 1.0.1), Rubinius , libmemcached ( sterownik C dla Memcached ), npm (menedżer pakietów nodejs), maatkit , Hadoop , Kyoto Cabinet, Cassandra , Solr , vowpal wabbit , Elasticsearch , Guava , Kafka i RedHat Virtual Data Optimizer (VDO) .
Luki w zabezpieczeniach
Funkcje skrótu mogą być podatne na ataki kolizyjne , w których użytkownik może wybrać dane wejściowe w taki sposób, aby celowo spowodować kolizje skrótów. Jean-Philippe Aumasson i Daniel J. Bernstein byli w stanie wykazać, że nawet implementacje MurmurHash przy użyciu losowego materiału siewnego są podatne na tak zwane ataki HashDoS . Za pomocą kryptoanalizy różnicowej byli w stanie wygenerować dane wejściowe, które doprowadziłyby do kolizji mieszania. Autorzy ataku zalecają zamiast tego użycie własnego SipHash .
Algorytm
algorytm Murmur3_32 to // Uwaga: W tej wersji wszystkie działania arytmetyczne są wykonywane przy użyciu 32-bitowych liczb całkowitych bez znaku. // W przypadku przepełnienia wynik jest redukowany modulo 2 32 . wejście: klucz , len , ziarno c1 ← 0xcc9e2d51 c2 ← 0x1b873593 r1 ← 15 r2 ← 13 m ← 5 n ← 0xe6546b64 hash ← ziarno dla każdego czterobajtowego fragmentu klucza do
k ← fourByteChunk k ← k × c1 k ← k ROL r1 k ← k × c2 hash ← hash XOR k hash ← hash ROL r2 hash ← (hash × m) + n z pozostałymi bajtami w kluczu do pozostałych bajtów ← SwapToLittleEndian (pozostałe bajty w kluczu ) // Uwaga : Zamiana endianów jest konieczna tylko na maszynach big-endian. // Celem jest umieszczenie znaczących cyfr bliżej dolnego końca wartości, // tak aby te cyfry miały jak największy wpływ na cyfry z dolnego zakresu
// w kolejnym mnożeniu. Weź pod uwagę, że umieszczenie znaczących cyfr // w górnym zakresie miałoby większy wpływ na wyższe cyfry // mnożenia, a zwłaszcza, że takie wysokie cyfry prawdopodobnie zostaną odrzucone // przez arytmetykę modulo w przypadku przepełnienia. Nie chcemy tego. pozostałe Bajty ← pozostałe Bajty × c1 pozostałe Bajty ← pozostałe Bajty ROL r1 pozostałe Bajty ← pozostałe Bajty × c2 hash ← hash XOR pozostałe Bajty 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)
Poniżej przykładowa implementacja C (dla procesorów little-endian):
static inline uint32_t murmur_32_scramble ( uint32_t k ) { k *= 0xcc9e2d51 ; k = ( k << 15 ) | ( k >> 17 ); k *= 0x1b873593 ; zwróć k ; } uint32_t murmur3_32 ( const uint8_t * klucz , size_t len
, uint32_t ziarno ) { uint32_t h = ziarno ; uint32_t k ; /* Czytaj w grupach po 4. */ for ( size_t i = len >> 2 ; i ; i -- ) { // Oto źródło różnych wyników dla endianów. // Zamiana tutaj nie ma jednak wpływu na właściwości skrótu. memcpy ( & k , klucz ,
0
rozmiar ( uint32_t )); klucz += rozmiar ( uint32_t ); h ^= szmer_32_scramble ( k ); godz = ( godz << 13 ) | ( h >> 19 ); h = h * 5 + 0xe6546b64 ; } /* Przeczytaj resztę. */ k = ; dla ( rozmiar_t i
= długość & 3 ; ja ; ja -- ) { k <<= 8 ; k |= klucz [ ja - 1 ]; } // Zamiana *nie* jest tutaj konieczna, ponieważ poprzednia pętla już // umieszcza młodsze bajty na niższych miejscach zgodnie z użytą // endiannością. Zamiany mają zastosowanie tylko wtedy, gdy pamięć jest kopiowana w porcji. h ^= szmer_32_scramble ( k ); /* Finalizuj. */
h ^= długość ; godz ^= godz >> 16 ; h *= 0x85ebca6b ; godz ^= godz >> 13 ; h *= 0xc2b2ae35 ; godz ^= godz >> 16 ; powrót h ; }