Криптоанализ ГОСТ 34.11-2012

Криптоанализ ГОСТ-Р 34.11-2012

ГОСТ Р 34.11-2012 Править

ГОСТ Р 34.11-2012 (неофициальное название — Стрибог) — российский криптографический стандарт на хеш-функцию, введённый 1 января 2013 года вместо устаревшего ГОСТ Р 34.11-94.

Данная хеш-функция основана на схеме Меркла-Дамгора.

Для хеширования данные разбиваются на блоки размером 512 бит, при необходимости блок дополняется вектором $\text{[math]}$ $\text{[math]}$ $(0..01)$ такой длины, чтобы размер блока стал равным 512 бит.

Затем для каждого блока итеративно применяется функция сжатия. После этого проводится ещё две итерации — для длины входного сообщения и для контрольной суммы всех блоков, из которых состояло сообщение.

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

Выходные данные представляют собой последовательность длиной 512 или 256 бит.

Функция сжатия Править

В основу функции сжатия положен 12-раундовый AES-подобный шифр (соответствие было показано, например, в работе^[1] А.Казимирова и В.Казимировой). Важной частью функции сжатия является XSPL-преобразование, являющееся композицией четырёх функций:

X — операция сложения по модулю 2 с раундовым ключом или раундовой константой (в зависимости от того, получаем ли мы шифр блока сообщения или получаем раундовый ключ)
S — нелинейная замена каждого байта блока некоторым другим по стандартной таблице подстановок.
P — перестановка байтов блока по определённому стандартом порядку.
L — линейное преобразование, эквивалентное умножению восьми 64-битных векторов на определённую стандартом матрицу.

В работе^[1] утверждается, что с помощью приведения функции сжатия к AES-подобному виду, можно показать устойчивость функции сжатия и, соответственно, всей хеш-функции к атакам, основанным на методах дифференциального и линейного криптоанализа. Однако, вместо операции ShiftRows, характерной для структур, основанных на AES, используется линейное преобразование — матричная перестановка. И, хотя с момента разработки и введения стандарта прошло не так много времени, уже появилось несколько работ, показывающих, что такое решение, вероятно, приводит к большей уязвимости.

Атака рикошетом Править

Данная атака (англ. Rebound Attack) была представлена в 2009 году Менделем в качестве атаки на хеш-функции, основанные на AES-подобных шифрах, такие, как Whirlpool и Grøstl, является статистической.

В этой атаке криптографический примитив E делится на три части: $\text{[math]}$ $\text{[math]}$ $E=E_{fw}\circ E_{in}\circ E_{bw}$ , а сама атака состоит из двух частей: внутренней фазы (inbound phase) и внешней (outbound phase).

Внутренняя фаза Править

Данная часть (иногда называющаяся match-in-the-middle phase — «совпадение посередине») начинается с нескольких выбранных входных/выходных разностей для E_in, которые затем подвергаются линейным преобразованиям в прямом и обратном направлениях. Под разностями (реже употребляется термин «дифференциалы») здесь понимается результат операции сложения по модулю 2. На основе этого генерируются всевозможные пары значений, которые удовлетворяют выбранным значениям разностей. Эти значения являются «начальными данными» для следующей части.

Внешняя фаза Править

Данные, полученные на предыдущем шаге, «продвигаются» в прямом и обратном направлениях (преобразования E_fw и E_bw), после чего ищутся совпадения для поиска коллизий или «близких коллизий» (англ. near-collision).

Функция сжатия «ГОСТ Р» Править

В работе^[2] показано построение атаки, выявляющей коллизию, на усечённую функцию сжатия с 4.5, 5.5, 7.5 и 9.5 раундами. $\text{[math]}$ $\text{[math]}$ $i$ -м раундом называется последовательность преобразований $\text{[math]}$ $\text{[math]}$ $X[k_{i+1}]\circ L\circ P\circ S$ , где $\text{[math]}$ $\text{[math]}$ $(k_{i+1})$ -раундовый ключ, за половину раунда в данных атаках считают последовательность преобразований $\text{[math]}$ $\text{[math]}$ $P\circ S$ .

