MurmurHash — це проста і швидка некриптографічна хеш-функція, яка підходить для загального пошуку на основі хешування. Chouza et al . Вона був створений Остіном Епплбі в 2008 році і зараз розміщена на GitHub разом із набором тестів під назвою «SMHasher». Вона існує в декількох варіантах , усі з яких опубліковані у відкритому доступі. Назва походить від двох основних операцій, множення (MU-ltiply) і повороту (R-otate), які використовуються у її внутрішньому циклі.
На відміну від криптографічних хеш-функцій, вона не розроблена спеціально для того, щоб її було важко відмінити зловмисником, що робить її непридатною для криптографічних цілей.
Із переваг функції автори виділяють простоту, хороший розподіл, хороший лавиновий ефект, висока швидкість и доволі висока стійкість до колізій.
Варіанти
MurmurHash3 Поточна версія — MurmurHash3 , яка повертає 32- або 128-бітове хеш-значення. При використанні 128-бітів версії x86 і x64 не видають однакові значення, оскільки алгоритми оптимізовано для відповідних платформ. MurmurHash3 було випущено разом із SMHasher — пакетом для тестування хеш-функцій.
MurmurHash2 MurmurHash2 видає 32- або 64-бітне значення. Він випускався в кількох варіантах, включаючи такі, які дозволяють використовувати інкрементальне хешування.
MurmurHash2 (32-розрядний, x86) - Оригінальна версія; містить недолік, який у деяких випадках призводить до більшої частоти колізій. MurmurHash2A (32-розрядний, x86) – фіксований варіант із використанням конструкції Меркла–Дамгорда . Трохи повільніший. CMurmurHash2A (32-розрядний, x86) - MurmurHash2A, але працює інкрементально. MurmurHashNeutral2 (32-розрядний, x86) - повільніше, але endian і нейтральний до вирівнювання. MurmurHashAligned2 (32-розрядний, x86) — повільніше, але виконує вирівняне читання (що безпечніше на деяких платформах). MurmurHash64A (64-розрядна, x64) - оригінальна 64-bit версія. Оптимізована для 64-розрядної арифметики. MurmurHash64B (64-розрядна, x86) - 64-розрядна версія, оптимізована для 32-розрядних платформ. Це не справжній 64-бітний хеш через недостатнє змішування смуг.
MurmurHash1 Оригінальний MurmurHash був створений як спроба створити швидшу функцію, ніж Lookup3 . Незважаючи на успіх, він не був ретельно протестований і не міг забезпечити створення 64-розрядних хешів, як у Lookup3. Вона мала досить елегантний дизайн, який пізніше буде перенесений на MurmurHash2, поєднуючи мультиплікативний хеш (схожий на хеш-функцію Фаулера–Нолла–Во ) та Xorshift .
Реалізації Канонічна реалізація в C++, але функція була портована для багатьох популярних мов, включаючи Python, C, Go, C#, D, Lua, Perl, Ruby, Rust, PHP, Common Lisp, Haskell, Elm, Clojure, [ Scala, Java, Murmur3, part of Guava Erlang, Swift, Object Pascal, GitHub - Xor-el/HashLib4Pascal: Hashing for Modern Object Pascal Kotlin, і JavaScript .
Вона використовується у ряді проектів з відкритим вихідним кодом, зокрема libstdc++ (версія 4.6), nginx (версія 1.0.1), Rubinius, libmemcached (драйвер C для Memcached ), npm (менеджер пакетів nodejs), maatkit, Hadoop, Kyoto Cabinet, Cassandra, Solr, vowpal wabbit, Elasticsearch, Guava, Kafka і RedHat Virtual Data Optimizer (VDO) . Virtual Data Optimizer source code
Вразливості Хеш-функції можуть бути вразливими до колізійних атак, коли користувач може вибрати вхідні дані таким чином, щоб навмисно спричинити хеш-колізії. Жан-Філіп Омассон і Деніел Дж. Бернштейн змогли показати, що навіть реалізації MurmurHash із використанням рандомізованого початкового числа вразливі до так званих атак HashDoS. За допомогою диференціального криптоаналізу вони змогли згенерувати вхідні дані, які призвели б до хеш-колізії. Автори атаки рекомендують замість цього використовувати власну функцію SipHash .
Алгоритм є алгоритм Murmur3_32 // Примітка: у цій версії вся арифметика виконується з 32-розрядними беззнаковими цілими числами. // У разі переповнення результат обрізається за модулем . input: key, len, seed
c1 ← 0xcc9e2d51 c2 ← 0x1b873593 r1 ← 15 r2 ← 13 м ← 5 n ← 0xe6546b64
hash← seed
for each fourByteChunk of key 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
with any remainingBytesInKey do remainingBytes ← SwapToLittleEndian(remainingBytesInKey) // Примітка: зміна порядку байтів необхідна лише на машинах з непрямим порядком байтів (big-endian).
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) Нижче наведено зразок реалізації C (для ЦП з прямим порядком байтів):static inline uint32_t murmur_32_scramble(uint32_t k) { k *= 0xcc9e2d51; k = (k << 15) | (k >> 17); k *= 0x1b873593; return k; } uint32_t murmur3_32(const uint8_t* key, size_t len, uint32_t seed) { uint32_t h = seed; uint32_t k; /* Read in groups of 4. */ for (size_t i = len >> 2; i; i--) { // Here is a source of differing results across endiannesses. // A swap here has no effects on hash properties though. memcpy(&k, key, sizeof(uint32_t)); key += sizeof(uint32_t); h ^= murmur_32_scramble(k); h = (h << 13) | (h >> 19); h = h * 5 + 0xe6546b64;
/* Read the rest. */ k = 0; for (size_t i = len & 3; i; i--) { k <<= 8; k |= key[i - 1];
// A swap is *not* necessary here because the preceding loop already // places the low bytes in the low places according to whatever endianness // we use. Swaps only apply when the memory is copied in a chunk. h ^= murmur_32_scramble(k); /* Finalize. */ h ^= len; h ^= h >> 16; h *= 0x85ebca6b; h ^= h >> 13; h *= 0xc2b2ae35; h ^= h >> 16; return h; }
Дивись також
Некриптографічні хеш-функції
Посилання