Хеш-функция Дженкинса - Jenkins hash function

В Хеш-функции Дженкинса представляют собой набор (не-криптографический ) хэш-функции для мульти-байт ключи, разработанные Боб Дженкинс. Первый был официально опубликован в 1997 году.

Хеш-функции

один за раз

Дженкинса один за раз хэш адаптирован здесь из WWW-страницы Боба Дженкинса,[1] который является расширенной версией его Доктора Добба статья.[2] Первоначально он был создан для выполнения определенных требований, описанных криптографом Колином Пламбом, но в конечном итоге не был использован.[1]

uint32_t jenkins_one_at_a_time_hash(const uint8_t* ключ, size_t длина) {  size_t я = 0;  uint32_t хэш = 0;  пока (я != длина) {    хэш += ключ[я++];    хэш += хэш << 10;    хэш ^= хэш >> 6;  }  хэш += хэш << 3;  хэш ^= хэш >> 11;  хэш += хэш << 15;  возвращаться хэш;}

Примеры хеш-значений для один за раз хеш-функция.

один за раз("а", 1)0xca2e9442один за раз("Быстрая коричневая лиса прыгает через ленивую собаку", 43)0x519e91f5
Лавинное поведение Jenkins Однократное хеширование по 3-байтовым ключам

В лавина поведение этого хеша показано справа.

Каждая из 24 строк соответствует одному биту в 3-байтовом ключе ввода, а каждый из 32 столбцов соответствует одному биту в выходном хеш-коде. Цвета выбираются в зависимости от того, насколько хорошо бит входного ключа влияет на данный выходной хэш-бит: зеленый квадрат указывает на хорошее поведение микширования, желтый квадрат - слабое поведение микширования, а красный означает отсутствие микширования. Только несколько битов в последнем байте входного ключа слабо смешаны с меньшим количеством битов в выходном хэше.

Стандартные реализации Perl язык программирования до версии 5.28 включал хеш-код Jenkins по одному или его усиленный вариант, который использовался по умолчанию.[3][4]

lookup2

В lookup2 функция была временным преемником по одному. Это функция, названная «Мой хэш» в статье журнала доктора Доббса 1997 года, хотя она была устарела в последующих функциях, выпущенных Дженкинсом. Приложения этой хеш-функции находятся в:

  • то Проверка модели SPIN, для вероятностного обнаружения ошибок. В статье об этой программе исследователи Диллинджер и Манолиос отмечают, что lookup2 - «популярный выбор среди разработчиков хеш-таблиц и Фильтры Блума ". Они изучают lookup2 и его простое расширение, которое производит 96-битные, а не 32-битные хеш-значения.[5]
  • В Netfilter компонент брандмауэра Linux,[6] где он заменил более раннюю хеш-функцию, которая была слишком чувствительна к коллизиям. Однако оказалось, что полученная система все еще чувствительна к хеш-флуд атаки, даже если хеш Jenkins рандомизирован с использованием секретного ключа.[7]
  • Программа, решившая игру калах использовал хеш-функцию Jenkins вместо Зобристское хеширование техника, более часто используемая для этого типа проблем; Причины этого выбора заключались в скорости работы функции Дженкинса на небольших представлениях досок кала, а также в том факте, что основное правило калы может радикально изменить доску, сводя на нет преимущества инкрементального вычисления хэш-функций Зобристом.[8]

поиск3

В поиск3 функция потребляет ввод в виде блоков по 12 байт (96 бит).[9] Это может быть уместно, когда скорость важнее простоты. Однако обратите внимание, что любое улучшение скорости от использования этого хэша, вероятно, будет полезно только для больших ключей, и что повышенная сложность также может иметь последствия для скорости, такие как предотвращение встраивания хеш-функции оптимизирующим компилятором.

SpookyHash

В 2011 году Дженкинс выпустил новую 128-битную хеш-функцию под названием SpookyHash.[10] SpookyHash значительно быстрее, чем lookup3.

Пример для V2 (little-endian x64):

Короткий метод для менее 192 байтов (43 байта):

   Hash128 («Быстрая коричневая лиса перепрыгивает через ленивого пса») 2b12e846aa0693c71d367e742407341b

Стандартный метод для более 191 байта (219 байтов):

   Hash128 («Быстрая коричневая лиса перепрыгивает через ленивую собаку Быстрая коричневая лиса перепрыгивает через ленивую собаку Быстрая коричневая лисица перепрыгивает через ленивую собаку Быстрая коричневая лиса перепрыгивает через ленивую собаку Быстрая коричневая лиса перепрыгивает через ленивую собаку») f1b71c6ac5af39e7b69363a60dd29c49

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

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

  1. ^ а б Дженкинс, Боб (3 ноября 2013 г.). «Хеш-функция для поиска в хеш-таблице». Получено 9 февраля, 2018.
  2. ^ Дженкинс, Боб (сентябрь 1997 г.). «Хеш-функции». Журнал доктора Добба.
  3. ^ "RFC: perlfeaturedelta": "алгоритм одноразового хеширования ... [добавлен в версии] 5.8.0"
  4. ^ "perl: hv_func.h"
  5. ^ Диллинджер, Питер С .; Манолиос, Панайотис (2004). Быстрая и точная проверка состояния битов для SPIN. Proc. 11-й Международный семинар SPIN. С. 57–75. CiteSeerX  10.1.1.4.6765.
  6. ^ Нейра Аюсо, Пабло (2006). «Система отслеживания соединений Netfilter» (PDF). ;авторизоваться:. 31 (3).
  7. ^ Бар-Йосеф, Ноа; Шерсть, Авишай (2007). Удаленные атаки алгоритмической сложности на рандомизированные хэш-таблицы Proc. Международная конференция по безопасности и криптографии (SECRYPT) (PDF). С. 117–124.
  8. ^ Ирвинг, Джеффри; Донкерс, Джерун; Uiterwijk, Jos. "Решение калах" (PDF). Журнал ICGA.
  9. ^ Дженкинс, Боб. "исходный код lookup3.c". Получено 16 апреля, 2009.
  10. ^ Дженкинс, Боб. «SpookyHash: 128-битный некриптографический хеш». Получено 29 января, 2012.