Whirlpool (криптография)

Интернет магазин китайских планшетных компьютеров

Компьютеры - Whirlpool (криптография) - Описание

30 марта 2011

Оглавление:
1. Whirlpool (криптография)
2. Описание
3. Криптостойкость
4. Применение

Введение

В данной статье описывается последняя версия Whirlpool. В отличие от первой версии S-box определен, а диффузная матрица заменена на новую после доклада Taizo Shirai и Kyoji Shibutani .

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

Используемые обозначения и операции

В алгоритме используются операции в поле Галуа $\ GF$ по модулю неприводимого многочлена $\ p_8 = x^8 + x^4 + x^3 + x^2 + 1$ .

Многочлены для краткости записываются в шестнадцатеричном представлении. Например, запись $\ 11D_x$ означает $\ p_8$ .

Символом $\circ$ обозначается оператор композиции . Выражение $f \circ g$ означает композицию функций $\ g$ и $\ f$ .

Для обозначения композиции последовательности функций $f_m, f_{m+1},...,f_{n-1}, f_n, m \leq n$ используется символ $\bigcirc_m^{r=n}$ :

$\bigcirc_m^{r=n} f_r \equiv f_n \circ f_{n-1} \circ \dots \circ f_{m+1} \circ f_m.$

$M_{m \times n}$ — множество матриц $m \times n$ над $\ GF.$

$\ cir$ — циркулянтная матрица $m \times m$ , первая строка которой состоит из элементов $\ a_0, a_1, . . . , a_{m-1},$ то есть:

$cir \equiv \begin{bmatrix} a_0 & a_1 & \dots & a_{m-1} \\ a_{m-1} & a_0 & \dots & a_{m-2} \\ \vdots & \vdots & \ddots & \vdots \\ a_1 & a_2 & \dots & a_0 \\ \end{bmatrix},$

или просто $\ cir = c \Leftrightarrow c_{ij} = a_{ mod m}, 0 \leq i,j \leq m-1.$

Формат данных

Как уже говорилось выше, Whirlpool построена на специальном блочном шифре W, который работает с 512-битными данными.

В преобразованиях промежуточный результат вычисления хеша называется хеш-состоянием или просто состоянием. При вычислениях состояние обычно представляется матрицей состояния. Для Whirlpool это матрица в $M_{8 \times 8}$ . Следовательно, 512-битные блоки данных должны быть преобразованы в этот формат перед дальнейшими вычислениями. Это достигается введением функции $\ \mu$ :

$\mu: GF^{64} \to M_{8 \times 8}, \qquad \mu = b \Leftrightarrow b_{ij} = a_{8i+j}, 0 \leq i,j \leq 7.$

Проще говоря, заполнение матрицы состояния данными происходит построчно. При этом каждый байт матрицы представляет собой соответствующий многочлен в $\ GF$ .

Преобразования

Нелинейное преобразование γ

Функция $\gamma: M_{8 \times 8} \to M_{8 \times 8}$ состоит из параллельного применения блока подстановки) $S: GF \to GF, x \to S$ ко всем байтам матрицы состояния:

$\gamma=b \Leftrightarrow b_{ij} = S, 0 \leq i,j \leq 7.$

Блок подстановки описывается следующей таблицей замен:

Таблица 1. Блок подстановки
	00_x	01_x	02_x	03_x	04_x	05_x	06_x	07_x	08_x	09_x	0A_x	0B_x	0c_x	0d_x	0E_x	0F_x
