Fugue (хеш-функция)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Fugue
Разработчики Shai Halevi, William E. Hall, Charanjit S. Jutla
Создан 2009
Опубликован Октябрь 2009
Размер хеша 224, 256, 384 или 512 бит
Число раундов 4
Тип хеш-функция

Fugue — алгоритм хеширования, разработанный Shai Halevi[англ.], William E. Hall и Charanjit S. Jutla из IBM для конкурса хеш-функций Национального Института стандартов и технологий в 2009 году, где прошёл во второй раунд[1]. Однако алгоритм не прошёл в третий раунд конкурса из-за недостаточного количества криптографического анализа и неуверенности в криптостойкости.[2]

Для входного сообщения длиной от 1 до 264−1 бит алгоритм генерирует 224, 256, 384 или 512-битное хеш-значение, называемое также дайджестом сообщения. Функции для соответствующих длин выходных данных называются соответственно Fugue-224, Fugue-256, Fugue-384 и Fugue-512. Авторы также описали параметризованную версию алгоритма Fugue. Слабозащищенная версия Fugue-256, работающая в два раза быстрее стандартной версии, также описывается через параметризованную версию.

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

Основная идея

[править | править код]

В основу Fugue положен хеш алгоритм Grindahl, и потому использует S-блоки из AES, однако перестановочная матрица 4x4 заменена 16x16 «супер-перестановочной» («Super-Mix») операцией, значительно улучшая лавинный эффект. При этом «супер-перестановка» («Super-Mix») является лишь чуть более трудозатратной операцией, чем перестановочная стратегия AES.

Супер-перестановка (Super-Mix)

[править | править код]

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

В основе алгоритма, известного как «Супер перестановочное преобразование» («Super-Mix transformation»), лежит прием матрицы 4х4 в качестве входных данных и возвращение новой матрицы 4х4. На вход функции передаются просто первые четыре колонки из текущей матрицы (4x30 или 4x36) и полученная новая матрица подставляется вместо использованных входных данных. Таким образом, супер-перестановка затрагивает только первые 4 столбца матрицы состояния.

«Супер-перестановочная» («Super-Mix») функция определяется следующим образом:

где:

;
 — это матрица байт размером 4x4 (то есть матрица после S-блочной подстановки);
 — это транспонированная матрица M.

Преобразование принимает матрицу 4x4 и сдвигает -тую строку влево на байт, то есть

Супер-перестановка является обратимой функцией.

Хеш-функция F-256

[править | править код]

Функция F-256 лежит в основе Fugue-256. F-256 принимает на вход 4-х-байтную строку и 32-х-байтный вектор инициализации (IV256) и выдает на выходе 32 байта хэшированного значения.

Хеш-функция F-256 сохраняет состояние тридцати 4-х-байтных колонок, начиная с инициализационного состояния, полученного из вектора инициализации (IV256). Входящий поток из 4m байт (m≥0) разбивается на m четырёхбайтных слова и отдается по одному слову в функцию круговой трансформации (round transformation) R, которая меняет внутреннее состояние. После всех круговых трансформаций внутреннее состояние отправляется на финальный раунд трансформации G. В итоге 8 колонок состояния возвращаются в качестве результата функции F-256.

Вектор инициализации для F-256:

Круговая трансформация (round transformation) R

[править | править код]

Круговая трансформация R принимает на вход 30 колонок состояния S и одно 4-х-байтное слово I и возвращает новое состояние из 30 колонок. Трансформация R состоит из следующих шагов:

TIX(I);ROR3;CMIX;SuperMix;ROR3;CMIX;SuperMix;

где:

TIX(I) — это «уменьшение для XOR», «очистка» (Truncate), «вставка» (Insert), «исключающее или» (XOR), состоит из следующих шагов:

S10 += S0;
S0 = I;
S8 += S0;
S1 += S24.

ROR3 — это просто сдвиг состояния на 3 колонки вправо,

CMIX — это смешивание колонок (Column MIX), состоит из следующих шагов:

