Фуга (хеш-функция)

Fugue - это криптографическая хеш-функция, представленная IBM на конкурс хеш-функций NIST. Он был разработан Шаем Халеви, Уильямом Э. Холлом и Чаранджитом С. Ютла. Fugue берет сообщение произвольной длины и сжимает его до фиксированной битовой длины (224, 256, 384 или 512 бит). Хеш-функции для разной длины вывода называются Fugue-224, Fugue-256, Fugue-384 и Fugue-512. Авторы также описывают параметризованную версию Fugue. Слабая версия Fugue-256 также описывается с помощью этой параметризованной версии.

Смысл продажи Fugue - это заявленное авторами доказательство того, что широкий спектр текущих стратегий атак, основанных на дифференциальном криптоанализе, не может быть эффективным против Fugue. Также утверждается, что он конкурирует с хэш-функцией NIST SHA-256 как по программной, так и по аппаратной эффективности, обеспечивая до 36,2 цикла на байт на Intel Family 6 Model 15 Xeon 5150 и до 25 циклов на байт на Intel Core. 2 процессора T7700. На 45-нм процессорах Core2, например T9400, Fugue-256 работает с 16 циклами на байт с использованием инструкций SSE4.1. На более новых архитектурах Westmere (32 нм), например, Core i5, Fugue-256 работает со скоростью 14 циклов на байт.

Дизайн Fugue начинается с хэш-функции Grindahl, и, как и Grindahl, использует S-блок из AES, но он заменяет матрицу смешивания столбцов 4 × 4 операцией «суперсмешивания» 16 × 16, что значительно улучшает распространение. Однако операция "супер-микширования" лишь немного дороже в вычислительном отношении для реализации, чем стратегия микширования AES.

224- и 256-битные варианты Fugue работают с состоянием, которое может быть представлено в виде матрицы 4 на 30 байтов без знака, тогда как варианты 384 и 512 бит работают с матрицей 4 на 36 байтов. В этом состоянии можно выполнять операции на месте.

Ядро алгоритма, известное как «преобразование SuperMix», принимает на входе матрицу 4 × 4 и возвращает новую матрицу 4x4. Входные данные SuperMix - это просто первые четыре столбца текущего состояния из 30 столбцов, а выходные данные используются для замены этой же области состояния (т.е. SuperMix влияет только на матрицу 4x4 в заголовке состояния).

Функцию SuperMix можно определить как:

${\ displaystyle {\ text {SuperMix}} (U) = {\ text {ROL}} \ left (M \ cdot U + {\ begin {pmatrix} \ sum _ {j \ neq 0} U_ {j} ^ {i } amp; 0 amp; 0 amp; 0 \\ 0 amp; \ sum _ {j \ neq 1} U_ {j} ^ {i} amp; 0 amp; 0 \\ 0 amp; 0 amp; \ sum _ {j \ neq 2} U_ {j} ^ {i} amp; 0 \\ 0 amp; 0 amp; 0 amp; \ sum _ {j \ neq 3} U_ {j} ^ {i} \ end {pmatrix}} \ cdot M ^ {T} \ right)}$

где:

${\ displaystyle M = {\ begin {pmatrix} 1 amp; 4 amp; 7 amp; 1 \\ 1 amp; 1 amp; 4 amp; 7 \\ 7 amp; 1 amp; 1 amp; 4 \\ 4 amp; 7 amp; 1 amp; 1 \ end {pmatrix}}}$;

${\ displaystyle U}$представляет собой матрицу байтов 4x4 (то есть матрицу после подстановки S-блока ввода); и

${\ Displaystyle M ^ {T}}$ транспонированная М.

Преобразование принимает матрицу 4x4 и поворачивает -ю строку влево на байты, т.е. ${\ displaystyle ROL}$${\ displaystyle i}$${\ displaystyle i}$

${\ displaystyle {\ text {ROL}} (W) _ {j} ^ {i} = W_ {ji {\ pmod {4}}} ^ {i}}$

Fugue 2.0 - это усовершенствованная версия оригинальной Fugue, которая работает примерно в два раза быстрее, чем Fugue для 256-битного вывода. Разработчики заявляют о расширенных доказательствах устойчивости к дифференциальным атакам на столкновение для этой улучшенной версии. Полную спецификацию можно найти по ссылке ниже.

• Фуга хеш-функции