00_x	18_x	23_x	c6_x	E8_x	87_x	B8_x	01_x	4F_x	36_x	A6_x	d2_x	F5_x	79_x	6F_x	91_x	52_x
10_x	60_x	Bc_x	9B_x	8E_x	A3_x	0c_x	7B_x	35_x	1d_x	E0_x	d7_x	c2_x	2E_x	4B_x	FE_x	57_x
20_x	15_x	77_x	37_x	E5_x	9F_x	F0_x	4A_x	dA_x	58_x	c9_x	29_x	0A_x	B1_x	A0_x	6B_x	85_x
30_x	Bd_x	5d_x	10_x	F4_x	cB_x	3E_x	05_x	67_x	E4_x	27_x	41_x	8B_x	A7_x	7d_x	95_x	d8_x
40_x	FB_x	EE_x	7c_x	66_x	dd_x	17_x	47_x	9E_x	cA_x	2d_x	BF_x	07_x	Ad_x	5A_x	83_x	33_x
50_x	63_x	02_x	AA_x	71_x	c8_x	19_x	49_x	d9_x	F2_x	E3_x	5B_x	88_x	9A_x	26_x	32_x	B0_x
60_x	E9_x	0F_x	d5_x	80_x	BE_x	cd_x	34_x	48_x	FF_x	7A_x	90_x	5F_x	20_x	68_x	1A_x	AE_x
70_x	B4_x	54_x	93_x	22_x	64_x	F1_x	73_x	12_x	40_x	08_x	c3_x	Ec_x	dB_x	A1_x	8d_x	3d_x
80_x	97_x	00_x	cF_x	2B_x	76_x	82_x	d6_x	1B_x	B5_x	AF_x	6A_x	50_x	45_x	F3_x	30_x	EF_x
90_x	3F_x	55_x	A2_x	EA_x	65_x	BA_x	2F_x	c0_x	dE_x	1c_x	Fd_x	4d_x	92_x	75_x	06_x	8A_x
A0_x	B2_x	E6_x	0E_x	1F_x	62_x	d4_x	A8_x	96_x	F9_x	c5_x	25_x	59_x	84_x	72_x	39_x	4c_x
B0_x	5E_x	78_x	38_x	8c_x	d1_x	A5_x	E2_x	61_x	B3_x	21_x	9c_x	1E_x	43_x	c7_x	Fc_x	04_x
c0_x	51_x	99_x	6d_x	0d_x	FA_x	dF_x	7E_x	24_x	3B_x	AB_x	cE_x	11_x	8F_x	4E_x	B7_x	EB_x
d0_x	3c_x	81_x	94_x	F7_x	B9_x	13_x	2c_x	d3_x	E7_x	6E_x	c4_x	03_x	56_x	44_x	7F_x	A9_x
E0_x	2A_x	BB_x	c1_x	53_x	dc_x	0B_x	9d_x	6c_x	31_x	74_x	F6_x	46_x	Ac_x	89_x	14_x	E1_x
F0_x	16_x	3A_x	69_x	09_x	70_x	B6_x	d0_x	Ed_x	cc_x	42_x	98_x	A4_x	28_x	5c_x	F8_x	86_x

Циклическая перестановка π

Перестановка $\pi: M_{8 \times 8} \to M_{8 \times 8}$ циклически сдвигает каждый столбец матрицы состояния так, что столбец j сдвигается вниз на j позиций:

$\pi=b \Leftrightarrow b_{ij} = a_{ mod 8, j}, 0 \leq i,j \leq 7.$

Задача данного преобразования — перемешать байты строк матрицы состояния между собой.

Линейная диффузия θ

Линейная диффузия $\theta: M_{8 \times 8} \to M_{8 \times 8}$ — это линейное преобразование, матрицей которого является MDS матрица $\ C = cir$ , то есть:

$C = cir = \begin{bmatrix} 01_x & 01_x & 04_x & 01_x & 08_x & 05_x & 02_x & 09_x \\ 09_x & 01_x & 01_x & 04_x & 01_x & 08_x & 05_x & 02_x \\ 02_x & 09_x & 01_x & 01_x & 04_x & 01_x & 08_x & 05_x \\ 05_x & 02_x & 09_x & 01_x & 01_x & 04_x & 01_x & 08_x \\ 08_x & 05_x & 02_x & 09_x & 01_x & 01_x & 04_x & 01_x \\ 01_x & 08_x & 05_x & 02_x & 09_x & 01_x & 01_x & 04_x \\ 04_x & 01_x & 08_x & 05_x & 02_x & 09_x & 01_x & 01_x \\ 01_x & 04_x & 01_x & 08_x & 05_x & 02_x & 09_x & 01_x \\ \end{bmatrix},$

