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

Сначала сообщение разбивается на блоков , ,…, по бит каждый. Для вариантов функции, возвращающих до 256 бит = 512. Для вариантов, возвращающих большие значения, = 1024.

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

, ,…,  — так называемый chaining input.

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

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

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

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

[править | править код]

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

224 00…00 00 e0
256 00…00 01 00
384 00…00 01 80
512 00…00 02 00

Для работы с сообщениями произвольной длины, используется функция . Она преобразует сообщение произвольной длины в сообщение с длиной, кратной . Для этого к сообщению сначала добавляется бит со значением 1. Далее добавляется нулевых бит, где . И наконец, добавляется 64х битовое представление числа . Это же число определяет количество блоков, на которые будет разбито сообщение.

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

[править | править код]

Сжимающая функция или функция компрессии состоит из двух -битовых перестановок и и определяется как .

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

[править | править код]

Функция выходного преобразования определяется как Ω , где  — функция, которая возвращает последние бит входного значения .

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

[править | править код]

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

Каждая перестановка выполняется раундов, в каждом из которых производятся 4 раундовых преобразования:

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

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

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

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

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

Это преобразование выполняет операцию XOR между матрицей состояния и константой, зависящей от раунда: A←A , где  — константа, зависящая от раунда. Эти константы различны для каждой перестановки P и Q:

512

1024

512

1024

где - номер раунда, представленный 8 битным значением.

Это преобразование заменяет каждый байт матрицы состояния значением, взятым из S-блока. В хеш функции Grøstl используется такой же S-блок, как и в шифре AES. Следовательно преобразование выглядит следующим образом: , где  — элемент матрицы 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


Преобразование ищет элементы в первой колонке, и элемент в первой строке.( — логическое «или»). На выход идет элемент, находящийся на их пересечении.


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]


При этом преобразовании каждая колонка матрицы А умножается на константную матрицу B в конечном поле . Матрица B определяется как

Преобразование MixBytes можно обозначить как: A←BA.

Криптостойкость

[править | править код]

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