Хэш-функция Дженкинса
Хэш -функции Дженкинса — это семейство некриптографических хэш-функций для многобайтовых ключей , разработанное Бобом Дженкинсом . Первый из них был официально опубликован в 1997 году.
Хэш-функции
[ редактировать ]один_в_время
[ редактировать ]Хэш Дженкинса one_at_a_time адаптирован здесь со страницы WWW Боба Дженкинса, [1] это расширенная версия статьи доктора Добба . [2] Первоначально он был создан для выполнения определенных требований, описанных криптографом Колином Пламбом, но в конечном итоге не был использован. [1]
uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
size_t i = 0;
uint32_t hash = 0;
while (i != length) {
hash += key[i++];
hash += hash << 10;
hash ^= hash >> 6;
}
hash += hash << 3;
hash ^= hash >> 11;
hash += hash << 15;
return hash;
}
Примеры хеш-значений для хеш-функции one_at_a_time .
one_at_a_time("a", 1)
0xca2e9442
one_at_a_time("The quick brown fox jumps over the lazy dog", 43)
0x519e91f5
Лавинное поведение этого хеша показано справа.
Каждая из 24 строк соответствует одному биту 3-байтового входного ключа, а каждый из 32 столбцов соответствует биту выходного хэша. Цвета выбираются в зависимости от того, насколько хорошо входной ключевой бит влияет на данный выходной хэш-бит: зеленый квадрат указывает на хорошее поведение смешивания, желтый квадрат указывает на слабое поведение смешивания, а красный означает отсутствие смешивания. Лишь несколько битов в последнем байте входного ключа слабо смешиваются с меньшинством битов выходного хэша.
Стандартные реализации языка программирования Perl до версии 5.28 включали поочередный хэш Дженкинса или его усиленный вариант, который использовался по умолчанию. [3] [4]
поиск2
[ редактировать ]Функция Lookup2 была временным преемником функции «по одному». Это функция, названная «My Hash» в журнальной статье доктора Доббса 1997 года, хотя она устарела из-за последующих функций, выпущенных Дженкинсом. Приложения этой хэш-функции можно найти в:
- средство проверки модели SPIN для вероятностного обнаружения ошибок. В статье об этой программе исследователи Диллинджер и Манолиос отмечают, что Lookup2 является «популярным выбором среди разработчиков хеш-таблиц и фильтров Блума ». Они изучают поиск2 и его простое расширение, которое выдает 96-битные, а не 32-битные хэш-значения. [5]
- Компонент брандмауэра Netfilter в Linux , [6] где она заменила более раннюю хеш-функцию, которая была слишком чувствительна к коллизиям. Однако было показано, что полученная система по-прежнему чувствительна к атакам с переполнением хеша , даже если хеш Дженкинса рандомизируется с использованием секретного ключа. [7]
- Программа, которая решила игру в калах, использовала хэш-функцию Дженкинса вместо метода хеширования Зобриста, который чаще используется для решения задач такого типа; Причинами этого выбора была скорость работы функции Дженкинса на небольших представлениях досок кала, а также тот факт, что основное правило кала может радикально изменить доску, сводя на нет преимущества инкрементального вычисления хэш-функций Зобриста. [8]
поиск3
[ редактировать ]Функция Lookup3 принимает входные данные частями по 12 байт (96 бит). [9] Это может быть уместно, когда скорость важнее простоты. Однако обратите внимание, что любое повышение скорости за счет использования этого хэша, вероятно, будет полезно только для больших ключей, и что повышенная сложность может также иметь последствия для скорости, такие как предотвращение встраивания хэш-функции оптимизирующим компилятором.
Функция Lookup3 была включена в Hierarchical Data Format 5 в качестве контрольной суммы для внутренних структур данных на основе ее относительной силы и скорости по сравнению с CRC32 и Fletcher32 . [10]
SpookyHash
[ редактировать ]В 2011 году Дженкинс выпустил новую 128-битную хеш-функцию под названием SpookyHash. [11] SpookyHash значительно быстрее, чем поиск3.
Пример для версии 2 (с прямым порядком байтов x64):
Короткий метод для размера менее 192 байт (43 байта):
Hash128("The quick brown fox jumps over the lazy dog")
2b12e846aa0693c71d367e742407341b
Стандартный метод для более 191 байта (219 байт):
Hash128("The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog")
f1b71c6ac5af39e7b69363a60dd29c49
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б Дженкинс, Боб (3 ноября 2013 г.). «Хеш-функция для поиска в хэш-таблице» . Проверено 9 февраля 2018 г.
- ^ Дженкинс, Боб (сентябрь 1997 г.). «Хеш-функции» . Доктор Журнал Добба .
- ^ "RFC: perlfeaturedelta" : «алгоритм поочередного хеширования… [добавлен в версии] 5.8.0»
- ^ "perl: hv_func.h"
- ^ Диллинджер, Питер К.; Манолиос, Панайотис (2004). Быстрая и точная проверка битового состояния для SPIN . Учеб. 11-й Международный семинар СПИН. стр. 57–75. CiteSeerX 10.1.1.4.6765 .
- ^ Нейра Аюсо, Пабло (2006). «Система отслеживания соединений Netfilter» (PDF) . ;авторизоваться: . 31 (3).
- ^ Бар-Йосеф, Ноа; Шерсть, Авишай (2007). Удаленные алгоритмические атаки на рандомизированные хеш-таблицы. Учеб. Международная конференция по безопасности и криптографии (SECRYPT) (PDF) . стр. 117–124.
- ^ Ирвинг, Джеффри; Донкерс, Йерун; Уитервейк, Йос. «Решение кала» (PDF) . Журнал ICGA .
- ^ Дженкинс, Боб. «исходный код Lookup3.c» . Проверено 16 апреля 2009 г.
- ^ Козиол, Куинси. «[svn-r12661] Описание: · HDFGroup/hdf5@d3a12e1» . Проверено 18 июля 2023 г.
- ^ Дженкинс, Боб. «SpookyHash: 128-битный некриптографический хеш» . Проверено 29 января 2012 г.