MurmurHash - Википедия - MurmurHash

MurmurHash не-криптографический хэш-функция подходит для общего поиска по хешам.[1] Он был создан Остином Эпплби в 2008 году.[2] и в настоящее время размещен на GitHub вместе с его набором тестов под названием «SMHasher». Он также существует в нескольких вариантах,[3] все они были переданы в общественное достояние. Название происходит от двух основных операций, умножения (MU) и вращения (R), используемых во внутреннем цикле.

В отличие от криптографические хеш-функции, он не предназначен специально для того, чтобы его было сложно отменить злоумышленником, что делает его непригодным для криптографических целей.

Варианты

MurmurHash3

Текущая версия - MurmurHash3,[4][5] что дает 32-битное или 128-битное хеш-значение. При использовании 128-битных версий x86 и x64 не дают одинаковых значений, поскольку алгоритмы оптимизированы для их соответствующих платформ. MurmurHash3 был выпущен вместе с SMHasher - набором тестов хэш-функций.

MurmurHash2

MurmurHash2[6] дает 32-битное или 64-битное значение. Он был представлен в нескольких вариантах, в том числе с возможностью инкрементного хеширования и выровненных или нейтральных версий.

  • MurmurHash2 (32-бит, x86) - Оригинальная версия; содержит дефект, который в некоторых случаях снижает вероятность столкновения.[7]
  • MurmurHash2A (32-бит, x86) - фиксированный вариант с использованием Строительство Меркле-Дамгарда. Чуть медленнее.
  • CMurmurHash2A (32-разрядная версия, x86) - MurmurHash2A, но работает постепенно.
  • MurmurHashNeutral2 (32-бит, x86) - медленнее, но с порядком байтов и выравниванием.
  • MurmurHashAligned2 (32-разрядная версия, x86) - медленнее, но выполняет выровненное чтение (безопаснее на некоторых платформах).
  • MurmurHash64A (64-бит, x64) - Исходная 64-битная версия. Оптимизирован для 64-битной арифметики.
  • MurmurHash64B (64-бит, x86) - 64-битная версия, оптимизированная для 32-битных платформ. Это не настоящий 64-битный хеш из-за недостаточного смешивания полос.[8]

Человек, первоначально обнаруживший уязвимость в MurmurHash2, создал неофициальную 160-битную версию MurmurHash2 под названием MurmurHash2_160.[9]

MurmurHash1

Оригинальный MurmurHash был создан как попытка сделать функцию более быстрой, чем Lookup3.[10] Несмотря на успех, он не был тщательно протестирован и не мог предоставить 64-битные хэши, как в Lookup3. Он имел довольно элегантный дизайн, который позже будет построен в MurmurHash2, объединяя мультипликативный хеш (аналогичный Хэш-функция Фаулера – Нолла – Во ) с Xorshift.

Реализации

Каноническая реализация находится в C ++, но есть эффективные порты для множества популярных языков, включая Python,[11] C,[12] Идти,[13] C #,[5][14] D,[15] Lua, Perl,[16] Рубин,[17] Ржавчина,[18] PHP[19][20], Common Lisp,[21] Haskell,[22] Вяз,[23] Clojure,[24] Scala,[25] Ява,[26][27] Erlang,[28] Быстрый,[29] и JavaScript,[30][31] вместе с онлайн-версией.[32]

Он был принят в ряд проектов с открытым исходным кодом, в первую очередь libstdc ++ (версия 4.6), nginx (версия 1.0.1),[33] Рубиниус,[34] libmemcached ( C драйвер для Memcached ),[35] npm (менеджер пакетов nodejs),[36] мааткит,[37] Hadoop,[1] Киотский кабинет,[38] RaptorDB,[39] ОлегДБ,[40] Кассандра,[41] Solr,[42] vowpal wabbit,[43] Elasticsearch,[44] Гуава,[45] Кафка[46] и RedHat Virtual Data Optimizer (VDO).[47]

Уязвимости

