Primary tabs

HighwayHash: быстрое хеширование со скоростью более 10 ГБ / с

Ссылка на оригинал - https://blog.minio.io/highwayhash-fast-hashing-at-over-10-gb-s-per-core-in-golan…, автор публикации - Frank Wessels

Введение

HighwayHash - это новая и очень быстрая псевдослучайная функция (PRF), разработанная Юрки Алакуйялой, Биллом Коксом и Яном Вассенбергом из исследования Google. Алгоритм принимает 256-битный ключ и вычисляет 64-, 128- или 256-битные значения хеш-функции данных сообщений.

HighwayHash может использоваться для предотвращения хеш-атак и аутентификации недолговечных сообщений. Кроме того, он может использоваться как функция снятия отпечатков пальцев. Обратите внимание, что HighwayHash не является криптографической хэш-функцией общего назначения (такой как Blake2b, SHA-3 или SHA-2) и не должна использоваться, если требуется сильное сопротивление столкновению.

В Minio мы разработали собственный репозиторий Golang для HighwayHash с оптимизированными реализациями сборки для платформ Intel и ARM. Мы переключим защиту от гниения, которая в настоящее время использует алгоритм Blake2b, на HighwayHash.

Высокая производительность: в 10 раз быстрее

HighwayHash - это примерно в 5 раз более быстрая хеш-функция SIMD по сравнению с SipHash, которая сама по себе является быстрой и «криптографической стойкой» псевдослучайной функцией, разработанной Аумассоном и Бернштейном.

HighwayHash использует новый способ смешивания входов с инструкциями Intel AVX2 для умножения и перестановки для достижения своей производительности. Умножения являются 32x32-битными, что дает результаты в 64-битной ширине, и поэтому их невозможно инвертировать. Дополнительно перестановка выравнивает распределение результирующих байтов.

На процессоре Skylake (3,0 ГГц Xeon Platinum 8124M) в таблице ниже показано, как HighwayHash сравнивается с другими методами хеширования для сообщений объемом 5 МБ (производительность одного ядра, все реализации Golang, см. Тест производительности ).

BenchmarkHighwayHash 11986,98 МБ / с 
BenchmarkSHA256_AVX512 3552,74 МБ / с 
BenchmarkBlake2b 972,38 МБ / с 
BenchmarkSHA1 950,64 МБ / с 
BenchmarkMD5 684,18 МБ / с 
BenchmarkSHA512 562,04 МБ / с 
BenchmarkSHA66

Примечание: AVX512-версия SHA256 использует технологию многобуферной криптографической библиотеки , разработанную Intel, более подробную информацию можно найти в sha256-simd .

Таким образом, легко видеть, что HighwayHash более чем в 10 раз быстрее по сравнению с Blake2b, который сам по себе в 2–3 раза быстрее, чем, например. SHA512 или SHA256.

Выступление на ARM

Приведенные выше показатели производительности относятся к процессорам Intel, а также к процессорам ARM. HighwayHash работает хорошо и даже превосходит аппаратно-ускоренный алгоритм SHA256 на 50%. На процессоре ARM Cortex-A53 с тактовой частотой 1,2 ГГц он может превышать скорость более 1 ГБ / с для одного ядра.

Стабильность

По состоянию на январь 2018 года все три выходных размера HighwayHash были объявлены стабильными . Это означает, что результаты хеширования для любого данного входного сообщения гарантированно не изменятся.

Качественное сравнение

Мы провели «качественную» оценку того, как HighwayHash сравнивается с другими Blake2b с точки зрения распределения контрольных сумм для различного количества сообщений. Это показывает, что HighwayHash ведет себя аналогично согласно следующему графику:

Более подробную информацию о том, как это сравнение было достигнуто, можно найти в HashCompare .

Масштабирование по ядрам

В качестве последнего теста мы проанализировали, как HighwayHash масштабируется на несколько ядер (на том же 16-ядерном процессоре Skylake, как указано выше, но с большим размером сообщения 10 МБ):

BenchmarkWrite_1024K_1Core 8241,5 МБ / с 
BenchmarkWrite_1024K_2Core 15397,9 МБ / с 
BenchmarkWrite_1024K_4Core 29715,8 МБ / с 
BenchmarkWrite_1024K_8Core 55177,7 МБ / с 
Бенчмарк Write_1024K / 
12Core 7,666,616 S16 659,69

Это показывает, что HighwayHash хорошо масштабируется, поскольку он работает на большем количестве ядер и может дать еще 10-кратное улучшение скорости при работе порядка 16 ядер.

Завершение

Пожалуйста, зайдите на GitHub для репозитория HighwayHash и протестируйте его для себя.

Мы будем рады любым отзывам и / или предложениям по улучшению.

Не нашли ответ на свой вопрос? Возможно, вы найдете решение проблемы на нашем канале в Youtube! Здесь мы собрали небольшие, но эффективные инструкции. Смотрите и подписывайтесь на наш youtube-канал!

Смотреть на Youtube