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

Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Октябрь 2014 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Смысл продажи 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, и, как и Гриндал, использует 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 {ext {SuperMix}} (U) = {ext {ROL}} left (Mcdot U + {egin {pmatrix} sum _ {jeq 0} U_ {j} ^ {i} & 0 & 0 & 0 0 & sum _ {jeq 1} U_ {j} ^ {i} & 0 & 0 0 & 0 & sum _ {jeq 2} U_ {j} ^ {i} & 0 0 & 0 & 0 & sum _ {jeq 3} U_ {j} ^ {i} end {pmatrix}} cdot M ^ {T} ight)}$

куда:

${displaystyle M = {egin {pmatrix} 1 & 4 & 7 & 1 1 & 1 & 4 & 7 7 & 1 & 1 & 4 4 & 7 & 1 & 1end {pmatrix}}}$;

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

${displaystyle M ^ {T}}$ является транспонированной М.

Преобразование ${displaystyle ROL}$ берет матрицу 4x4 и вращает ${displaystyle i}$-й ряд слева на ${displaystyle i}$ байтов, т.е.

${displaystyle {ext {ROL}} (W) _ {j} ^ {i} = W_ {j-i {pmod {4}}} ^ {i}}$

Фуга 2.0

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

внешняя ссылка

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