Grøstl

Grøstl
Разработчики	Сорен Стефан Томпсон, Ларс Кнудсен, Мартин Шлэффер, Кристиан Речбергер, Флориан Мендель, Кристиан Матюсевич, Праавен Гаураварам
Размер хеша	224, 256, 384, 512 (переменный, 8-512 бит)
Число раундов	9 (рекомендовано)
Тип	хеш-функция

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

История

Алгоритм Grøstl был специально разработан для участия в конкурсе криптографических функций SHA-3 командой криптографов^[1] из Датского технического университета. Первоначально функция называлась 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».

Алгоритм

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

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

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

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

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

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

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

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

${\displaystyle n}$	${\displaystyle iv}$${\displaystyle n}$
224	00…00 00 e0
256	00…00 01 00
384	00…00 01 80
512	00…00 02 00

Функция pad

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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 ${\displaystyle \oplus C[i]}$, где ${\displaystyle C[i]}$ — константа, зависящая от раунда. Эти константы различны для каждой перестановки P и Q:

${\displaystyle P}$₅₁₂ ${\displaystyle :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}}}$

${\displaystyle P}$₁₀₂₄ ${\displaystyle :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}}}$

${\displaystyle Q}$₅₁₂ ${\displaystyle :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}}}$

${\displaystyle Q}$₁₀₂₄ ${\displaystyle :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}}}$

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

SubBytes

Это преобразование заменяет каждый байт матрицы состояния значением, взятым из S-блока. В хеш функции Grøstl используется такой же S-блок, как и в шифре AES. Следовательно преобразование выглядит следующим образом: ${\displaystyle a}$_{${\displaystyle i,j}$}←${\displaystyle S(a}$_{${\displaystyle i,j}$}${\displaystyle )}$, где ${\displaystyle a}$_{${\displaystyle 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

Преобразование ${\displaystyle S(a}$_{${\displaystyle i,j}$}${\displaystyle )}$ ищет элементы ${\displaystyle a}$_{${\displaystyle i,j}$}${\displaystyle \bigwedge f0}$ в первой колонке, и элемент ${\displaystyle a}$_{${\displaystyle i,j}$}${\displaystyle \bigwedge 0f}$ в первой строке.(${\displaystyle \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 в конечном поле ${\displaystyle \mathbb {F} }$_{${\displaystyle 256}$}. Матрица B определяется как
${\displaystyle 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${\displaystyle \times }$A.

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

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

Цель атаки	Тип атаки	Количество бит на выходе	количество раундов	Количество операций
Хеш-функция	нахождение коллизий	224, 256	3	2^64
Хеш-функция	нахождение коллизий	512	3	2^192
Функция сжатия	нахождение частичных коллизий	256	6	2^120
Функция сжатия	нахождение частичных коллизий	384	6	2^180
Функция сжатия	нахождение частичных коллизий	512	6	2^180
Перестановка	Дифференциальное свойство	256	9	2^368
Перестановка	Дифференциальное свойство	512	8	2^280
Перестановка	Дифференциальное свойство	512	9	2^328
Перестановка	Дифференциальное свойство	512	10	2^392
Выходное преобразование	Нахождение прообраза	256	6	2^251
Выходное преобразование	Нахождение прообраза	256	5	2^206
Выходное преобразование	Нахождение прообраза	512	8	2^495
Хеш-функция	нахождение псевдо-прообраза	256	5	2^245
Хеш-функция	нахождение псевдо-прообраза	512	8	2^507

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

Программная реализация 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

Примеры хешей Grøstl

Значения разных вариантов хеша от пустой строки.

Grøstl-224("")
0x f2e180fb5947be964cd584e22e496242c6a329c577fc4ce8c36d34c3
Grøstl-256("")
0x 1a52d11d550039be16107f9c58db9ebcc417f16f736adb2502567119f0083467
Grøstl-384("")
0x ac353c1095ace21439251007862d6c62f829ddbe6de4f78e68d310a9205a736d8b11d99bffe448f57a1cfa2934f044a5
Grøstl-512("")
0x 6d3ad29d279110eef3adbd66de2a0345a77baede1557f5d099fce0c03d6dc2ba8e6d4a6633dfbd66053c20faa87d1a11f39a7fbe4a6c2f009801370308fc4ad8

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

Grøstl-256("The quick brown fox jumps over the lazy dog")
0x 8c7ad62eb26a21297bc39c2d7293b4bd4d3399fa8afab29e970471739e28b301
Grøstl-256("The quick brown fox jumps over the lazy dog.")
0x f48290b1bcacee406a0429b993adb8fb3d065f4b09cbcdb464a631d4a0080aaf

Grøstl-512("The quick brown fox jumps over the lazy dog")
0x badc1f70ccd69e0cf3760c3f93884289da84ec13c70b3d12a53a7a8a4a513f99715d46288f55e1dbf926e6d084a0538e4eebfc91cf2b21452921ccde9131718d
Grøstl-512("The quick brown fox jumps over the lazy dog.")
0x 518a55cc274fc887d8dcbd0bb24000395f6d3be62445d84cc9e85d419161a968268e490f7537e475e57d8c009b0957caa05882bc8c20ce22d50caa2106d0dcfd

Примечания

1. Hash function Grøstl — SHA-3 candidate  (неопр.). Дата обращения: 13 декабря 2013. Архивировано 11 октября 2013 года.

Ссылки

• 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