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

1 Что нужно восстановить?

Видео

MP4, AVI и HD видео хранятся на телефоне и / или по ошибке удаляются вместе с фотографиями и другими медиафайлами.

Контакты

Номера телефонов друзей и знакомых из приложения «Контакты Android», журналы вызовов; Восстановление SIM-карты.

Фото

Удалены файлы JPG / PNG из Галереи Android; фото, загруженные на мобильный, файлы повреждены после восстановления.

Смс и сообщения

Чаты WhatsApp и Facebook, текстовые сообщения в соцсетях, информация на сим-карте

2 Где пропали файлы?

На sd-карте

Фотографии и документы хранятся на SD-картах. Часто на них случайно удаляются файлы

На телефоне

Программы для восстановления не распознают внутреннее хранилище телефона как диск, но есть другие решения.

На USB флешке

Эти небольшие устройства хранения данных часто выходят из строя или на них появляются ошибки чтения.

На HDD или SSD

Несмотря на то, что настольные платформы становятся все менее популярными, проблема потери файлов всегда оставалась.