Max Home IndustryХорошо, хэш-функция может и не быть огромной частью программного обеспечения, но когда вы знаете, как трудно найти хорошую хэш-функцию, имеющую еще три открытых источника, следует приветствовать.
Первый-это параллельная реализация SipHash, быстрой криптографически сильной псевдослучайной функции. Версия Google выдает тот же результат, что и стандартный SipHash, но в 1,5 раза быстрее из-за использования инструкций AVX-2. Инструкции AVX работают со 128-битными векторами. SipHash важен, потому что он используется для реализации хэш-таблиц во многих современных языках, например Python, Haskell, Ruby и Rust. Он также используется в системных пакетах, таких как systemd и OpenDNS. Дело в том, что хэш-функции есть везде.
Быстрые случайные хэш-функции необходимы в серверах и языковых реализациях из-за возможности атак с хэш-флудом. Хэш — таблица работает быстро, если в таблице достаточно места и хэш-функция хорошая. Однако, если вы представляете хэш-таблицу со списком данных, которые все имеют один и тот же хэш, то все они должны храниться в одном и том же месте, и каждое обновление после первого является более дорогостоящим. Это может быть настолько дорогостоящим, что приведет к остановке сервера.
Если вы считаете, что это маловероятно, то в 2011 году атака на PHP-сервер с 500 КБ тщательно построенных почтовых данных заняла минуту процессорного времени. Решение состоит в том, чтобы использовать случайную хэш-функцию, которая может быть настроена так, чтобы каждый раз, когда она используется для одних и тех же данных, давать другой набор хэш-значений, например, SipHash.
SipTreeHash является вариантом SipHash и не дает одинаковых результатов. Он работает, разрезая входные данные на 8-байтовые куски и параллельно вычисляет сифаш на каждом куске, снова используя инструкции AVX-2, а затем объединяет результат, используя окончательный сифаш. Единственная проблема заключается в том, что инструкции AVX-2 доступны только на процессорах Intel Haswell и более поздних версиях или на скоро выпущенных процессорах AMD.
Поскольку при выполнении фрагментации возникают накладные расходы, это происходит быстрее, чем SipHash, только если размер входных данных превышает 96 байт. Для достаточно больших входных данных SipTreeHash работает в три раза быстрее, чем SipHash.
Последняя новая хэш — функция-HighwayHash-откуда они берут имена? В этом случае хэш-функция является совершенно новой и предназначена для наилучшего использования инструкций умножения и перестановки AVX-2. Основная идея заключается в том, что используемые 32×32-битные умножения дают 64-битные результаты, и поэтому их нелегко отменить, а перестановки выравнивают распределение байтов. Выигрыш заключается в том, что он в два-три раза быстрее, чем SipTreeHash, и, следовательно, в шесть раз быстрее, чем SipHash.
Большая проблема заключается в том, что эта новая хэш-функция недостаточно изучена, и это одна из причин открытого поиска кода. Предполагается, что HighwayHash будет проверен и доказан криптографически сильным.
Код доступен на GitHub, и, как и следовало ожидать, все это на C++ и выполняется с использованием GCC.