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

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 до 2⁶⁴−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») функция определяется следующим образом:

[math]\displaystyle{ \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) }[/math]

где:

[math]\displaystyle{ M = \begin{pmatrix} 1 & 4 & 7 & 1\\ 1 & 1 & 4 & 7\\ 7 & 1 & 1 & 4\\ 4 & 7 & 1 & 1 \end{pmatrix} }[/math];

[math]\displaystyle{ U }[/math] — это матрица байт размером 4x4 (то есть матрица после S-блочной подстановки);

[math]\displaystyle{ M^T }[/math] — это транспонированная матрица M.

Преобразование [math]\displaystyle{ ROL }[/math] принимает матрицу 4x4 и сдвигает [math]\displaystyle{ i }[/math]-тую строку влево на [math]\displaystyle{ i }[/math] байт, то есть

[math]\displaystyle{ \text{ROL}(W)_j^i = W_{j-i \pmod 4}^{i} }[/math]

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

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

[math]\displaystyle{ \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} }[/math]

Круговая трансформация (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, возвращаются следующие колонки: S₁ S₂ S₃ S₄ S₁₅ S₁₆ S₁₇ S₁₈, то есть, если финальное состояние выглядит следующим образом:

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

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

Fugue-224

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

[math]\displaystyle{ \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} }[/math]

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 до 2⁶⁴−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 и вычисляет:

[math]\displaystyle{ \text{HMAC-Fugue-256}(K, X) = \text{Fugue-256}(K \oplus \text{opad } | \text{ Fugue-256}(K \oplus \text{ipad } | \text{ } X)) }[/math]

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

Независимые тесты производительности алгоритма 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

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

Примечания

↑ Кандидаты второго раунда конкурса SHA-3.
↑ http://csrc.nist.gov/publications/nistir/ir7764/nistir-7764.pdf Архивная копия от 15 февраля 2013 на Wayback Machine Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition
↑ Официальный сайт eBASH benchmark.
↑ Официальная документация хеш-функции Fugue 2.0.

Литература

The Hash Function Fugue official website (англ.). Дата обращения: 20 декабря 2013.

SHA-3 competition(2007-2012) (англ.). Дата обращения: 20 декабря 2013.

The Hash Function Fugue official docs (англ.). Дата обращения: 20 декабря 2013.

The Hash Function Fugue 2.0 official docs (англ.). Дата обращения: 20 декабря 2013.

eBASH: Encrypt benchmark official site (англ.) (недоступная ссылка). Дата обращения: 20 декабря 2013. Архивировано 4 декабря 2013 года.

SHA-3 second round candidates (англ.). Дата обращения: 20 декабря 2013.

[_25ec85ff460aafe4-1] Кандидаты второго раунда конкурса SHA-3.

[2] ttp://csrc.nist.gov/publications/nistir/ir7764/nistir-7764.pdf Архивная копия от 15 февраля 2013 на Wayback Machine Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition

[_a65578a0dcf95247-3] Официальный сайт eBASH benchmark.

[_a02634cb1b8c5462-4] Официальная документация хеш-функции Fugue 2.0.

[1]

[2]

[3]

[4]

Хеш-функции
Общего назначения	Adler-32 CRC Контрольная сумма Флетчера FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH-Дерево хешей Jenkins hash Хеш-сумма
Криптографические	Стрибог ГОСТ Р 34.11-94 BelT BLAKE BMW CubeHash ECHO Edonkey2k FSB Fugue Grøstl HAVAL Hamsi JH Kupyna LM-хеш Luffa MD2 MD4 MD5 MD6 N-Hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Skein Snefru Tiger Whirlpool
Функции формирования ключа	bcrypt PBKDF2 scrypt Argon2 Lyra2
Контрольное число (сравнение)	Контрольная сумма Алгоритм Верхуффа Алгоритм Луна Алгоритм Дамма Штрих-код Банковских счетов Банковских карт ISIN СНИЛС ОКПО ИНН ОКАТО ISBN ОГРН и ОГРНИП VIN
Применение хешей	Сравнение контрольных чисел Протоколы аутентификации Сравнение штрихкодов Криптография Magnet-ссылка Подпись Меркла ed2k URN