Grøstl

Шаблон:Карточка хеш функции Grøstl (Groestl) — итеративная криптографическая хеш-функция. Одна из пяти финалистов конкурса SHA-3, организованного NIST. Сжимающая функция Grøstl состоит из двух фиксированных 2n-битных перестановок P и Q, структура которых заимствована у шифра AES. В частности, используется такой же S-блок. Результат работы хеш-функции может иметь длину от 8 до 512 бит. Вариант, возвращающий n бит, называется Grøstl-n.

История

Алгоритм Grøstl был специально разработан для участия в конкурсе криптографических функций SHA-3 командой криптографов из Датского технического университета. Первоначально функция называлась Grøstl-0. Однако, для участия в финале были увеличены структурные различия между перестановками. Были изменены значения ShiftBytes в перестановке Q. Также изменениям подверглись раундовые константы в P и Q. Обновленная хеш-функция получила название Grøstl. Однако, показав хорошую криптостойкость, по ряду показателей она уступала другим участникам финального раунда и не смогла стать победителем.

Происхождение названия

Грёстль — блюдо австрийской кухни. По рецепту очень близко к блюду, которое в США называют «Hash». Буква «ö» в названии функции была заменена на букву «ø» из датского алфавита, которое имеет такое же произношение.

Особенности

Grøstl — байт-ориентированная SP-сеть. По своему строению она значительно отличается от алгоритмов семейства SHA. Многие компоненты хеш-функции заимствованы у шифра AES. Так же как и у AES, перестановки разработаны с использованием метода Wide Trail design strategy, главными принципами которого являются наличие у блочного шифра:

• Нелинейных замен (то есть наличие хорошего S-блока)
• Линейных преобразований (для того, чтобы обеспечить хорошую диффузию и нелинейность S-блока)
• Сложения ключей (обычно с помощью XOR)

Размер внутреннего состояния функции значительно больше, чем размер выходных данных. Это так называемый «wide-pipe construction».

Алгоритм

Сначала сообщение $M$ разбивается на $t$ блоков $m$_$1$, $m$_$2$,…,$m$_$t$ по $l$ бит каждый. Для вариантов функции, возвращающих до 256 бит $l$ = 512. Для вариантов, возвращающих большие значения, $l$ = 1024.

Далее, строится хеш-функция, используя рекуррентный способ вычисления. Каждый блок $m$ обрабатывается последовательно сжимающей функцией $f$ по формуле $h$_$i$$=$ $f$$($$m$_$i$ , $h$_$i-1$$)$.

$h$$=$$($$h$_$0$ , $h$_$1$,…, $h$_$t$$)$ — так называемый chaining input.

Начальное значение $h$_$0$ = $iv$.

После обработки последнего блока, $l$-битовое значение $h$_$i$ подается на вход функции преобразования Ω$($$h$_$i$$)$, которая возвращает сообщение длиной $n$, такой, что $2n$ ≤ $l$.

Таким образом результат выполнения хеш-функции $H$$($$M$$)$$=$Ω$($$h$_$t$$)$

Начальное значение

Начальному значению $iv$_$n$ функции Grøstl-n присваивается $l$-битовое представление числа n. В таблице показаны начальные значения для разных вариантов хеш-функции.

$n$	$iv$$n$
224	00…00 00 e0
256	00…00 01 00
384	00…00 01 80
512	00…00 02 00

Функция pad

Для работы с сообщениями произвольной длины, используется функция $x*=pad(x)$. Она преобразует сообщение $x$ произвольной длины $N$ в сообщение с длиной, кратной $l$. Для этого к сообщению сначала добавляется бит со значением 1. Далее добавляется$w$ нулевых бит, где $w=(-N-65)mod$ $l$. И наконец, добавляется 64х битовое представление числа $(N+w+65)/l$. Это же число определяет количество блоков, на которые будет разбито сообщение.

Сжимающая функция

Сжимающая функция или функция компрессии состоит из двух $l$-битовых перестановок $P$ и $Q$ и определяется как $f(h,m)=P(h\oplus m)\oplus Q(m)\oplus h$.

Выходное преобразование

Функция выходного преобразования определяется как Ω$(x)=trunc$_$n$$(P(x)\oplus x)$ , где $trunc$_$n$$(x)$ — функция, которая возвращает последние $n$ бит входного значения $x$.

Перестановки P и Q

Функция сжатия Grøstl может работать с короткими сообщениями (512 бит) и с длинными (1024 бит). Соответственно всего существует 4 перестановки $P$_$512$, $Q$_$512$ и $P$_$1024$, $Q$_$1024$.

Каждая перестановка выполняется $R$ раундов, в каждом из которых производятся 4 раундовых преобразования:

• AddRoundConstant
• SubBytes
• ShiftBytes(или ShiftBytesWide для длинных дайджестов)
• MixBytes

