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 бит. Вариант, возвращающий 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 блоков  m1,  m2,…, mt по l бит каждый. Для вариантов функции, возвращающих до 256 бит l = 512. Для вариантов, возвращающих большие значения, l = 1024.

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

h=(h0 , h1,…, ht) — так называемый chaining input.

Начальное значение h0 = iv.

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

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

Начальное значение[править | править вики-текст]

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

n ivn
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) = truncn(P(x) \oplus x) , где truncn(x) — функция, которая возвращает последние n бит входного значения x.

Перестановки P и Q[править | править вики-текст]

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

Каждая перестановка выполняется 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:


P512 : 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}

P1024 : 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}

Q512 : 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}

Q1024 : 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. Следовательно преобразование выглядит следующим образом: ai,jS(ai,j), где ai,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(ai,j) ищет элементы ai,j\bigwedge f0 в первой колонке, и элемент ai,j\bigwedge 0f в первой строке.(\bigwedge  — логическое «или»). На выход идет элемент, находящийся на их пересечении.


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 в конечном поле \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\timesA.

Криптостойкость[править | править вики-текст]

Надежность хеш-функции напрямую зависит от количества раундов. В результате криптоанализа удалось произвести только на первые 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

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]