Grøstl (Grøstl)

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».

Алгоритм

Сначала сообщение $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	2⁶⁴
Хеш-функция	нахождение коллизий	512	3	2¹⁹²
Функция сжатия	нахождение частичных коллизий	256	6	2¹²⁰
Функция сжатия	нахождение частичных коллизий	384	6	2¹⁸⁰
Функция сжатия	нахождение частичных коллизий	512	6	2¹⁸⁰
Перестановка	Дифференциальное свойство	256	9	2³⁶⁸
Перестановка	Дифференциальное свойство	512	8	2²⁸⁰
Перестановка	Дифференциальное свойство	512	9	2³²⁸
Перестановка	Дифференциальное свойство	512	10	2³⁹²
Выходное преобразование	Нахождение прообраза	256	6	2²⁵¹
Выходное преобразование	Нахождение прообраза	256	5	2²⁰⁶
Выходное преобразование	Нахождение прообраза	512	8	2⁴⁹⁵
Хеш-функция	нахождение псевдо-прообраза	256	5	2²⁴⁵
Хеш-функция	нахождение псевдо-прообраза	512	8	2⁵⁰⁷

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

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

Примечания

↑ 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

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

[1]

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

	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

	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

	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