Криптогафическая хэш-функция Whirlpool

В данной статье описана общая структура криптографической хеш-функции Whirlpool и основные процедуры для хеширования данных . Приведены результаты криптоанализа Whirlpool, позволяющие сделать вывод о дальнейшем развитии хеш-функций.

Ключевые слова: хеш-функции, cхема Миагучи-Пренеля, функция раунда , криптоанализ Whirlpool

Содержание

1. Введение

Хеширование : преобразование исходного информационного массива произвольной длины в битовую строку фиксированной длины.

Криптографическая хеш-функция : хеш-функция, являющаяся криптографически стойкой, то есть удовлетворяющая ряду требований, специфичных для криптографических приложений. Функции хеширования могут применяться в качестве криптографических генераторов псевдослучайных чисел для создания нескольких ключей на основе одного секретного ключа. Криптографические хеш-функции используют для защиты информации от несанкционированного доступа. Также хеш-функции применяют в базах данных для хранения паролей и оганизации хеш-таблиц.

Whirlpool [1] : криптографическая хеш-функция, разработанная Винсентом Риджменом (Vincent Rijmen) и Пауло Баретто (Paolo Barreto). Впервые опубликована в ноябре 2000 года. Осуществляет хеширование входного сообщения с длиной до 2 sup 256 бит. Одобрена европейской организацией NESSIE (New European Schemes for Signature, Integrity and Encryption, Новые европейские схемы подписей, целостности и шифрования). Основой для хеш-функций может быть блочный шифр с симметричными ключами. Для Whirlpool функцией сжатия является блочный шифр AES.

2. Структура Whirlpool

2.1. Дополнение сообщения

Входное сообщение разбивается на 512-битовые блоки M sub 1, M sub 2, M sub 1, если длина блока M sub k < 512 бит, блок M sub k дополянется до 512 бит. Результатом дополнения сообщения M является сообщение M prime, длина M prime кратна 512 бит. Пусть L - длина сообщения M. Для того, чтобы получить M prime, необходимо сделать 3 операции: 1) К концу сообщения M приписать бит «1»; 2) Приписать x битов «0», чтобы длина полученной строки L+1+ x была кратна 256 нечетное число раз; 3) Приписать 256-битное представление числа L. Для решения данной проблемы в Whirlpool используется дополнение входного сообщения. Результатом дополнения сообщения M является сообщение M prime, длина которого кратна 512 бит. Пусть L — длина исходного сообщения. Для того, чтобы получить M prime, необходимо сделать 3 операции:

  1. К концу сообщения M приписать бит «1» ;
  2. Приписать x битов «0» так, чтобы длина полученной строки L+1+x была кратна 256 нечетное число раз;
  3. Приписать 256-битное представление числа L.

2.2. Схема Миагучи-Пренеля

Whirlpool использует структуру Меркля-Дамгарда[2] и одностороннюю функцию сжатия Миагучи-Пренеля[2] (рис. 1) для формирования 512-блока зашифрованого текста W. После дополнения входное сообщение разбивается на 512-битовые блоки M sub 1, M sub 2, M sub t, которые используются для генерации последовательности хэш-значений H sub 1, H sub 2, H sub t (H sub 0 - строка из 512 «0» бит). Для вычисления H sub i, W шифрует M sub i, используя в качестве ключа H sub {i-1}, и выполняет XOR между H sub {i-1} и M sub i. Значением хэш-функции является H sub k.

2.3. Параметры алгоритма

Входным потоком для алгоритма Whirlpool является последовательность произвольной длины, выходным потоком является последовательность 512 бит. Ключ хеширования для алгоритма Whirlpool - последовательность из 512 бит. Алгоритм состоит из 10 раундов. На каждом раунде используется функция раунда.

2.4 Функция раунда

512 бит входного блока группируются в 64 байта a sub 0 .. a sub 63. Затем эти байты записываются

в матрицу размером 8 * 8: left | matrix { ccol {a sub 0 above a sub 1 above a sub 2 above a sub 3 above a sub 4 above a sub 5 above a sub 6 above a sub 7} ccol {a sub 8 above a sub 9 above a sub 10 above a sub 11 above a sub 12 above a sub 13 above a sub 14 above a sub 15} ccol {a sub 16 above a sub 17 above a sub 18 above a sub 19 above a sub 20 above a sub 21 above a sub 22 above a sub 23} ccol {a sub 24 above a sub 25 above a sub 26 above a sub 27 above a sub 28 above a sub 29 above a sub 30 above a sub 31} ccol {a sub 32 above a sub 33 above a sub 34 above a sub 35 above a sub 36 above a sub 37 above a sub 38 above a sub 39} ccol {a sub 40 above a sub 41 above a sub 42 above a sub 43 above a sub 44 above a sub 45 above a sub 46 above a sub 47} ccol {a sub 48 above a sub 49 above a sub 50 above a sub 51 above a sub 52 above a sub 53 above a sub 54 above a sub 55} ccol {a sub 56 above a sub 57 above a sub 58 above a sub 59 above a sub 60 above a sub 61 above a sub 62 above a sub 63} } right | .

В дальнейшем нам придется работать в конечном поле GF(2 sup 8 ). Элементы GF(2 sup 8 ) это байты, они могут складываться с помощью операции XOR. Модель конечного поля GF(2 sup 8 ) зависит от выбора неприводимого многочлена степени 8. Для Whirlpool этим многочленом является X sup 8 + X sup 4 + X sup 3 + X sup 2 + 1.