S0 += S4; S1 += S5; S2 += S6;
S15 += S4; S16 += S5; S17 += S6;

SuperMix (или SMIX) — это «супер-перестановка» («Super-Mix»)

Финальный раунд трансформации G

[править | править код]

Финальный раунд трансформации G принимает на вход 30 колонок состояния S и возвращает финальное состояние из 30 колонок. Вот, как это выглядит:

Повторяется 5 раз
   {
      ROR3;CMIX; SMIX
      ROR3;CMIX; SMIX
   }
Повторяется 13 раз
   {
      S4 += S0; S15 += S0;ROR15; SMIX;
      S4 += S0; S16 += S0;ROR14; SMIX;
   }
S4 += S0; S15 += S0;

Реализация хеш-алгоритма F-256 в псевдокоде

[править | править код]

Ниже приведена реализация хеш-алгоритма F-256 в псевдокоде, все обозначения указаны выше:

for j = 0..21, set Sj = 0;
for j = 0..7, set S(22+j) = IVj .
for i = 1..m
{ 
   TIX(Pi);
   Повторяется 2 раза 
   {
       ROR3;CMIX; SMIX; 
   }
}
Повторяется 10 раз 
   {
      ROR3;CMIX; SMIX; 
   }
Повторяется 13 раз 
   { 
      S4 += S0; S15 += S0;ROR15; SMIX;
      S4 += S0; S16 += S0;ROR14; SMIX;
   }
S4 += S0; S15 += S0;
Возвращается: S1 S2 S3 S4 S15 S16 S17 S18.

После финального раунда G, возвращаются следующие колонки: S1 S2 S3 S4 S15 S16 S17 S18, то есть, если финальное состояние выглядит следующим образом:

,

то первыми 16-ю байтами выхода будут: 04 05 06 07 08 09 … 12 13

Алгоритм Fugue-224 практически ничем не отличается от Fugue-256. Результатом функции F-224 являются байты S1…4S15…17 вместо S1…4S15…18 у Fugue-256, а также отличается вектор инициализации (IV224):

Отличия Fugue-384 от Fugue-256

[править | править код]

Алгоритм Fugue-384 практически ничем не отличается от Fugue-256. В этом алгоритме переопределены функции TIX(I) и CMIX, а также используется другой вектор инициализации (IV384) и несколько другой порядок операций в F-384 и возвращается хеш значение длиной 48 байт.

Реализация хеш-алгоритма F-384 в псевдокоде

[править | править код]

Ниже приведена реализация хеш-алгоритма F-384 в псевдокоде:

For j = 0..23, set Sj = 0;
For j = 0..11, set S(24+j) = IVj .
For i = 1..m
   { 
      TIX(Pi);
      Повторяется 3 раза: 
         {
            ROR3;CMIX; SMIX; 
         }
   }
Повторяется 18 раз : 
   {
      ROR3;CMIX; SMIX; 
   }
Повторяется 13 раз :
   {
      S4+ = S0; S12+ = S0; S24+ = S0; ROR12; SMIX;
      S4+ = S0; S13+ = S0; S24+ = S0; ROR12; SMIX;
      S4+ = S0; S13+ = S0; S25+ = S0; ROR11; SMIX;
   }
S4+ = S0; S12+ = S0; S24+ = S0;
Возвращается: S1..4 S12..15 S24..27.

где:

TIX(I) — это «уменьшение для XOR», «очистка» (Truncate), «вставка» (Insert), «исключающее или» (XOR), состоит из следующих шагов:

S16 += S0;
S0 = I;
S8 += S0;
S1 += S27; S4 += S30;

CMIX — это смешивание колонок (Column MIX), состоит из следующих шагов:

S0 += S4; S1 += S5; S2 += S6;
S18 += S4; S19 += S5; S20 += S6;

Отличия Fugue-512 от Fugue-256

[править | править код]

