MurmurHash

MurmurHash — це проста і швидка некриптографічна хеш-функція, яка підходить для загального пошуку на основі хешування. Вона був створений Остіном Епплбі в 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, [13] Elm, Clojure, [ Scala, Java, Erlang, Swift, 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) .

Вразливості

Хеш-функції можуть бути вразливими до колізійних атак, коли користувач може вибрати вхідні дані таким чином, щоб навмисно спричинити хеш-колізії. Жан-Філіп Омассон і Деніел Дж. Бернштейн змогли показати, що навіть реалізації MurmurHash із використанням рандомізованого початкового числа вразливі до так званих атак HashDoS. За допомогою диференціального криптоаналізу вони змогли згенерувати вхідні дані, які призвели б до хеш-колізії. Автори атаки рекомендують замість цього використовувати власну функцію SipHash .

Алгоритм

є алгоритм Murmur3_32
  // Примітка: у цій версії вся арифметика виконується з 32-розрядними беззнаковими цілими числами.
  // У разі переповнення результат обрізається за модулем 232 .
  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;
}

Дивись також

• Некриптографічні хеш-функції