Оценка эффективности атак:

Количество раундов	Количество операций / Затраты на память
$\text{[math]}$ $\text{[math]}$ $4.5$	$\text{[math]}$ $\text{[math]}$ $2^{64}/2^{16}$
$\text{[math]}$ $\text{[math]}$ $5.5$	$\text{[math]}$ $\text{[math]}$ $2^{64}/2^{64}$
$\text{[math]}$ $\text{[math]}$ $7.5$	$\text{[math]}$ $\text{[math]}$ $2^{128}/2^{16}$
$\text{[math]}$ $\text{[math]}$ $9.5$	$\text{[math]}$ $\text{[math]}$ $2^{240}/2^{16}$ ( $\text{[math]}$ $\text{[math]}$ $2^{176}/2^{128}$ )

Далее показан пример построения «атаки рикошетом» для функции сжатия, усечённой до 4,5 раундов.

Атака на 4.5 раундовую функцию сжатия «ГОСТ Р» Править

Предлагается следующий способ разбиения на внутреннюю и внешнюю фазы:

Обозначения:

В скобках записаны преобразования X, L, S, P, использующиеся в функции сжатия «Стрибога», они описаны выше.

m — сообщение или его блок, проходящий сквозь функцию сжатия.

R с различными индексами — состояние блока, проходящего сквозь функцию сжатия.

Внутренняя: $\text{[math]}$ $\text{[math]}$ $R_{2}^{P}\longrightarrow (L\circ X[k_{3}])\longrightarrow R_{3}\longrightarrow (S)\longleftarrow R_{3}^{S}\longleftarrow (P\circ L)\longleftarrow R_{3}^{L}$

Внешняя: $\text{[math]}$ $\text{[math]}$ $m\longleftarrow (X[k_{1}])\longleftarrow R_{1}\longleftarrow (S\circ P\circ L\circ X[k_{2}])\longleftarrow R_{2}(S\circ P)\longleftarrow INBOUND\longrightarrow$

$\text{[math]}$ $\text{[math]}$ $\longrightarrow (X[k_{4}]\circ S\circ P\circ L\circ X[k_{5}])\longrightarrow R_{5}\longrightarrow (S\circ P)\longrightarrow R_{5}^{P}\longrightarrow XOR(h_{i-1})\longrightarrow XOR(m)\longrightarrow h'$

Здесь $\text{[math]}$ $\text{[math]}$ $h_{i-1}$ и $\text{[math]}$ $\text{[math]}$ $h_{i}$ — т. н. «сцепленная переменная» (chaining variable) — значения функции сжатия для $\text{[math]}$ $\text{[math]}$ $(i-1)$ и $\text{[math]}$ $\text{[math]}$ $i$ блоков сообщения соответственно.

Внутренняя фаза Править

Данный этап начинается с выбора 8-байтовой разности в R₂^P и R₃^L (Здесь под разностями так же подразумевается результат сложения по модулю 2). Далее мы подвергаем эти разности преобразованиям в прямом и обратном направлениях для получения R₃ и R₃^S соответственно. Из свойств L-преобразования следует, что мы получим полностью активное состояние и в R₃, и R₃^S. Далее, с помощью таблицы распределения разностей для S-преобразования (SBox Difference Disrtibution Table) ищутся решения, удовлетворяющие входной/выходной разности из равенства $\text{[math]}$ $\text{[math]}$ $S(x)\oplus S(x\oplus a)=b$ . В среднем ожидается нахождение одного решения для одной пары разностей (a, b).

Внешняя фаза Править

Теперь нужно использовать значения, вычисленные на предыдущем шаге, и точно так же провести вычисления в обоих направлениях. Разности при этом проявятся только в первых столбцах состояний R₁ и R₅^p (по 8 байт в каждом).