Процедуры, входящие в функцию раунда:

  1. сдвиг столбцов матрицы состояния на различную величину (ShiftColumns?);
  2. перемешивание данных каждого столбца матрицы состояния (SubBytes?);
  3. умножение каждого столбец матрицы состояния на матрицу констант в GF(2 sup 8 )(MixRows?);
  4. сложение ключа раунда с матрицей состояния (AddRoundKey?).

ShiftColumns?

Процедура ShiftColumns? (рис. 3) обеспечивает сдвиг столбцов матрицы состояния на различную величину. Столбец j сдвигается на j байт (Столбец 0 не изменяется, столбец 7 сдвигается на 7 байт.) В результате в матрице состояния записаны новые 8 байт.

SubBytes?

Процедура SubBytes? (рис. 4) обеспечивает нелинейную замену байт матрицы состояния с помощью таблицы (S-Box). Байт представляют в виде двух шестнадцатеричных цифр. Левая цифра определяет строку, а правая- столбец таблицы подстановки. Две шестнадцатеричные цифры на пересечении строки и столбца определяют новый байт. Например, два байта, 5A16 и 5B16, которые отличаются только одним битом, преобразованы к 5B sub 16 и 88 sub 16, которые отличаются пятью битами. Таблица S-Box приведена в приложениии 1

Таблица может быть вычислена алгебраически, используя поле GF(2 sup 4 ) с неприводимым полиномом (x sup 4 + x + 1). E - миниблоки вычисляют степень, равную шестнадцатеричному значению входа; R - миниблок использует псевдослучайный генератор чисел.

Каждая шестнадцатеричная цифра в байте передается миниблок ( E и E sup -1 ).

Результаты блока E и E sup -1 складываются с помощью XOR, и передаются на миниблок R.

Чтобы получить старшие 4 бита результата, выполняется XOR между выходами миниблоков E и R.

Чтобы получить младшие 4 бита результата, выполняется XOR между выходами миниблоков E sup -1 и R.

https://photos-1.dropbox.com/t/2/AABNAuRS6-Ft-p8G6td7PdMYBfYBz156FSSMScm0i-dK_w/12/544189381/jpeg/32x32/1/_/1/2/sbox_generate.bmp/EJeZwq0EGBsgAigC/e537EAFtAAI5Lm0pAwqqZ7rWI1ZNqdxDR3uYzmytJCc?size=1024x768&size_mode=3

2.4.3. MixRows?

Процедура MixRows? - матричное преобразование, где байты интерпретируются как полиномы с коэффициентами в GF(2 sup 8 ). Каждая строка матрицы состояния перемножается с фиксированным многочленом с(x) в GF(2 sup 8 ). Для Whirlpool этим многочленом является X sup 8 + X sup 4 + X sup 3 + X sup 2 + 1.

2.4.4. AddRoundKey?

В преобразовании AddRoundKey? байт матрицы состояния складывается в поле GF(2 sup 8 ) с соответствующим байтом матрицы состояний ключей раунда. Результат - новый байт в новой матрице состояний.

2.4.5. Константы раунда

Каждая константа раунда RC sup r является матрицей 8 x 8, где только первая строка имеет значения, отличные от нуля. Остальная часть входов содержит все нули. Значения для первой строки в каждой матрице констант могут быть вычислены, используя преобразование SubBytes?. Другими словами, RC sup 1 использует первые восемь входов в таблице преобразования SubBytes?; RC sup 2 использует вторые восемь входов, и т. д.

2.4.6 Расширение ключа

Для каждого раунда r , 0<= r <= 10 необходим 512-битный ключ шифрования. Для решения данной проблемы во многих алгоритмах вводится так называемая процедура расширения ключа. В Whirlpool расширение ключа реализуется следующим образом:

K sup 0 = K

K sup r = p\[RC sup r \] * K sup {r - 1}, r >= 0

где K sup r - ключ раунда, RC sup r - константа раунда, а p\[\] - функция раунда;

Таким образом, из известного ключа K производится необходимая последовательность K sup 0 ...,K sup 10 ключей для каждого раунда блочного шифра W.

3. Криптостойкость

В 2004 году Taizo Shirai и Kyoji Shibutani обнаружили дефект в диффузных матрицах Whirlpool[2], в последствии он был исправлен. В 2009 году был опубликован новый способ атаки на хеш-функции- The Rebound Attack[3]. Удалось сгенерировать коллизию для 4,5 раундoв Whirlpool со сложностью 2120. Однако, данная атака не сильно повлияла на криптостойкость Whirlpool, сложность вычислений оказалась достаточно высока. На сегодняшний день хеш-функция Whirlpool устойчива ко всем видам криптоанализа.

4. Заключение

Не смотря хорошую криптографическую стойкость, хеш-функция Whirlpool мало изучена. Она базируется на устойчивой схеме Миагучи-Пренеля, в качестве функции сжатия использует шифр, основанный на AES. Кроме того, размер дайджеста сообщения 512 бит, поэтому Whirlpool является очень сильной функцией криптографического хеширования. Однако для ее повсеместного использования необходимо провести серьезные исследования.

5. Список литературы

  1. Vincent Rijmen, Paolo Barreto. "The WHIRLPOOL Hashing Function"- Scopus Tecnologia S. A, San Paulo, Brazil, 2000,
  2. Schneier Bruce, Ferguson Niels, "Practical cryptography"- Inc, Wiley Publishing, pp 432 ,2003.
  3. Taizo Shirai, Kyoji Shibutani. "On the diffusion matrix employed in the Whirlpool hashing function",- NESSIE public report, 2003
  4. Florian Mendel, Christian Rechberger, Martin Schlaffer, Soren S. Thomsen. "The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grostl"- Unpublished manuscript, 2009.

КатегорияКриптография