Хеш-функции могут быть уязвимы для атак, если пользователь может выбрать входные данные таким образом, чтобы намеренно вызвать коллизии хешей. Жан-Филипп Аумассон и Дэниел Дж. Бернштейн смогли показать, что даже реализации MurmurHash с использованием рандомизированного начального числа уязвимы для так называемых атак HashDoS.[48] С использованием дифференциальный криптоанализ они могли генерировать входные данные, которые приводили к конфликту хешей. Авторы атаки рекомендуют использовать собственные SipHash вместо.

Алгоритм

алгоритм Шепот 3_32 является    // Примечание: в этой версии вся арифметика выполняется с 32-битными целыми числами без знака.    // В случае переполнения результат уменьшается по модулю 232.    Вход: ключ, len, семя        c1 ← 0xcc9e2d51 c2 ← 0x1b873593 r1 ← 15 r2 ← 13 m ← 5 n ← 0xe6546b64 hash ← семя    для каждого fourByteChunk из ключ делать        k ← fourByteChunk k ← k × c1 k ← k ROL r1 k ← k × c2 hash ← hash XOR k hash ← hash ROL r2 hash ← (hash × m) + n с любым оставшийсяBytesInKey делать        ОстающийсяБайт ← SwapToLittleEndian (ОстающийсяБайтесинкэй) // Примечание: обратный порядок байтов необходим только на машинах с прямым порядком байтов.        // Цель состоит в том, чтобы разместить значимые цифры ближе к нижнему краю значения,        // чтобы эти цифры имели наибольший потенциал повлиять на цифры нижнего диапазона        // в последующем умножении. Учтите, что поиск значимых цифр        // в высоком диапазоне будут иметь больший эффект на старшие цифры        // умножение и, в частности, то, что такие высокие цифры могут быть отброшены        // по арифметическому модулю при переполнении. Мы этого не хотим.                оставшиеся байты ← оставшиеся байты × c1 оставшиеся байты ← оставшиеся байты ROL r1 оставшиеся байты ← оставшиеся байты × c2 хэш ← хэш XOR оставшийся хэш байтов ← хэш XOR len    hash ← hash XOR (hash >> 16) hash ← hash × 0x85ebca6b hash ← hash XOR (hash >> 13) hash ← hash × 0xc2b2ae35 hash ← hash XOR (hash >> 16) хеш

Ниже приводится пример реализации C (для процессоров с прямым порядком байтов):

