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
Примечания
- ↑ 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
В статье не хватает ссылок на источники (см. также рекомендации по поиску). |