Функция сжатия работает следующим образом: $\text{[math]}$ $\text{[math]}$ $h'=h\oplus E_{4.5}(k,m)\oplus m$ . Следовательно, для одинаковых h и k коллизия получится автоматически, если разности m и E(k, m) равны. Вероятность этого равна 2⁻⁶⁴. Поэтому нужно генерировать 2⁶⁴ точек, а хранить только таблицу распределения разностей для S-преобразования(уже упоминавшийся SBox Difference Distribution Table) размером 256х256 байт, так что временная сложность построения коллизии для такой функции составляет 2⁶⁴ при затратах на память в 2¹⁶ байт. В работах^[2] и^[3] данная атака улучшена и проведена на функции сжатия, усечённой до 5.5, 7.5 и 9.5 раундов.

Интегральный различитель Править

Вместе с проверкой на устойчивость к дифференциальным атакам так же исследовалась и устойчивость к интегральным атакам. В частности, искался интегральный различитель. Вкратце, интегральным различителем называется атака, позволяющая выяснить, действительно ли в качестве функции сжатия используется функция, вид которой был предположен аналитиком, а не какая-то иная. В работе^[4] были получены различители для 6.5 и 7.5 раундов внутренней перестановки и для 7-раундовой функции сжатия. Однако, удалось получить более сильный результат для 10-раундовой функции сжатия^[2]. Результат, полученный с помощью атаки на 9.5-раундовую функцию сжатия, используют для функции сжатия, усечённой до 10 раундов. Тогда все разности на входе лежат в пространстве размерности 2⁶⁴, а на выходе — 2¹²⁸ (вследствие свойств преобразований L и P). Таким образом, временная сложность проверки для нашей функции сжатия составляет 2¹⁷⁶ с затратами по памяти в 2¹⁶ байт, или 2¹²⁸ по времени и 2¹²⁸ по памяти, в то время, как для произвольной функции нам придётся произвести 2^512-64-128=2³²⁰ вычислений, чтобы получить такое же отображение разностей на входе и на выходе. В работе^[3] также описано подробное построение различителя для 9.5-раундовой функции сжатия.

Построение мультиколлизий Править

k-коллизией называется нахождение k открытых текстов, имеющих одно значение хеш-суммы. Считается, что для идеальной хеш-функции временная сложность поиска обычной (парной) коллизии составляет 2^n/2 (вследствие парадокса «дней рождения»), в то время, как поиск k-коллизии для такой функции составит 2^{n*(k — 1) / k}, что при больших k приведёт к 2ⁿ.

Однако, Антуан Жу (Antoine Joux) в работе, посвящённой поиску мультиколлизий (k-коллизий при $\text{[math]}$ $\text{[math]}$ $k>2$ )^[5] показал оригинальный способ построения мультиколлизий для хеш-функций, основанных на итеративной функции сжатия, за меньшее, чем 2^n*(k-1)/k время.

В своей работе он исходил из того, что криптоаналитику уже известен способ найти парную коллизию, то есть, у него есть доступ к некоторой функции C, которая получает на вход значение «сцепленной переменной» h и генерирует два блока — B и B' такие, что $\text{[math]}$ $\text{[math]}$ $f(h,B)=f(h,B')$ , где f — функция сжатия.

Далее, покажем, что за два обращения к этой функции мы можем получить 4-коллизию:

