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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Криптографическая
хэш-функция
Название

Fugue

Создан

2009

Опубликован

Октябрь 2009

Размер хэша

224, 256, 384 или 512 бит

Число раундов

4

Тип

хеш-функция

Fugue — алгоритм хеширования, разработанный Shai Halevi, William E. Hall и Charanjit S. Jutla из IBM для конкурса хеш-функций Национального Института стандартов и технологий (en:NIST hash function competition) в 2009 году, где прошел во второй раунд[1]. Для входного сообщения длиной от 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») функция определяется следующим образом:


\text{SuperMix}(U) = \text{ROL} \left( M \cdot U +  
\begin{pmatrix}
\sum_{j \ne 0} U_j^i & 0 & 0 & 0\\
0 & \sum_{j \ne 1} U_j^i & 0 & 0\\
0 & 0 & \sum_{j \ne 2} U_j^i & 0\\
0 & 0 & 0 & \sum_{j \ne 3} U_j^i
\end{pmatrix}  \cdot M^T \right)

где:


M = \begin{pmatrix}
1 & 4 & 7 & 1\\
1 & 1 & 4 & 7\\
7 & 1 & 1 & 4\\
4 & 7 & 1 & 1
\end{pmatrix}
;
U — это матрица байт размером 4x4 (то есть матрица после S-блочной подстановки);
M^T — это транспонированная матрица M.

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


\text{ROL}(W)_j^i = W_{j-i \pmod 4}^{i}

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

Хэш функция 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:


\text{IV256} =   
\begin{pmatrix}
e9 & 66 & e0 & d2 & f9 & fb & 91 & 34\\
52 & 71 & d4 & b0 & 6c & f9 & 49 & f8\\
bd & 13 & f6 & b5 & 62 & 29 & e8 & c2\\
de & 5f & 68 & 94 & 1d & de & 99 & 48
\end{pmatrix}

Круговая трансформация (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, то есть, если финальное состояние выглядит следующим образом:

  
\begin{pmatrix}
00 & 04 & 08 & 0c & 10\\
01 & 05 & 09 & 0d & 11\\
02 & 06 & 0a & 0e & 12 & ...\\
03 & 07 & 0b & 0f & 13
\end{pmatrix}
,

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

Fugue-224[править | править вики-текст]

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


\text{IV224} =   
\begin{pmatrix}
f4 & 62 & ee & e0 & a1 & 9a & bd\\
c9 & 86 & 39 & 74 & 12 & 43 & 8d\\
12 & f7 & e0 & e3 & 7c & d2 & 67\\
0d & 57 & 1c & cb & 62 & 15 & 9a
\end{pmatrix}

Fugue-384[править | править вики-текст]

Отличия 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-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 в приложениях, которым это нужно.

HMAC-Fugue-256[править | править вики-текст]

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

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


\text{HMAC-Fugue-256}(K, X) = \text{Fugue-256}(K \oplus \text{opad } | \text{ Fugue-256}(K \oplus \text{ipad } | \text{ } X))

Быстродействие[править | править вики-текст]

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

Процессор 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[править | править вики-текст]

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

Примечания[править | править вики-текст]

Литература[править | править вики-текст]