Быстрая хеш-функция HighwayHash и развитие SipHash от Google
Компания Google представила три новые реализации хеш-функций: быстрая реализация SipHash-AVX2, модификация SipTreeHash и полностью новая хеш-функция HighwayHash. Одно из основных предназначений хеш-функций этой категории - противостояние атакам типа hashDoS (трата чрезмерных ресурсов при обработке значений, вызывающих коллизии). Реализации написаны на языке C++ с использованием intrinsics для обеспечения распараллеливания обработки данных с использованием инструкций AVX2. Код хеш-функций открыт под лицензией Apache 2.0.
Реализация SipHash-AVX2 полностью совместима на уровне выдаваемых значений с оригинальной SipHash, но в полтора раза быстрее ранее доступного варианта, оптимизированного с использованием инструкций SSE4.1. Модификация SipTreeHash, кроме инструкций AVX2, использует хеширование на основе деревьев j-lanes, позволяющих одновременно в несколько параллельных потоков обрабатывать входные данные (ввод разбивается на 8-байтовые пакеты, которые обрабатываются параллельно). SipTreeHash в три раза быстрее исходного SipHash, за исключением случаев с расчётом хешей для мелких наборов данных (на данных менее 96 байтов SipTreeHash медленнее SipHash).
В хеш-функции HighwayHash применяется новый метод смешивания входных данных, используя минимум AVX-2 инструкций умножения и переставления. По мнению инженеров Google, получившаяся хеш-функция является криптографически надёжной, но для подтверждения стойкости требуется проверка при помощи новых методов криптоанализа. При обработке больших входных данных эффективность HighwayHash достигает 0.3 процессорных такта на байт, но и на небольших данных HighwayHash также остаётся эффективнее SipHash. Например, при обработке блоков в 1 KiB HighwayHash в семь раз быстрее исходного SipHash, а пропускная способность на CPU Xeon E5-1650 v3 3.5 GHz составляет 11.3 GB/s (SipHash - 1.7 GB/s, SipTreeHash - 4.8 GB/s).
Дополнение: Появилась реализация SipHash-AVX2 на языке C (вместо C++) от мейнтейнера libsodium.