Grøstl

В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (12 июля 2018)

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

Сначала сообщение ${\displaystyle M}$ разбивается на ${\displaystyle t}$ блоков ${\displaystyle m}$_{${\displaystyle 1}$}, ${\displaystyle m}$_{${\displaystyle 2}$},…,${\displaystyle m}$_{${\displaystyle t}$} по ${\displaystyle l}$ бит каждый. Для вариантов функции, возвращающих до 256 бит ${\displaystyle l}$ = 512. Для вариантов, возвращающих большие значения, ${\displaystyle l}$ = 1024.

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

${\displaystyle h}$${\displaystyle =}$${\displaystyle (}$${\displaystyle h}$_{${\displaystyle 0}$} , ${\displaystyle h}$_{${\displaystyle 1}$},…, ${\displaystyle h}$_{${\displaystyle t}$}${\displaystyle )}$ — так называемый chaining input.

Начальное значение ${\displaystyle h}$_{${\displaystyle 0}$} = ${\displaystyle iv}$.

После обработки последнего блока, ${\displaystyle l}$-битовое значение ${\displaystyle h}$_{${\displaystyle i}$} подается на вход функции преобразования Ω${\displaystyle (}$${\displaystyle h}$_{${\displaystyle i}$}${\displaystyle )}$, которая возвращает сообщение длиной ${\displaystyle n}$, такой, что ${\displaystyle 2n}$ ≤ ${\displaystyle l}$.

Таким образом результат выполнения хеш-функции ${\displaystyle H}$${\displaystyle (}$${\displaystyle M}$${\displaystyle )}$${\displaystyle =}$Ω${\displaystyle (}$${\displaystyle h}$_{${\displaystyle t}$}${\displaystyle )}$

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

${\displaystyle n}$	${\displaystyle iv}$${\displaystyle n}$
224	00…00 00 e0
256	00…00 01 00
384	00…00 01 80
512	00…00 02 00

Для работы с сообщениями произвольной длины, используется функция ${\displaystyle x*=pad(x)}$. Она преобразует сообщение ${\displaystyle x}$ произвольной длины ${\displaystyle N}$ в сообщение с длиной, кратной ${\displaystyle l}$. Для этого к сообщению сначала добавляется бит со значением 1. Далее добавляется${\displaystyle w}$ нулевых бит, где ${\displaystyle w=(-N-65)mod}$ ${\displaystyle l}$. И наконец, добавляется 64х битовое представление числа ${\displaystyle (N+w+65)/l}$. Это же число определяет количество блоков, на которые будет разбито сообщение.

Сжимающая функция или функция компрессии состоит из двух ${\displaystyle l}$-битовых перестановок ${\displaystyle P}$ и ${\displaystyle Q}$ и определяется как ${\displaystyle f(h,m)=P(h\oplus m)\oplus Q(m)\oplus h}$.

Функция выходного преобразования определяется как Ω${\displaystyle (x)=trunc}$_{${\displaystyle n}$}${\displaystyle (P(x)\oplus x)}$ , где ${\displaystyle trunc}$_{${\displaystyle n}$}${\displaystyle (x)}$ — функция, которая возвращает последние ${\displaystyle n}$ бит входного значения ${\displaystyle x}$.

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

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

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

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

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

${\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}}}$

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

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

Это преобразование выполняет операцию XOR между матрицей состояния и константой, зависящей от раунда: A←A ${\displaystyle \oplus C[i]}$, где ${\displaystyle C[i]}$ — константа, зависящая от раунда. Эти константы различны для каждой перестановки P и Q:

${\displaystyle P}$₅₁₂ ${\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}}}$

${\displaystyle P}$₁₀₂₄ ${\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}}}$

${\displaystyle Q}$₅₁₂ ${\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}}}$

${\displaystyle Q}$₁₀₂₄ ${\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}}}$

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

Это преобразование заменяет каждый байт матрицы состояния значением, взятым из S-блока. В хеш функции Grøstl используется такой же S-блок, как и в шифре AES. Следовательно преобразование выглядит следующим образом: ${\displaystyle a}$_{${\displaystyle i,j}$}←${\displaystyle S(a}$_{${\displaystyle i,j}$}${\displaystyle )}$, где ${\displaystyle a}$_{${\displaystyle i,j}$} — элемент матрицы A. А S-блок имеет вид:

Преобразование ${\displaystyle S(a}$_{${\displaystyle i,j}$}${\displaystyle )}$ ищет элементы ${\displaystyle a}$_{${\displaystyle i,j}$}${\displaystyle \bigwedge f0}$ в первой колонке, и элемент ${\displaystyle a}$_{${\displaystyle i,j}$}${\displaystyle \bigwedge 0f}$ в первой строке.(${\displaystyle \bigwedge }$ — логическое «или»). На выход идет элемент, находящийся на их пересечении.

Пусть α=[α₁, α₂,…, α₇ ] — набор целых чисел от 1 до 7. Преобразование ShiftBytes циклически сдвигает все байты в строке i матрицы состояния A на α_i позиций влево. Для перестановок P и Q эти наборы чисел различны:

• P₅₁₂: α=[0,1,2,3,4,5,6,7]
• Q₅₁₂: α=[1,3,5,7,0,2,4,6]

Соответственно для функции ShiftBytesWide:

• P₁₀₂₄: α=[0,1,2,3,4,5,6,11]
• Q₁₀₂₄: α=[1,3,5,11,0,2,4,6]

При этом преобразовании каждая колонка матрицы А умножается на константную матрицу B в конечном поле ${\displaystyle \mathbb {F} }$_{${\displaystyle 256}$}. Матрица B определяется как
${\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}}}$

Преобразование MixBytes можно обозначить как: A←B${\displaystyle \times }$A.

Надежность хеш-функции напрямую зависит от количества раундов. В результате криптоанализа удалось произвести только на первые 3 раунда. В таблице приведены некоторые результаты криптоанализа, проведенного во время финального раунда конкурса на хеш-функцию SHA-3:

Программная реализация Grøstl рассчитана в основном на 64-битный процессор, однако возможна также работа и на 32-битных процессорах. В ходе тестов, проведенных в финале конкурса NIST, производительность хеш-функции оказалась самой низкой, относительно других участников конкурса. Однако при выполнении алгоритма на микроконтроллере, скорость его работы оказалась гораздо выше, чем у конкурентов. В таблице представлена скорость работы программных реализаций разных вариантов функции.

В следующей таблице приводится 8-битная реализация на микроконтроллере ATmega163.

Значения разных вариантов хеша от пустой строки.

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 на 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