МурмурХэш
MurmurHash — это некриптографическая хеш-функция, подходящая для общего поиска на основе хэш-функции. [1] [2] [3] Он был создан Остином Эпплби в 2008 году. [4] и в настоящее время размещен на GitHub вместе со своим набором тестов под названием SMHasher. Он также существует в нескольких вариантах, [5] все из которых были переданы в общественное достояние. Название происходит от двух основных операций: умножения (MU) и поворота (R), используемых во внутреннем цикле.
В отличие от криптографических хеш-функций , она не предназначена специально для того, чтобы ее было трудно отменить злоумышленнику, что делает ее непригодной для криптографических целей.
Варианты
[ редактировать ]МурмурХэш1
[ редактировать ]Оригинальный MurmurHash был создан как попытка сделать функцию более быстрой, чем Lookup3 . [6] Несмотря на успех, он не был тщательно протестирован и не был способен предоставлять 64-битные хэши, как в Lookup3. У него был довольно элегантный дизайн, который позже был развит в MurmurHash2, сочетая мультипликативный хеш (аналог хеш-функции Фаулера-Нолла-Во ) с Xorshift .
МурмурХэш2
[ редактировать ]МурмурХэш2 [7] дает 32-битное или 64-битное значение. Он существовал в нескольких вариантах, включая те, которые позволяли инкрементное хеширование, а также выровненные или нейтральные версии.
- MurmurHash2 (32-бит, x86) — оригинальная версия; содержит недостаток, который в некоторых случаях ослабляет столкновение. [8]
- MurmurHash2A (32-разрядная версия, x86) — фиксированный вариант, использующий конструкцию Меркла-Дамгорда . Чуть медленнее.
- CMurmurHash2A (32-разрядная версия, x86) — MurmurHash2A, но работает постепенно.
- MurmurHashNeutral2 (32-разрядная версия, x86) — медленнее, но с порядком байтов и нейтральным выравниванием.
- MurmurHashAligned2 (32-разрядная версия, x86) — медленнее, но выполняет выровненное чтение (безопаснее на некоторых платформах).
- MurmurHash64A (64-бит, x64) — исходная 64-битная версия. Оптимизирован для 64-битной арифметики.
- MurmurHash64B (64-бит, x86) — 64-битная версия, оптимизированная для 32-битных платформ. Это не настоящий 64-битный хэш из-за недостаточного смешивания полос. [9]
Человек, который изначально нашел ошибку [ нужны разъяснения ] в MurmurHash2 создана неофициальная 160-битная версия MurmurHash2 под названием MurmurHash2_160. [10]
МурмурХэш3
[ редактировать ]Текущая версия — MurmurHash3, [11] [12] что дает 32-битное или 128-битное хеш-значение. При использовании 128-битной версии версии x86 и x64 не выдают одинаковые значения, поскольку алгоритмы оптимизированы для соответствующих платформ. MurmurHash3 был выпущен вместе с SMHasher — набором тестов для хеш-функций.
Реализации
[ редактировать ]Каноническая реализация находится на C++ , но существуют эффективные порты для множества популярных языков, включая Python . [13] С , [14] Идти , [15] С# , [12] [16] Д , [17] Луа , Перл , [18] Руби , [19] Ржавчина , [20] PHP , [21] [22] Общий Лисп , [23] Хаскелл , [24] Вяз , [25] Клююр , [26] Скала , [27] Ява , [28] [29] Эрланг , [30] Быстрый , [31] Объект Паскаль , [32] Котлин , [33] JavaScript . [34] и OCaml , [35]
Он был принят в ряд проектов с открытым исходным кодом, в первую очередь в libstdc++ (версия 4.6), nginx (версия 1.0.1), [36] рубин , [37] libmemcached ( драйвер C для Memcached ), [38] npm (менеджер пакетов nodejs), [39] страны , [40] Хадуп , [1] Киотский кабинет, [41] Кассандра , [42] [43] Солр , [44] вопал ваббит , [45] Эластичный поиск , [46] Гуава , [47] Кафка [48] и Оптимизатор виртуальных данных RedHat (VDO) . [49]
Уязвимости
[ редактировать ]Хэш-функции могут быть уязвимы для атак коллизий , когда пользователь может выбирать входные данные таким образом, чтобы намеренно вызывать коллизии хэшей. Жан-Филипп Омассон и Дэниел Дж. Бернштейн смогли показать, что даже реализации MurmurHash с использованием рандомизированного начального числа уязвимы для так называемых HashDoS- атак. [50] С помощью дифференциального криптоанализа они смогли генерировать входные данные, которые могли привести к коллизии хэшей. Авторы атаки рекомендуют вместо этого использовать собственный SipHash .
Алгоритм
[ редактировать ]algorithm Murmur3_32 is
// Note: In this version, all arithmetic is performed with unsigned 32-bit integers.
// In the case of overflow, the result is reduced modulo 232.
input: key, len, seed
c1 ← 0xcc9e2d51
c2 ← 0x1b873593
r1 ← 15
r2 ← 13
m ← 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)
// 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)
Ниже приведен пример реализации 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;
}
| Тестовая строка | Начальное значение | Хэш-значение (шестнадцатеричное) | Хэш-значение (десятичное) |
|---|---|---|---|
0x00000000
|
0x00000000
|
0
| |
0x00000001
|
0x514E28B7
|
1,364,076,727
| |
0xffffffff
|
0x81F16F39
|
2,180,083,513
| |
| тест | 0x00000000
|
0xba6bd213
|
3,127,628,307
|
| тест | 0x9747b28c
|
0x704b81dc
|
1,883,996,636
|
| Привет, мир! | 0x00000000
|
0xc0363e43
|
3,224,780,355
|
| Привет, мир! | 0x9747b28c
|
0x24884CBA
|
612,912,314
|
| Быстрая коричневая лиса перепрыгивает через ленивую собаку | 0x00000000
|
0x2e4ff723
|
776,992,547
|
| Быстрая коричневая лиса перепрыгивает через ленивую собаку | 0x9747b28c
|
0x2FA826CD
|
799,549,133
|
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б «Hadoop в Java» . Hbase.apache.org. 24 июля 2011 г. Архивировано из оригинала 12 января 2012 г. Проверено 13 января 2012 г.
- ^ Чоуза и др .
- ^ «Couceiro et al» (PDF) (на португальском языке). п. 14 . Проверено 13 января 2012 г.
- ^ Танджент (tanjent) написал,3 марта 2008 г., 13:31:00. «Первое объявление MurmurHash» . Tanjent.livejournal.com . Проверено 13 января 2012 г.
{{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка ) - ^ «МурмурХэш2-160» . Simonhf.wordpress.com. 25 сентября 2010 г. Проверено 13 января 2012 г.
- ^ «МурмурХэш1» . Проверено 12 января 2019 г.
- ^ «MurmurHash2 на Github» .
- ^ "MurmurHash2Flaw" . Проверено 15 января 2019 г.
- ^ «MurmurHash3 (см. примечание к MurmurHash2_x86_64)» . Проверено 15 января 2019 г.
- ^ "МурмурХэш2_160" . Проверено 12 января 2019 г.
- ^ «MurmurHash3 на Github» .
- ^ Jump up to: а б Хорват, Адам (10 августа 2012 г.). «MurMurHash3, сверхбыстрый алгоритм хеширования для C#/.NET» .
- ^ «pyfasthash в Python» . Проверено 13 января 2012 г.
- ^ «Реализация C в qLibc, автор Сынён Ким» .
- ^ «мурмур3 в Го» .
- ^ Лэндман, Дэви. «Дэви Ландман на C#» . Landman-code.blogspot.com . Проверено 13 января 2012 г.
- ^ «std.digest.murmurhash — язык программирования D» . dlang.org . Проверено 5 ноября 2016 г.
- ^ «Тору Маэсака в Perl» . Metacpan.org . Проверено 13 января 2012 г.
- ^ Юки Курихара (16 октября 2014 г.). "Дайджест::MurmurHash" . GitHub.com . Проверено 18 марта 2015 г.
- ^ "stusmall/murmur3" . Гитхаб . Проверено 29 ноября 2015 г.
- ^ «Реализация MurmurHash3 в пользовательской среде PHP» . github.com . Проверено 18 декабря 2017 г.
- ^ «PHP 8.1 с поддержкой MurmurHash3» .
- ^ "tarballs_are_good/murmurhash3" . Проверено 7 февраля 2015 г.
- ^ «Хаскелл» . Hackage.haskell.org . Проверено 13 января 2012 г.
- ^ «Вяз» . package.elm-lang.org . Проверено 12 июня 2019 г.
- ^ «Murmur3.java в исходном коде Clojure на Github» . Clojure.org . Проверено 11 марта 2014 г.
- ^ «Реализация стандартной библиотеки Scala» . 26 сентября 2014 г.
- ^ Murmur3 , часть Гуавы
- ^ «Классы Java Murmur3A и Murmur3F на Github » зеленый робот Получено 5 ноября.
- ^ "биптелин/мурмерл3" . Гитхаб . Проверено 21 октября 2015 г.
- ^ Дайсуке Т (7 февраля 2019 г.). «МурмурХэш-Свифт» . GitHub.com . Проверено 10 февраля 2019 г.
- ^ GitHub - Xor-el/HashLib4Pascal: хеширование для современного объектного Паскаля
- ^ "goncalossilva/kotlinx-murmurhash" . GitHub.com. 10 декабря 2021 г. Проверено 14 декабря 2021 г.
- ^ Рэйкморган (владелец). «Реализация Javascript Рэем Морганом» . Gist.github.com . Проверено 13 января 2012 г.
- ^ ИНРИА. «Источник OCaml» . GitHub.com.
- ^ «нгинкс» . Проверено 13 января 2012 г.
- ^ «Рубиниус» . Проверено 29 февраля 2012 г.
- ^ «libMemcached» . libmemcached.org . Проверено 21 октября 2015 г.
- ^ «переключиться с MD5 на шум» .
- ^ "мааткит" . 24 марта 2009 года . Проверено 13 января 2012 г.
- ^ «Спецификация Киотского кабинета министров» . Fallabs.com. 4 марта 2011 года . Проверено 13 января 2012 г.
- ^ «Перегородчики» . apache.org. 15 ноября 2013 года . Проверено 19 декабря 2013 г.
- ^ «Введение в Apache Cassandra™ + что нового в версии 4.0, Патрик Макфадин. Представляет DataStax» . Ютуб . 10 апреля 2019 г.
- ^ «Solr MurmurHash2 Javadoc» .
- ^ «hash.cc в исходном коде vowpalwabbit» .
- ^ «Elasticsearch 2.0 — CRUD и изменения маршрутизации» .
- ^ «Хеширование Гуавы.java» .
- ^ «Кафка DefaultPartitioner.java» .
- ^ Virtual Data Optimizer Исходный код
- ^ «Срочный шум: перезагрузка DoS-затопления» .