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

Примеры хешей 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

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

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