Эти преобразования управляют состоянием, которое представляется матрицей А, содержащей в каждой ячейке 1 байт информации. Для работы с короткими дайджестами сообщений матрица имеет размер 8Х8, для длинных дайджестов — 8Х16.

Сначала матрица A заполняется последовательностью байт . Например для последовательности 00 01 02 … 3f матрица A выглядит следующим образом.

${\begin{bmatrix}00&08&10&18&20&28&30&38\\01&09&11&19&21&29&31&39\\02&0a&12&1a&22&2a&32&3a\\03&0b&13&1b&23&2b&33&3b\\04&0c&14&1c&24&2c&34&3c\\05&0d&15&1d&25&2d&35&3d\\06&0e&16&1e&26&2e&36&3e\\07&0f&17&1f&27&2f&37&3f\end{bmatrix}}$

Аналогичным образом заполняется матрица 8 X 16.

Далее выполняются раундовые преобразования над матрицей А.

AddRoundConstant

Это преобразование выполняет операцию XOR между матрицей состояния и константой, зависящей от раунда: A←A $\oplus C[i]$, где $C[i]$ — константа, зависящая от раунда. Эти константы различны для каждой перестановки P и Q:

$P$₅₁₂ $:C[i]={\begin{bmatrix}00\oplus i&10\oplus i&20\oplus i&30\oplus i&40\oplus i&50\oplus i&60\oplus i&70\oplus i\\00&00&00&00&00&00&00&00\\00&00&00&00&00&00&00&00\\00&00&00&00&00&00&00&00\\00&00&00&00&00&00&00&00\\00&00&00&00&00&00&00&00\\00&00&00&00&00&00&00&00\\00&00&00&00&00&00&00&00\end{bmatrix}}$

$P$₁₀₂₄ $:C[i]={\begin{bmatrix}00\oplus i&10\oplus i&20\oplus i&30\oplus i&40\oplus i&50\oplus i&60\oplus i&70\oplus i&\cdots &f0\oplus i\\00&00&00&00&00&00&00&00&\cdots &00\\00&00&00&00&00&00&00&00&\cdots &00\\00&00&00&00&00&00&00&00&\cdots &00\\00&00&00&00&00&00&00&00&\cdots &00\\00&00&00&00&00&00&00&00&\cdots &00\\00&00&00&00&00&00&00&00&\cdots &00\\00&00&00&00&00&00&00&00&\cdots &00\end{bmatrix}}$

$Q$₅₁₂ $:C[i]={\begin{bmatrix}ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff&ff&ff&ff&ff&ff&ff&ff\\ff\oplus i&ef\oplus i&df\oplus i&cf\oplus i&bf\oplus i&af\oplus i&9f\oplus i&8f\oplus i\end{bmatrix}}$

$Q$₁₀₂₄ $:C[i]={\begin{bmatrix}ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff&ff&ff&ff&ff&ff&ff&ff&\cdots &ff\\ff\oplus i&ef\oplus i&df\oplus i&cf\oplus i&bf\oplus i&af\oplus i&9f\oplus i&8f\oplus i&\cdots &0f\oplus i\end{bmatrix}}$

где $i$- номер раунда, представленный 8 битным значением.

SubBytes

Это преобразование заменяет каждый байт матрицы состояния значением, взятым из S-блока. В хеш функции Grøstl используется такой же S-блок, как и в шифре AES. Следовательно преобразование выглядит следующим образом: $a$_$i,j$←$S(a$_$i,j$$)$, где $a$_$i,j$ — элемент матрицы A. А S-блок имеет вид:

	00	01	02	03	04	05	06	07	08	09	0a	0b	0c	0d	0e	0f
00	63	7c	77	7b	f2	6b	6f	c5	30	01	67	2b	fe	d7	ab	76
10	ca	82	c9	7d	fa	59	47	f0	ad	d4	a2	af	9c	a4	72	c0
20	b7	fd	93	26	36	3f	f7	cc	34	a5	e5	f1	71	d8	31	15
30	04	c7	23	c3	18	96	05	9a	07	12	80	e2	eb	27	b2	75
40	09	83	2c	1a	1b	6e	5a	a0	52	3b	d6	b3	29	e3	2f	84
50	53	d1	00	ed	20	fc	b1	5b	6a	cb	be	39	4a	4c	58	cf
60	d0	ef	aa	fb	43	4d	33	85	45	f9	02	7f	50	3c	9f	a8
70	51	a3	40	8f	92	9d	38	f5	bc	b6	da	21	10	ff	f3	d2
80	cd	0c	13	ec	5f	97	44	17	c4	a7	7e	3d	64	5d	19	73
90	60	81	4f	dc	22	2a	90	88	46	ee	b8	14	de	5e	0b	db
a0	e0	32	3a	0a	49	06	24	5c	c2	d3	ac	62	91	95	e4	79
b0	e7	c8	37	6d	8d	d5	4e	a9	6c	56	f4	ea	65	7a	ae	08
c0	ba	78	25	2e	1c	a6	b4	c6	e8	dd	74	1f	4b	bd	8b	8a
d0	70	3e	b5	66	48	03	f6	0e	61	35	57	b9	86	c1	1d	9e
e0	e1	f8	98	11	69	d9	8e	94	9b	1e	87	e9	ce	55	28	df
f0	8c	a1	89	0d	bf	e6	42	68	41	99	2d	0f	b0	54	bb	16

