MurmurHash2 - это быстрая, некриптографическая хеш-функция, созданная Остином Эпплби (Austin Appleby). Её основное назначение - эффективно генерировать 32-битные или 64-битные хеш-значения из данных произвольной длины (ключей) для использования в структурах данных типа хеш-таблиц, фильтрах Блума или распределённых системах.
Ключевые характеристики и принцип работы
- Высокая скорость: Оптимизирован для современных процессоров, использует эффективные арифметические и битовые операции (умножение, сдвиги >>, <<, XOR ^).
- Хорошее распределение (лавинный эффект): Малейшее изменение входных данных (даже один бит) приводит к значительному и непредсказуемому изменению выходного хеша, минимизируя коллизии для случайных данных.
- Поточная обработка: Данные обрабатываются последовательно, блоками фиксированного размера (обычно по 4 байта для 32-битной версии).
- "Murmur" (смешивание): Сердце алгоритма — операция m, которая интенсивно перемешивает (murmurs) текущее внутреннее состояние (хеш) с очередным блоком данных:
- Блок умножается на константу (M).
- Результат циклически сдвигается (ROTL).
- Умножается на другую константу (N).
- Выполняется операция XOR (^) с текущим значением хеша.
- Цель: Максимально "размазать" влияние каждого входного бита по всему хешу.
- Финальный микс (Final Mix/Avalanche): После обработки всех полных блоков оставшиеся байты (0-3 для 32-битной версии) обрабатываются отдельно. Затем выполняется серия финальных перемешивающих операций над накопленным хешем:
- Хеш ^= (хеш >> R)
- Хеш *= M
- (Повторяется несколько раз с разными R и M)
- Цель: Устранить остаточные закономерности и обеспечить сильный лавинный эффект для последних байтов.
- Семя (Seed): Принимает начальное значение (seed), позволяя генерировать разные последовательности хешей для одного и того же набора данных. Полезно для защиты от атак на хеш-таблицы.
Коллизии
- MurmurHash2 известен уязвимостями, позволяющими искусственно создавать коллизии (разные данные с одинаковым хешем). Это делает его непригодным для безопасности (подписи, пароли).
- Конкретный пример пары коллизий сложен для краткости, но суть: Зная алгоритм, можно специально подобрать два разных сообщения (например, строки или бинарные данные), которые дадут одинаковый хеш MurmurHash2 при одном и том же seed. Это была одна из причин создания MurmurHash3.
Важное предупреждение
Несмотря на скорость и хорошее распределение для случайных данных, MurmurHash2 считается уязвимым к преднамеренным коллизиям. Эта уязвимость делает его небезопасным в контекстах, где злоумышленник может контролировать входные данные (например, веб-запросы, сетевые пакеты). Для таких случаев настоятельно рекомендуется использовать криптографические хеши (SHA-256 и т.д.). MurmurHash2 уместен только в контролируемых средах, где риск искусственных коллизий минимален (например, внутренние хеш-таблицы с доверенными ключами).