Алгоритм Fugue-512, как и Fugue-384, практически ничем не отличается от Fugue-256. В этом алгоритме также переопределены функции TIX(I) и CMIX и используется другой вектор инициализации (IV512) и несколько другой порядок операций в F-512. Fugue-512 возвращает хеш значение длиной 64 байт.

Реализация хеш-алгоритма F-512 в псевдокоде

[править | править код]

Ниже приведена реализация хеш-алгоритма F-512 в псевдокоде:

For j = 0..19, set Sj = 0;
For j = 0..15, set S(20+j) = IVj .
For i = 1..m
   { 
      TIX(Pi);
      Повторяется 4 раза : 
         {
            ROR3;CMIX; SMIX; 
         }
   }
Повторяется 32 раза : 
   {
      ROR3;CMIX; SMIX; 
   }
Повторяется 13 раз :
   {
      S4+ = S0; S9 + = S0; S18+ = S0; S27+ = S0; ROR9; SMIX;
      S4+ = S0; S10+ = S0; S18+ = S0; S27+ = S0; ROR9; SMIX;
      S4+ = S0; S10+ = S0; S19+ = S0; S27+ = S0; ROR9; SMIX;
      S4+ = S0; S10+ = S0; S19+ = S0; S28+ = S0; ROR8; SMIX;
   }
S4+ = S0; S9+ = S0; S18+ = S0; S27+ = S0;
Возвращается: S1..4 S9..12 S18..21 S27..30

где:

TIX(I) состоит из следующих шагов:

S22 += S0;
S0 = I;
S8 += S0;
S1 += S24; S4 += S27; S7 += S30;

CMIX(Column MIX) состоит из следующих шагов:

S0 += S4; S1 += S5; S2 += S6;
S18 += S4; S19 += S5; S20 += S6;

Разновидности Fugue-256

[править | править код]

«Псевдо-случайная» хеш-функция PR-Fugue-256

[править | править код]

PR-Fugue-256 принимает на вход двоичные данные от 0 до 264−1 бит, а также 32-х-байтный ключ. Этот ключ по сути используется в качестве вектора инициализации вместо фиксированного IV256, что является единственным отличием от Fugue-256.

«Сжатая» функция C-Fugue-256

[править | править код]

C-Fugue-256 определена для обратной совместимости для приложений, которые должны использовать сжатие структурой Меркла — Дамгарда. Разработчики утверждают, что такое использование Fugue не является оптимальным с точки зрения производительности и безопасности, но оно позволяет использовать Fugue в приложениях, которым это нужно.

Fugue-256 может заменить собой SHA-256 во многих режимах работы, включая HMAC, без использования обратно совместимой функции C-Fugue-256.

Например, HMAC-Fugue-256 принимает на вход данные X и ключ K и вычисляет:

Быстродействие

[править | править код]

Независимые тесты производительности алгоритма Fugue, проведенные с помощью бенчмарка eBASH, показали следующие результаты (скорость указана в циклах на байт (cpb))[3]:

Процессор Core i5 Core 2 (45 nm) Core 2 (65 nm)
Fugue 2.0 12.81 cpb 15.31 cpb 15.35 cpb
Fugue-256 16.75 cpb 18.42 cpb 21.41 cpb
Fugue-512 46.20 cpb 56.91 cpb 56.82 cpb

Функция Fugue обладает частично параллельной архитектурой, что позволяет создавать эффективные реализации алгоритма. Часть инструкций доступна на многих широко-известных архитектурах (x86, PowerPC, ARM).

Что касается требований, предъявляемых к RAM, хеш-функции Fugue необходимо достаточно много памяти для хранения внутреннего состояния.

Fugue 2.0[4] — расширение оригинального хеш-алгоритма Fugue, подготовленное авторами для второго раунда конкурса SHA-3, которое работает в два раза быстрее для 256-битного хеша. Дизайнеры доказали улучшенную защиту от атак дифференциального криптоанализа в новой версии.

Примечания

[править | править код]

Литература

[править | править код]