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

Алгоритм

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

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

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

Начальное значение [math]\displaystyle{ h }[/math][math]\displaystyle{ 0 }[/math] = [math]\displaystyle{ iv }[/math].

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

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

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

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

[math]\displaystyle{ n }[/math] [math]\displaystyle{ iv }[/math][math]\displaystyle{ n }[/math]
224 00…00 00 e0
256 00…00 01 00
384 00…00 01 80
512 00…00 02 00

Функция pad

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

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

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

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

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

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

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

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

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

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

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

[math]\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} }[/math]

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

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

AddRoundConstant

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

[math]\displaystyle{ P }[/math]512 [math]\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} }[/math]

[math]\displaystyle{ P }[/math]1024 [math]\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} }[/math]

[math]\displaystyle{ Q }[/math]512 [math]\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} }[/math]

[math]\displaystyle{ Q }[/math]1024 [math]\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} }[/math]

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

SubBytes

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


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


ShiftBytes(ShiftBytesWide)

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

  • P512: α=[0,1,2,3,4,5,6,7]
  • Q512: α=[1,3,5,7,0,2,4,6]

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

  • P1024: α=[0,1,2,3,4,5,6,11]
  • Q1024: α=[1,3,5,11,0,2,4,6]


MixBytes

При этом преобразовании каждая колонка матрицы А умножается на константную матрицу B в конечном поле [math]\displaystyle{ \mathbb{F} }[/math][math]\displaystyle{ 256 }[/math]. Матрица B определяется как
[math]\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} }[/math]

Преобразование MixBytes можно обозначить как: A←B[math]\displaystyle{ \times }[/math]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

Примеры хешей 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 года.

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Grøstl&oldid=5904703