Чуть менее, чем самая быстрая, переносимая, 64-битная хеш-функция, с достойным качеством.
Да, вжух и в дамки, примерно так. Читаем дальше?
Опустим определение хеш-функций вместе с детальным перечислением свойств и требований для их криптографического применения, предполагая что читатель либо владеет необходимым минимумов знаний, либо восполнит их. Также условимся, что здесь и далее мы подразумеваем некриптографические (криптографически не стойкие) хеш-функции, если явно не указывается иное.
Хеширование применяется в массе алгоритмов, при этом практически всегда требуется максимально эффективная (быстрая) обработка данных, одновременно с соблюдением некоторого минимального уровня качества хеширования. Причём под «качеством», прежде всего, пониvмается «условная случайность» (стохастичность) результата относительно исходных данных. Несколько реже предъявляются дополнительные требования: устойчивость к преднамеренной генерации коллизий или необратимость.
Для стройности изложения необходимо определить понятия «качества» хеш-функции и остальные требования чуть более детально:
- Базовое качество: Изменение одного или более произвольных бит в произвольном наборе исходных данных, приводит к изменению каждого бита результата с вероятностью ½.
- Необратимость (стойкость к восстановлению прообраза): Невозможность получения исходных данных или отдельных битов по результату хеширования.
- Устойчивость к подбору под результат (стойкость к коллизиям первого рода): Сложность поиска/подбора исходного набора данных с целью получения заданного результата или даже отдельных его битов, в том числе когда известен исходный набора данных.
- Устойчивость к подбору сообщений (стойкость к коллизиям второго рода): Сложность поиска/подбора двух разных наборов данных, которые давали бы одинаковый результат или совпадение отдельных битов.
Опуская цитирование доказательств и прочие выкладки можно констатировать:
- Надлежащее выполнение всех пунктов, одновременно с обеспечением производительности, является достаточно трудной задачей, решение которой даёт хорошую криптографическую хеш-функцию. Но мы пока заниматься этим не будем.
- Обеспечение базового качества требует достаточно большого количества операций АЛУ. Проще говоря, качество всегда конфликтует со скоростью.
- Получение качественного результата с разрядностью больше разрядности операций АЛУ требует более, чем кратного увеличения количества перемешиваний, а следовательно базовых операций АЛУ.
- В целом, создание быстрой хеш-функции предполагает достижения взвешенного компромисса между скоростью, качеством и разрядностью результата.
Так вот, можно сказать, что t1ha появилась в результате поиска компромисса между качеством и скоростью, одновременно с учетом возможностей современных процессоров и уже найденных способов (арифметико-логических комбинаций) перемешивания и распространения зависимостей (лавинного эффекта).
Базовый вариант t1ha является (самой) быстрой переносимой хеш-функцией для построения хеш-таблиц и других родственных применений. Поэтому базовый вариант t1ha ориентирован на 64-битные little-endian архитектуры, принимает 64-битное подсаливающее значение (seed) и выдает 64-битный результат, который включает усиление длиной ключа и seed-ом. Стоит отметить, t1ha намеренно сконструирована так, чтобы возвращать 0 при нулевых входных данных (ключ нулевого размера и нулевой seed).
64-битные операции: Возможно стоит пояснить, что именно 64-битные операции дают скорость и качество, не отбирая переносимости. Собственно, чем шире разрядность арифметических операций, тем больше они дают лавинного эффекта и лучше перемешивают данные. Ну и обрабатывать данные, при прочих равных, конечно быстрее по 8 байт, чем по 4. С другой стороны, именно 64-битные операции нативно доступны на многих современных процессорах, и более-менее сносно могут быть оттранслированы в 32-битные. Все прочие варианты, в том числе SIMD-операции, заставляют сильно жертвовать переносимостью и/или скоростью на "не родных" платформах.
64-битный результат: Для построения хеш-таблиц, во многих случаях, действительно достаточно результата меньшей ширины. Даже 32 бит может быть более, чем достаточно. Однако, при использовании 64-битных операций, 64-битный результат фактически получается сам-собой. При этом достаточно качественный 64-битный результат хеширования позволяет быстро выполнять сравнение на не-равенство, и с хорошей достоверностью сравнивать на равенство.
Эта "магия" замены сравнений может быть непонятной и не востребованной, а может на порядок повысить скорость работы только за счет локальности, т.е. меньшего вымывания кэша CPU. Проще говоря, вы можете построить структуру хеш-таблицы так, чтобы вычисленные хеш-значения лежали рядом (паковались в кэш-линии). А за реальными данными процессору приходилось идти только при совпадении хеш-значений. И вот в этом случае 64-бита от t1ha позволяют получить предельный результат. Причем 128 бит уже не дадут выигрыша, а взять от 64 битов меньше — можно всегда.
Сравнение с HighwayHash: У меня двоякое отношение к этому неофициальному проекту сотрудников Google.
- Во-первых: С одной стороны, хороший код и отличное техническое воплощение. С другой стороны, HighwayHash позиционируется как возможно криптографический стойкий (как минимум равный SipHash). Хотя доказательство "стойкости" сводится к результатам статистических тестов, но без возможности их воспроизвести (как-то я даже позволил себе лишнее).
- Во-вторых: HighwayHash действительно быстр только на x86_64 c AVX2 или SSE41. Так не проще ли использовать AES-NI или акселерацию SHA?
Если всё будет хорошо, то в наборе t1ha появятся дополнительные варианты (прежде всего по ширине результата) и оптимизированные для E2K. На этом тему сравнения с HighwayHash я хотел-бы закрыть.
Качество
Оценить качество хеш-функции во всех аспектах достаточно сложно. Можно идти аналитическим путем, либо проводить различные статистические испытания. К сожалению, аналитический подход малоэффективен для оценки хеш-функций с компромиссом между качеством и скоростью. Причем сравнительная аналитическая оценка таких функций стремится к субъективной.
Напротив, для статистических испытаний легко получить прозрачные количественные оценки. При этом есть хорошо зарекомендовавшие себя тестовые пакеты, например SMHasher. Для t1ha результаты просты — все варианты t1ha проходят все тесты без каких-либо замечаний. С другой стороны, не следует считать, что у t1ha есть какие-либо свойства сверх тех, что необходимы для целевого применения (построение хеш-таблиц).
Читатели наверняка оценили бы тщательный и глубокий анализ качественности и/или стойкости t1ha. Однако, исходя из целевых областей применения t1ha это представляется излишним. Проще говоря, нам была важнее скорость, в том числе для коротких ключей. Поэтому много-раундовое перемешивание не рассматривалось. Представляемый вариант t1ha экономит на спичках тактах и выдает 64-битный результат — практически бессмысленно измерять найденный компромисс иначе, как статистически, а эти результаты просто хороши.
я просто беру пример в statistical prove с коллег из Google ;)
Бенчмарки
Стоит пояснить наличие в заголовке словосочетания «самая быстрая». Действительно, крайне маловероятно, что существует хеш-функция, которая будет полезной и одновременно самой быстрой на всех платформах/архитектурах. На разных процессорах доступны разные наборы инструкций, а схожие инструкции выполняются с разной эффективностью. Очевидно, что «всеобщая самая быстрая» функция, скорее всего, не может быть создана. Однако, представляется допустимым использовать «самая быстрая» для функции, которая является переносимой и одновременно самой быстрой, как минимум на самой распространенной платформе (x86_64), при этом имея мало шансов проиграть на любом современном процессоре с достойным оптимизирующим компилятором.
В состав исходных текстов проекта входит тест, который проверяет как корректность результата, так и замеряет скорость работы каждого реализованного варианта. При этом на x86, в зависимости от возможностей процессора (и компилятора) могут проверяться дополнительные варианты функций, а замеры производятся в тактах процессора.
Кроме этого, на сайте проекта приведены таблицы с результатам замеров производительности посредством доработанной версии SMHasher от Reini Urban. Соответственно, все цифры можно перепроверить и/или получить результаты на конкретном процессоре при использовании конкретного компилятора.
Здесь же можно привести сопоставление с некоторыми ближайшими конкурентами t1ha.
Хеширование коротких ключей (среднее для 1..31 байта).
Смотрим на правую колонку «Cycles/Hash» (чем меньше значение, тем быстрее):
| Function | MiB/Second | Cycles/Hash |
|---|---|---|
| t1ha | 12228.80 | 35.55 |
| FastHash64 | 5578.06 | 43.42 |
| CityHash64 | 11041.72 | 51.77 |
| xxHash64 | 11123.15 | 56.17 |
| MetroHash | 11808.92 | 46.33 |
Хеширование длинных ключей (256 Кб).
Смотрим на среднюю колонку «MiB/Second» (чем больше значение, тем быстрее):
| Function | MiB/Second | Cycles/Hash |
|---|---|---|
| t1ha | 12228.80 | 35.55 |
| FarmHash64 | 12145.36 | 60.12 |
| CityHash64 | 11041.72 | 51.77 |
| xxHash64 | 11123.15 | 56.17 |
| Spooky64 | 11820.20 | 60.39 |
Варианты t1ha
Разработка t1ha преследовала сугубо практические цели. Первой такой целью было получение быстрой переносимой и достаточно качественной функции для построения хеш-таблиц.
Затем потребовался максимально быстрый вариант хеш-функции, который давал-бы сравнимый по качеству результат, но был максимально адаптирован на целевую платформу. Например, базовый вариант t1ha работает с little-endian порядком байт, из-за чего на big-endian архитектурах требуется конвертация с неизбежной потерей производительности. Так почему-бы не избавиться от лишних операций на конкретной целевой платформе? Таким же образом было добавлено ещё несколько вариантов:
- Упрощенный вариант для 32-битных платформ, как little, так и big-endian.
- Вариант с использованием инструкций AES-NI для процессоров без AVX.
- Два варианта с использованием инструкций AES-NI с использованием AVX.
Чуть позже стало понятно, что потребуются ещё варианты, сконструированные для различных применений, включая разную разрядность результата, требования к качеству и стойкости. Такое многообразие потребовало наведения порядка. Что выразилось в смене схемы именования, в которой цифровой суффикс обозначает «уровень» функции:
t1ha0()— максимально быстрый вариант для текущего процессора.t1ha1()— базовый переносимый 64-битный вариант t1ha.t1ha2()— переносимый 64-битный вариант с чуть большей заботой о качестве.t1ha3()— быстрый переносимый 128-битный вариант для получения отпечатков.- и т.д.
В этой схеме предполагается, что t1ha0() является диспетчером, который реализует перенаправление в зависимости от платформы и возможностей текущего процессора. Кроме этого, не исключается использование суффиксов «_le» и «_be» для явного выбора между little-endian и big-endian вариантами. Таким образом, под «вывеской» t1ha сейчас находится несколько хеш-функций и это семейство будет пополняться, в том числе с прицелом на отечественный E2K «Эльбрус».
Представление о текущем наборе функций и их свойствах можно получить из вывода теста. Стоит лишь отметить, что все функции проходят все тесты SMHasher, а производительность вариантов AES-NI сильно варьируется в зависимости от модели процессора:
Simple bench for x86 (large keys, 262144 bytes):
t1ha1_64le: 47151 ticks, 0.1799 clk/byte, 16.679 Gb/s @3GHz
t1ha1_64be: 61602 ticks, 0.2350 clk/byte, 12.766 Gb/s @3GHz
t1ha0_32le: 94101 ticks, 0.3590 clk/byte, 8.357 Gb/s @3GHz
t1ha0_32be: 99804 ticks, 0.3807 clk/byte, 7.880 Gb/s @3GHz
Simple bench for x86 (small keys, 31 bytes):
t1ha1_64le: 39 ticks, 1.2581 clk/byte, 2.385 Gb/s @3GHz
t1ha1_64be: 42 ticks, 1.3548 clk/byte, 2.214 Gb/s @3GHz
t1ha0_32le: 51 ticks, 1.6452 clk/byte, 1.824 Gb/s @3GHz
t1ha0_32be: 54 ticks, 1.7419 clk/byte, 1.722 Gb/s @3GHz
Simple bench for AES-NI (medium keys, 127 bytes):
t1ha0_ia32aes_noavx: 72 ticks, 0.5669 clk/byte, 5.292 Gb/s @3GHz
t1ha0_ia32aes_avx: 78 ticks, 0.6142 clk/byte, 4.885 Gb/s @3GHz
t1ha0_ia32aes_avx2: 78 ticks, 0.6142 clk/byte, 4.885 Gb/s @3GHz
Simple bench for AES-NI (large keys, 262144 bytes):
t1ha0_ia32aes_noavx: 38607 ticks, 0.1473 clk/byte, 20.370 Gb/s @3GHz
t1ha0_ia32aes_avx: 38595 ticks, 0.1472 clk/byte, 20.377 Gb/s @3GHz
t1ha0_ia32aes_avx2: 19881 ticks, 0.0758 clk/byte, 39.557 Gb/s @3GHzЕсли говорить чуть более детально, то t1ha построена по схеме Меркла-Дамгарда (в варианте «wipe-pipe») с упрочнением от размера данных и подсаливающего значения. Внутри основного сжимающего цикла используется 256-битное состояние, с аналогичным размером входного блока. Причем для каждого операнда данных реализуется две точки инъекции с перекрестным опылением. По завершению сжимающего цикла выполняется сжатие 256-битного состояния до 128 бит.
При выполнении описанных действий используются 64-битные операции, которые комбинируются в миксеры ARX (Add-Rotate-Xor) и MUX/MRX (Mul-Rotate-Xor). Немаловажно, что все эти вычисления выстроены так, чтобы обеспечить возможность параллельного выполнения большинства операций и плотной укладки u-ops как в конвейер, так и в исполняющие устройства x86_64. За счет этого достигается достаточно хорошее качество при практически предельной скорости хеширования длинных ключей.
Стоит отметить, что сжимающий цикл запускается только для блоков достаточного размера. Если же данных меньше, то промежуточное 128-битное состояние будет состоять только из размера ключа и подсаливающего значения.
Далее, оставшийся хвост данных порциями по 64 бита подмешивается попеременно к половинам 128-битного состояния. В заключении выполняется перемешивание состояния одновременно со сжатием до 64-битного результата. Немаловажной особенностью t1ha здесь является использование миксера на базе широкого умножения (128-битное произведение двух 64-битных множителей). Это позволяет реализовать качественно перемешивание с хорошим лавинным эффектом за меньшее количество операций. Несмотря на то, что широкое умножение относительно дорогая операция, меньшее количество операций позволяет t1ha обрабатывать короткие ключи за рекордно малое количество тактов процессора.
Следует отметить, что используемый миксер на основе широкого умножения и исключающего ИЛИ не идеален. Несмотря на то, что t1ha проходит все тесты SMHasher, у автора есть представление о последствиях неинъективности. Тем не менее, результирующее качество представляется рационально-достаточным, а в планах развития линейки t1ha уже отражено намерение предоставить чуть более качественный вариант.
Спасибо за внимание. Всем добра.
Автор: Леонид Юрьев