так что

$\theta=b \Leftrightarrow b = a \cdot C.$

Другими словами, матрица состояния умножается справа на матрицу $\ C$ . Напомним, что операции сложения и умножения элементов матриц производятся в $\ GF$ .

MDS матрица — это такая матрица над конечным полем $\ K$ , что если взять её в качестве матрицы линейного преобразования $\ f=x$ из пространства $\ K^n$ в пространство $\ K^m$ , то любые два вектора из пространства $\ K^{n+m}$ вида $\)$ будут иметь как минимум $\ m+1$ различий в компонентах. То есть набор векторов вида $\)$ образует код, обладающий свойством максимальной разнесённости. Таким кодом является, например, код Рида-Соломона.

В Whirlpool свойство максимальной разнесённости MDS матрицы означает, что общее количество меняющихся байт вектора $\ x$ и вектора $\ f=x$ не меньше $\ 8+1=9$ . Другими словами, любое изменение только одного байта $\ x$ приводит к изменению всех 8 байтов $\ f$ . В этом и состоит задача линейной диффузии .

Как уже упоминалось выше, MDS матрица в последней версии Whirlpool была изменена благодаря статье Taizo Shirai и Kyoji Shibutani . Они проанализировали MDS матрицу второй версии Whirlpool и указали на возможность повышения устойчивости Whirlpool к дифференциальному криптоанализу. Также они предложили 224 кандидата на место новой MDS матрицы . Из этого списка авторы Whirlpool выбрали вариант, наиболее легко реализуемый в аппаратном обеспечении.

Добавление ключа σ

Функция добавления ключа $\sigma: M_{8 \times 8} \to M_{8 \times 8}$ представляет собой побитовое сложение матриц состояния $\ a$ и ключа $k \in M_{8 \times 8}$ :

$\sigma=b \Leftrightarrow b_{i,j} = a_{i,j} \oplus k_{i,j}, 0 \leq i,j \leq 7.$

Константы раунда c

В каждом раунде $\ r, r > 0$ используется матрица констант $c^r \in M_{8 \times 8}$ такая, что:

$c_{0j}^r \equiv S, \qquad 0 \leq j \leq 7,$

$c_{ij}^r \equiv 0, \qquad \qquad \qquad \qquad 1 \leq i \leq 7, 0 \leq j \leq 7.$

Отсюда видно, что первая строка матрицы c является результатом применения блока подстановки S к байтовым числам $, 0 \leq j \leq 7$ .

Остальные 7 строк — нулевые.

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

Для каждого раунда $\ r$ функция раунда — это составное преобразование $\rho: M_{8 \times 8} \to M_{8 \times 8}$ , параметром k которого является матрица ключа $k \in M_{8 \times 8}$ . Описывается функция раунда следующим образом:

$\rho \equiv \sigma \circ \theta \circ \pi \circ \gamma.$

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

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

$\ K^0 = K,$

$\ K^r = \rho, r > 0.$

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

Блочный шифр W

Специальный 512-битный блочный шифр $W: M_{8 \times 8} \to M_{8 \times 8}$ в качестве параметра использует 512-битный ключ K и выполняет следующую последовательность преобразований:

$W = \left \circ \sigma,$

где ключи K,...,K порождены описанной выше процедурой расширения ключа. В хеш-функции Whirlpool число раундов R = 10.

Дополнение входного сообщения

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

Для решения данной задачи Whirlpool использует алгоритм Меркле-Дамгаарда дополнения входного сообщения. Результатом дополнения сообщения M является сообщение M', длина которого кратна 512. Пусть L — длина исходного сообщения. Тогда M' получается в несколько шагов:

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

Дополненное сообщение M' записывается в виде

$M' = \overbrace{M}^{L} \| 1 \| \overbrace{0 \dots 0}^{x} \| \overbrace{L}^{256}$