Grøstl (Groestl) — итеративная криптографическая хеш-функция. Одна из пяти финалистов конкурса SHA-3, организованного NIST. Сжимающая функция Grøstl состоит из двух фиксированных 2n-битных перестановок P и Q, структура которых заимствована у шифра AES. В частности, используется такой же S-блок. Результат работы хеш-функции может иметь длину от 8 до 512 бит с шагом 8 бит. Вариант, возвращающий n бит, называется Grøstl-n.
История Алгоритм Grøstl был специально разработан для участия в конкурсе криптографических функций SHA-3 командой криптографов из Датского технического университета. Первоначально функция называлась 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
Функция pad Для работы с сообщениями произвольной длины, используется функция . Она преобразует сообщение произвольной длины в сообщение с длиной, кратной . Для этого к сообщению сначала добавляется бит со значением 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.
Далее выполняются раундовые преобразования над матрицей А.
AddRoundConstant Это преобразование выполняет операцию XOR между матрицей состояния и константой, зависящей от раунда: A←A , где — константа, зависящая от раунда. Эти константы различны для каждой перестановки P и Q:
512
1024
512
1024
где - номер раунда, представленный 8 битным значением.
SubBytes Это преобразование заменяет каждый байт матрицы состояния значением, взятым из S-блока. В хеш функции Grøstl используется такой же S-блок, как и в шифре AES. Следовательно преобразование выглядит следующим образом: ←, где — элемент матрицы A. А S-блок имеет вид:
00 01 02 03 0405 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 7dfa 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 04c7 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 814f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db a0 e032 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79 b0 e7 c8 37 6d 8d d5 4e a9 6c 56f4 ea 65 7a ae 08 c0 ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a d070 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 f08c 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]
MixBytes При этом преобразовании каждая колонка матрицы А умножается на константную матрицу 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
Примечания
Ссылки Differential Fault Analysis on Grøstl на (на англ. яз); 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
Категория:Криптографические хеш-функции Категория:NIST hash function competition