Преобразование $S(a$_$i,j$$)$ ищет элементы $a$_$i,j$$\bigwedge f0$ в первой колонке, и элемент $a$_$i,j$$\bigwedge 0f$ в первой строке.($\bigwedge$ — логическое «или»). На выход идет элемент, находящийся на их пересечении.

ShiftBytes(ShiftBytesWide)

Пусть α=[α₁, α₂,…, α₇ ] — набор целых чисел от 1 до 7. Преобразование ShiftBytes циклически сдвигает все байты в строке i матрицы состояния A на α_i позиций влево. Для перестановок P и Q эти наборы чисел различны:

• P₅₁₂: α=[0,1,2,3,4,5,6,7]
• Q₅₁₂: α=[1,3,5,7,0,2,4,6]

Соответственно для функции ShiftBytesWide:

• P₁₀₂₄: α=[0,1,2,3,4,5,6,11]
• Q₁₀₂₄: α=[1,3,5,11,0,2,4,6]

MixBytes

При этом преобразовании каждая колонка матрицы А умножается на константную матрицу B в конечном поле $\mathbb {F}$_$256$. Матрица B определяется как
$B={\begin{bmatrix}02&02&03&04&05&03&05&07\\07&02&02&03&04&05&03&05\\05&07&02&02&03&04&05&03\\03&05&07&02&02&03&04&05\\05&03&05&07&02&02&03&04\\04&05&03&05&07&02&02&03\\03&04&05&03&05&07&02&02\\02&03&04&05&03&05&07&02\end{bmatrix}}$

Преобразование MixBytes можно обозначить как: A←B$\times$A.

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

Надежность хеш-функции напрямую зависит от количества раундов. В результате криптоанализа удалось произвести только на первые 3 раунда. В таблице приведены некоторые результаты криптоанализа, проведенного во время финального раунда конкурса на хеш-функцию SHA-3:

Цель атаки	Тип атаки	Количество бит на выходе	количество раундов	Количество операций
Хеш-функция	нахождение коллизий	224, 256	3	264
Хеш-функция	нахождение коллизий	512	3	2192
Функция сжатия	нахождение частичных коллизий	256	6	2120
Функция сжатия	нахождение частичных коллизий	384	6	2180
Функция сжатия	нахождение частичных коллизий	512	6	2180
Перестановка	Дифференциальное свойство	256	9	2368
Перестановка	Дифференциальное свойство	512	8	2280
Перестановка	Дифференциальное свойство	512	9	2328
Перестановка	Дифференциальное свойство	512	10	2392
Выходное преобразование	Нахождение прообраза	256	6	2251
Выходное преобразование	Нахождение прообраза	256	5	2206
Выходное преобразование	Нахождение прообраза	512	8	2495
Хеш-функция	нахождение псевдо-прообраза	256	5	2245
Хеш-функция	нахождение псевдо-прообраза	512	8	2507

Производительность

Программная реализация Grøstl рассчитана в основном на 64-битный процессор, однако возможна также работа и на 32-битных процессорах. В ходе тестов, проведенных в финале конкурса NIST, производительность хеш-функции оказалась самой низкой, относительно других участников конкурса. Однако при выполнении алгоритма на микроконтроллере, скорость его работы оказалась гораздо выше, чем у конкурентов. В таблице представлена скорость работы программных реализаций разных вариантов функции.

Процессор	Вариант функции	Скорость (цикл/байт)
Intel Core i7 M620	Grøstl-224/256	12,45
Intel Core i7 M620	Grøstl-384/512	17,85

В следующей таблице приводится 8-битная реализация на микроконтроллере ATmega163.

Хеш-функция	процессор	Память	Скорость (цикл/байт)
Grøstl-256	ATmega163	994	469
Grøstl-256	ATmega163	226	531
Grøstl-256	ATmega163	164	760

Примечания

• Differential Fault Analysis on Grøstl на IEEE Xplore;
• Improved Collision Attacks on the Reduced-Round Grøstl Hash Function на ResearchGate;
• On the Indifferentiability of the Grøstl Hash Function на Springer Science+Business Media

Ссылки

• Сайт Grøstl
• Спецификация Grøstl
• Сайт NIST. Конкурс на алгоритм SHA-3
• Результат финала конкурса на алгоритм SHA-3
• Wide Trail design strategy