Положим $\text{[math]}$ $\text{[math]}$ $h_{0}=\mathrm {IV}$ (Initial Value — начальное значение, определённое либо стандартом хеш-функции, либо её реализацией) и получим $\text{[math]}$ $\text{[math]}$ $(B_{0},B'_{0})=C(h_{0})$ . Исходя из свойств С: $\text{[math]}$ $\text{[math]}$ $f(IV,B_{0})=f(IV,B'_{0})$
Обозначим $\text{[math]}$ $\text{[math]}$ $f(IV,B_{0})=h_{1}$ , и с помощью функции C найдём блоки $\text{[math]}$ $\text{[math]}$ $(B_{1},B'_{1})=C(h_{1})$ .

Отсюда получаем: $\text{[math]}$ $\text{[math]}$ $f(h_{1},B_{1})=f(h_{1},B'_{1})=$

$\text{[math]}$ $\text{[math]}$ $=f(f(IV,B_{0}),B_{1})=f(f(IV,B'_{0}),B_{1})=f(f(IV,B_{0}),B'_{1})=f(f(IV,B'_{0}),B'_{1})$

Следовательно, мы получили 4 сообщения $\text{[math]}$ $\text{[math]}$ $B_{0}|B_{1},B'_{0}|B_{1},B_{0}|B'_{1},B'_{0}|B'_{1}$ , имеющих одинаковую хеш-сумму. Аналогично мы можем показать, что за t обращений к функции С получается 2^t коллизий.

Считая, что поиск одной парной коллизии (иначе говоря, время работы функции С) есть $\text{[math]}$ $\text{[math]}$ $2^{n/2}$ , получаем, что за $\text{[math]}$ $\text{[math]}$ $t*2^{n/2}$ можно сгенерировать $\text{[math]}$ $\text{[math]}$ $2^{t}$ сообщений, дающих одно значение хеш-суммы.

Этот способ был взят за основу в работе^[2]. Авторы показали, что данная атака применима и к функции сжатия «ГОСТ Р», и она позволяет найти k-коллизии для сообщений длиной в $\text{[math]}$ $\text{[math]}$ $t$ блоков, где $\text{[math]}$ $\text{[math]}$ $176<t<2^{256}$ за $\text{[math]}$ $\text{[math]}$ $2^{(\log _{2}t+256)*(k-1)/k}$ операций.

См. также Править

Примечания Править

↑ ¹ ² [1] А.Казимиров, В.Казимирова, «Algebraic Aspects of the Russian Hash Standard GOST R 34.11-2012», link Архивная копия от 31 января 2014 на Wayback Machine
↑ ¹ ² ³ ⁴ [2] Z.Wang, H.Yu, X.Wang, «Cryptanalysis of GOST R Hash Function», 2013 г. link Архивная копия от 31 января 2014 на Wayback Machine
↑ ¹ ² [3] B.Ma, B.Li, R.Hao, X.Li, «Improved Cryptanalysis on Reduced-round GOST and Whirlpool Hash Function», 2013, link Архивная копия от 21 апреля 2017 на Wayback Machine
↑ [4] R.AlTawy, A.M.Youssef, «Integral Distinguishers for Reduced-Round Stribog», link Архивная копия от 31 января 2014 на Wayback Machine
↑ [5] A.Joux, «Multicollisions in iterated hash functions», Advances in Cryptology — CRYPTO 2004

[first-1] ¹ ² [1] А.Казимиров, В.Казимирова, «Algebraic Aspects of the Russian Hash Standard GOST R 34.11-2012», link Архивная копия от 31 января 2014 на Wayback Machine

[second-2] ¹ ² ³ ⁴ [2] Z.Wang, H.Yu, X.Wang, «Cryptanalysis of GOST R Hash Function», 2013 г. link Архивная копия от 31 января 2014 на Wayback Machine

[third-3] ¹ ² [3] B.Ma, B.Li, R.Hao, X.Li, «Improved Cryptanalysis on Reduced-round GOST and Whirlpool Hash Function», 2013, link Архивная копия от 21 апреля 2017 на Wayback Machine

[fourth-4] [4] R.AlTawy, A.M.Youssef, «Integral Distinguishers for Reduced-Round Stribog», link Архивная копия от 31 января 2014 на Wayback Machine

[fifth-5] [5] A.Joux, «Multicollisions in iterated hash functions», Advances in Cryptology — CRYPTO 2004

[1]

[2]

[3]

[4]

[5]