Вступление

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 MB/s
BenchmarkSHA256_AVX512    	    	 3552.74 MB/s
BenchmarkBlake2b          	    	  972.38 MB/s
BenchmarkSHA1             	    	  950.64 MB/s
BenchmarkMD5              	    	  684.18 MB/s
BenchmarkSHA512           	    	  562.04 MB/s
BenchmarkSHA256           	    	  383.07 MB/s

Примечание: версия SHA256 для AVX512 использует технику многобуферной криптографической библиотеки, разработанную 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 MB/s
BenchmarkWrite_1024K_2Cores            15397.9 MB/s
BenchmarkWrite_1024K_4Cores            29715.8 MB/s
BenchmarkWrite_1024K_8Cores            55177.7 MB/s
BenchmarkWrite_1024K_12Cores           65329.6 MB/s
BenchmarkWrite_1024K_16Cores           79966.4 MB/s

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

Подведение итогов

Перейдите на GitHub, чтобы получить репозиторий HighwayHash и протестируйте его сами.

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

Перевод на русский язык см. По этой ссылке.