Исходное сообщение
"Быстрая хеш-функция HighwayHash и развитие SipHash от Google" Отправлено opennews, 03-Мрт-16 13:07
Компания Google представила (http://google-opensource.blogspot.com/2016/03/new-algorithms... три новые реализации хеш-функций: новая быстрая реализация SipHash-AVX2 (https://en.wikipedia.org/wiki/SipHash), быстрая криптографически стойкая псевдослучайная функция (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.7957) SipTreeHash и полностью новая хэш-функция HighwayHash (https://github.com/google/highwayhash/). Хэш-функции написаны на языке C++ с использованием intrinsics (https://en.wikipedia.org/wiki/Intrinsic_function) для обеспечения распараллеливания обработки данных с использованием инструкций AVX-2 и изначально рассчитаны на противостояние атакам  типа hashDoS (https://www.opennet.ru/opennews/art.shtml?num=32698) (трата чрезмерных ресурсов при обработке значений, вызывающих коллизии). Код хэш-функций открыт (https://github.com/google/highwayhash/) под лицензией Apache 2.0. Реализация SipHash-AVX2 полностью совместима на уровне выдаваемых значений с оригинальным SipHash, но в 1.5 раза быстрее, чем ранее доступный вариант, оптимизированный с использованием инструкций SSE4.1. Модификация SipTreeHash, кроме инструкций AVX2, использует хэширование на основе деревьев j-lanes, позволяющих одновременно в несколько параллельных потоков обрабатывать входные данные (ввод разбивается на 8-байтовые пакеты, которые обрабатываются параллельно). SipTreeHash в 3 раза быстрее чем исходный  SipHash, за исключением случаев с расчётом хэшей для мелких наборов данных (на данных, меньше 96 байт, SipTreeHash медленнее SipHash). В хэш-функции HighwayHash применяется новый метод смешивания входных данных, используя минимум AVX-2 инструкций умножения и переставления.  По мнению инженеров Google получившаяся хэш-функция является криптографически надёжной, но для полного подтверждения стойкости возможно требуется проверка при помощи дополнительных новых методов криптоанализа. При обработке больших входных данных эффективность HighwayHash достигает 0.3 процессорных цикла на байт, но и на небольших данных HighwayHash также остаётся эффективнее SipHash. Например, при обработке блоков в 1 KiB HighwayHash в 7 раз быстрее чем исходный SipHash и составляет на CPU Xeon E5-1650 v3 3.5 GHz - 11.3 GB/s (SipHash - 1.7 GB/s, SipTreeHash - 4.8 GB/s). URL: http://www.metzdowd.com/pipermail/cryptography/2016-March/02... Новость: http://www.opennet.ru/opennews/art.shtml?num=43979