статический в соответствии uint32_t murmur_32_scramble(uint32_t k) {    k *= 0xcc9e2d51;    k = (k << 15) | (k >> 17);    k *= 0x1b873593;    возвращаться k;}uint32_t murmur3_32(const uint8_t* ключ, size_t len, uint32_t семя){	uint32_t час = семя;    uint32_t k;    / * Читаем группами по 4. * /    за (size_t я = len >> 2; я; я--) {        // Вот источник разных результатов в зависимости от порядка байтов.        // Однако своп здесь не влияет на хэш-свойства.        memcpy(&k, ключ, размер(uint32_t));        ключ += размер(uint32_t);        час ^= murmur_32_scramble(k);        час = (час << 13) | (час >> 19);        час = час * 5 + 0xe6546b64;    }    / * Прочитать остальное. * /    k = 0;    за (size_t я = len & 3; я; я--) {        k <<= 8;        k |= ключ[я - 1];    }    // Обмен здесь * не * необходим, потому что предыдущий цикл уже    // помещает младшие байты в младшие в соответствии с порядком байтов    // мы используем. Свопы применяются только тогда, когда память копируется в блоке.    час ^= murmur_32_scramble(k);    / * Завершить. * /	час ^= len;	час ^= час >> 16;	час *= 0x85ebca6b;	час ^= час >> 13;	час *= 0xc2b2ae35;	час ^= час >> 16;	возвращаться час;}

Смотрите также

Рекомендации

  1. ^ а б «Hadoop на Java». Hbase.apache.org. 24 июля 2011. Архивировано с оригинал 12 января 2012 г.. Получено 13 января 2012.
  2. ^ Tanjent (tanjent) написал, 3 марта 2008 г. 13:31:00. "Первое объявление MurmurHash". Tanjent.livejournal.com. Получено 13 января 2012.
  3. ^ «МурмурХаш2-160». Simonhf.wordpress.com. 25 сентября 2010 г.. Получено 13 января 2012.
  4. ^ "MurmurHash3 на Github".
  5. ^ а б Хорват, Адам (10 августа 2012 г.). "MurMurHash3, сверхбыстрый алгоритм хеширования для C # / .NET".
  6. ^ "MurmurHash2 на Github".
  7. ^ "MurmurHash2Flaw". Получено 15 января 2019.
  8. ^ "MurmurHash3 (см. Примечание к MurmurHash2_x86_64)". Получено 15 января 2019.
  9. ^ "MurmurHash2_160". Получено 12 января 2019.
  10. ^ "MurmurHash1". Получено 12 января 2019.
  11. ^ "pyfasthash в Python". Google. Получено 13 января 2012.
  12. ^ «Реализация C в qLibc, автор - Сынён Ким».
  13. ^ "murmur3 in Go".
  14. ^ Ландман, Дэви. «Дэви Лэндман на C #». Landman-code.blogspot.com. Получено 13 января 2012.
  15. ^ "std.digest.murmurhash - язык программирования D". dlang.org. Получено 5 ноября 2016.
  16. ^ "Тору Маэсака на Perl". metacpan.org. Получено 13 января 2012.
  17. ^ Юки Курихара (16 октября 2014 г.). "Дайджест :: MurmurHash". GitHub.com. Получено 18 марта 2015.
  18. ^ "stusmall / murmur3". GitHub. Получено 29 ноябрь 2015.
  19. ^ "Реализация MurmurHash3 в пользовательском пространстве PHP". github.com. Получено 18 декабря 2017.
  20. ^ «PHP 8.1 с поддержкой MurmurHash3».
  21. ^ "tarballs_are_good / murmurhash3". Получено 7 февраля 2015.
  22. ^ "Haskell". Hackage.haskell.org. Получено 13 января 2012.
  23. ^ "Вяз". package.elm-lang.org. Получено 12 июн 2019.
  24. ^ "Murmur3.java в исходном коде Clojure на Github". clojure.org. Получено 11 марта 2014.
  25. ^ «Реализация стандартной библиотеки Scala». 26 сентября 2014 г.
  26. ^ Мурмур3, часть Гуавы
  27. ^ "Java-классы Murmur3A и Murmur3F на Github". зеленый робот. Получено 5 ноября 2014.
  28. ^ "биптелин / мурмер13". GitHub. Получено 21 октября 2015.
  29. ^ Дайсуке Т. (7 февраля 2019 г.). "MurmurHash-Swift". GitHub.com. Получено 10 февраля 2019.
  30. ^ райсморган (владелец). «Реализация Javascript Рэем Морганом». Gist.github.com. Получено 13 января 2012.
  31. ^ Гэрикур. "MurmurHash.js на Github". Github.com. Получено 13 января 2012.
  32. ^ «Онлайн-версия MurmurHash». shorelabs.com. Получено 12 августа 2014.
  33. ^ "nginx". Получено 13 января 2012.
  34. ^ «Рубиниус». Получено 29 февраля 2012.
  35. ^ "libMemcached". libmemcached.org. Получено 21 октября 2015.
  36. ^ "переключиться с MD5 на бормотание".
  37. ^ "мааткит". Google. 24 марта 2009 г.. Получено 13 января 2012.
  38. ^ «Спецификация Киотского кабинета». Fallabs.com. 4 марта 2011 г.. Получено 13 января 2012.
  39. ^ Голам, Мехди (13 ноября 2011 г.). "Страница RaptorDB CodeProject". Codeproject.com. Получено 13 января 2012.
  40. ^ "Документация OlegDB". Получено 24 января 2013.
  41. ^ «Перегородки». apache.org. 15 ноября 2013 г.. Получено 19 декабря 2013.
  42. ^ "Solr MurmurHash2 Javadoc".
  43. ^ "hash.cc в исходном коде vowpalwabbit".
  44. ^ «Elasticsearch 2.0 - CRUD и изменения маршрутизации».
  45. ^ "Guava Hashing.java".
  46. ^ "Kafka DefaultPartitioner.java".
  47. ^ Оптимизатор виртуальных данных исходный код
  48. ^ "Breaking Murmur: Hash-flooding DoS Reloaded".

внешняя ссылка