Атака по полному двудольному графу

Атака по полному двудольному графу (англ. Biclique attack) — одна из разновидностей атаки «встречи посередине»^[1]. В данной атаке используется структура полного двудольного графа для увеличения количества попыток атаки посредника. Так как эта атака основа на методе атаки посредника, то она применима как к блочным шифрам, так и к криптографическим хеш-функциям. Данная атака известна тем, что позволяет вскрыть шифры AES^[2] и IDEA^[3], хотя по скорости лишь немного обгоняет метод полного перебора. Вычислительная сложность атаки составляет ${\displaystyle 2^{126.1}}$, ${\displaystyle 2^{189.7}}$ и ${\displaystyle 2^{254.4}}$ для AES128, AES192 и AES256 соответственно. Так как вычислительная сложность – теоретическое значение, то это означает, что AES не был взломан и его использование остается относительно безопасным. Также эта атака поставила под сомнение достаточность количества раундов, используемых в AES.

История

Метод атаки посредника был впервые предложен Диффи и Хеллманом в 1977 году в процессе обсуждения свойств алгоритма DES.^[4] Они рассуждали о том, что размер ключа был слишком мал, и что повторное использование DES с разными ключами могло быть решением данной проблемы. Однако, было предложено не использовать "double DES", а сразу применять как минимум triple DES из-за особенностей атаки посредника. С тех пор, как Диффи и Хеллман предложили метод атаки посредника, появилось много вариаций, которые могут использоваться, когда классический вариант MITM неприменимы. Идея атаки по полному двудольному графу была впервые высказана Хоратовичем, Рехбергером и Савельевой для варианта с использованием хеш-функций.^[5] Впоследствии Богданов, Хоратович и Рехбергер опубликовали атаку на AES, в которой показали, как можно применить концепцию полного двудольного графа к секретному ключу, включающий в себя блочный шифр^[6].

Полный двудольный граф

Основная статья: Полный двудольный граф

В атаке посредника биты ключей ${\displaystyle K_{1}}$ и ${\displaystyle K_{2}}$, соответствующие первому и второму шифрам подстановки, должны быть не зависимы друг от друга, иначе совпадающие промежуточные значения открытого и зашифрованного текстов не смогут быть вычислены независимо в атаке посредника. Это свойство часто бывает трудно использовать в течение большого количества раундов, за счет диффузии атакуемого шифра.

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

В данном случае, полный двудольный граф помогает в решении этой проблемы. Например, если проводить 7 раундов атаки посредника на AES, и затем использовать полный двудольный граф длиной 3 (покрывающий 3 итерации шифра), то будет возможность сопоставить промежуточное состояние в начале 7 итерации с промежуточным состоянием последней итерации (с 10, в случае с AES128). Таким образом, получается атака на все раунды шифра, хотя в классической атаке посредника это могло быть невозможно.

Суть атаки по полному двудольному графу состоит в том, чтобы построить эффективный полный двудольный граф, который в зависимости от битов ключей ${\displaystyle K_{1}}$ и ${\displaystyle K_{2}}$ мог сопоставлять текущее промежуточное значение соответствующему шифртексту.

Построение полного двудольного графа

Данный метод был предложен Богдановым, Ховратовичем и Рехбергером в работе Biclique Cryptanalysis of the Full AES.

Необходимо помнить, что основная функция полного двудольного графа состоит в том, чтобы строить связи между состояниями ${\displaystyle S}$ и шфиротекстами ${\displaystyle C}$, используя ключи ${\displaystyle K[i,j]}$: Построение:
Первый шаг: Выбираем состояние(${\displaystyle S_{0}}$), шифротекст(${\displaystyle C_{0}}$) и ключ(${\displaystyle K[0,0]}$) так, что: ${\displaystyle S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}}$, где ${\displaystyle f}$ — это функция, которая отображает состояние в шифротекст, использую данный ключ.

Второй шаг: Выбирается два множества ключей, каждое размером ${\displaystyle 2^{d}}$, таким образом, что:

• Первое множество ключей — это ключи, которые удовлетворяют дифференциальным требованиям функции ${\displaystyle f}$ на основе базовые вычислений: ${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}}$
• Второе множество ключей — это ключи, которые удовлетворяют дифференциальным требованиям функции ${\displaystyle f}$ на основе базовые вычислений: ${\displaystyle \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0}$

Третий шаг: Заметим, что
${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}}$,
Также легко заметить, что кортеж ${\displaystyle (S_{0},C_{0},K[0,0])}$,так же удовлетворяем обоим дифференциалам. Подставляя ${\displaystyle S_{0},C_{0}}$ ${\displaystyle K[0,0]}$ в любое из определений, получим ${\displaystyle 0{\xrightarrow[{f}]{0}}0}$, где ${\displaystyle \Delta _{0}=0,\nabla _{0}=0}$ и ${\displaystyle \Delta _{0}^{K}=0}$.
Это означает, что к кортежу, полученному из базовых вычислений, также можно применять операцию XOR : ${\displaystyle S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}}$

Четвертый шаг: Легко заметить, что:
${\displaystyle S_{j}=S_{0}\oplus \nabla _{j}}$
${\displaystyle K[i,j]=K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}$
${\displaystyle C_{i}=C_{0}\oplus \Delta _{i}}$
Таким образом, имеем:
${\displaystyle S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$
Что совпадает с определением функции полного двудольного графа, показанной выше:
${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

Таким образом, можно создать полный двудольный граф размера ${\displaystyle 2^{2d}}$(${\displaystyle 2^{2d}}$, так как ${\displaystyle 2^{d}}$ ключей первого множества необходимо соединить с ${\displaystyle 2^{d}}$ ключами второго множества). Это означает, что граф размером ${\displaystyle 2^{2d}}$ можно построить, используя ${\displaystyle 2*2^{d}}$ вычислений дифференциалов ${\displaystyle \Delta _{i}}$ и ${\displaystyle \nabla _{j}}$ и функции ${\displaystyle f}$. Если ${\displaystyle \Delta _{i}\neq \nabla _{j}}$ для ${\displaystyle i+j>0}$ , тогда все ключи ${\displaystyle K[i,j]}$ будут различными во всем графе.

Криптографический анализ атаки

1. Криптоаналитик собирает все возможные ключи в подмножества ключей размером ${\displaystyle 2^{2d}}$, где ${\displaystyle d}$ некоторое число. Ключ в группе обозначается как ${\displaystyle K[i,j]}$ в матрице размера ${\displaystyle 2^{d}\times 2^{d}}$. Далее криптоаналитик разделят шифр на два шифра подстановки, ${\displaystyle f}$ и ${\displaystyle g}$ (такие, что ${\displaystyle E=f\circ g}$), так же, как и в атаке посредника. Множества ключей для каждого шифра подстановки имеют мощности ${\displaystyle 2^{d}}$, и обозначаются ${\displaystyle K[i,0]}$ и ${\displaystyle K[0,j]}$. Объединение ключей обоих шифров подстановки выражается через вышеупомянутую матрицу ${\displaystyle K[i,j]}$.

2. Криптоаналитик строит полный двудольный граф для каждой группы ${\displaystyle 2^{2d}}$ ключей. Граф имеет размерность ${\displaystyle d}$, так как он сопоставляет ${\displaystyle 2^{d}}$ внутренних состояний, ${\displaystyle S_{j}}$, с ${\displaystyle 2^{d}}$ шифротекстами, ${\displaystyle C_{i}}$, используя ${\displaystyle 2^{2d}}$ ключей. В данном случае полный двудольный граф строится на основе отличий двух множеств ключей, ${\displaystyle K[i,0]}$ и ${\displaystyle K[0,j]}$.

3. Криптоаналитик выбирает ${\displaystyle 2^{d}}$ возможных шифротекстов, ${\displaystyle C_{i}}$, и запрашивает соответствующие им открытые тексты, ${\displaystyle P_{i}}$.

4. Злоумышленник выбирает внутреннее состояние, ${\displaystyle S_{j}}$ и соответствующий ему открытый текст, ${\displaystyle P_{i}}$, и производит классическую атаку посредника, используя ${\displaystyle f}$ и ${\displaystyle g}$.

5. Как только находиться ключ, сопоставляющий ${\displaystyle S_{j}}$ с ${\displaystyle P_{i}}$, он тестируется на другой паре 'внутреннее состояние-шифротекст'. Если ключ работает и на этой паре, то с большой долей вероятности это корректный ключ.

Пример атаки

Ниже представлен пример атаки на AES128. Атака состоит из 7 раундовой атаки посредника, полный двудольный граф используется в 3 последних итерациях.

Разделение ключей

Ключи разделены на ${\displaystyle 2^{112}}$ групп, каждая группа состоит из ${\displaystyle 2^{16}}$ ключей. Для каждой группы используется уникальный базовый ключ ${\displaystyle K[0,0]}$, используемый для вычисления. Данный ключ имеет следующий вид:

${\displaystyle {\begin{bmatrix}-&-&-&0\\0&-&-&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

Оставшиеся 14 байт (112 бит) заполняются последовательно. Таким образом получается ${\displaystyle 2^{112}}$ уникальных базовых ключей; по одному на каждую группу ключей.
Обычно ${\displaystyle 2^{16}}$ ключей в каждой группе выбираются в соответствии с базовым ключом группы. Они отличаются только 2 байтами (либо из ${\displaystyle i}$, либо из ${\displaystyle j}$) из представленных ниже 4 байт:

${\displaystyle {\begin{bmatrix}-&-&i&i\\j&-&j&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

Таким образом, получается${\displaystyle 2^{8}K[i,0]}$ и ${\displaystyle 2^{8}K[0,j]}$, что в сумме даёт ${\displaystyle 2^{16}}$ различных ключей, ${\displaystyle K[i,j]}$.

Построение графа

Полный двудольный граф размером ${\displaystyle 2^{112}}$ строится так, как это указано в разделе "Построение полного двудольного графа".

Атака посредника

Как только граф построен, можно начинать атаку посредника. До начала атаки ${\displaystyle 2^{d}}$ состояний из открытого текста:
${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$,
${\displaystyle 2^{d}}$ состояний из шифротекста:
${\displaystyle {\xleftarrow[{v_{j}}]{}}{\xleftarrow[{}]{K[0,j]}}S_{j}}$,
и соответствующие состояния и множества ключей ${\displaystyle K[i,0]}$ или ${\displaystyle K[0,j]}$ уже посчитаны.

Теперь можно начинать атаку посредника. Чтобы проверить ключ ${\displaystyle K[i,j]}$, необходимо только пересчитать части шифра, который будет лежать между значениями ${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$ и ${\displaystyle P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}}$. Для обратных вычислений с ${\displaystyle S_{j}}$ к ${\displaystyle {\xleftarrow[{v_{j}}]{}}}$, необходимо пересчитать только 4 S-блока. Для дальнейших вычислений с ${\displaystyle P_{i}}$ к ${\displaystyle {\xrightarrow[{v_{i}}]{}}}$, всего 3 S-блока.

Когда состояния совпадут, ключ-кандидат ${\displaystyle K[i,j]}$, принимающий значения от ${\displaystyle P_{i}}$ до ${\displaystyle S_{j}}$ найден. Далее этот ключ тестируется на другой паре открытый-/шифротекст

Результаты

Эта атака позволяет уменьшить сложность вычислений для взлома AES128 до ${\displaystyle 2^{126.18}}$, что в свою очередь в 3-5 раз быстрее метода полного перебора.

Примечания

1. Ernest Foo, Douglas Stebila. Improving the Biclique Cryptoanalysis of AES // Information Security and Privacy: 20th Australasian Conference, ACISP 2015, Brisbane, QLD, Australia, June 29 -- July 1, 2015, Proceedings. — Springer, 2015. — С. 39.
2. Архивированная копия  (неопр.). Дата обращения: 14 ноября 2015. Архивировано из оригинала 6 марта 2016 года.Архивированная копия  (неопр.). Дата обращения: 14 ноября 2015. Архивировано из оригинала 6 марта 2016 года.
3. Narrow-Bicliques: Cryptanalysis of Full IDEA. Архивировано 17 ноября 2015 года.
4. Whitfield Diffie, Martin E. Hellman. Exhaustive Cryptanalysis of the NBS Data Encryption Standard. Архивировано 3 марта 2016 года.
5. Dmitry Khovratovich, Christian Rechberger, Alexandra Savelieva. Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family. Архивировано 22 июля 2016 года.
6. Andrey Bogdanov, Dmitry Khovratovich, Christian Rechberger. Biclique Cryptanalysis of the Full AES (англ.) // Advances in Cryptology – ASIACRYPT 2011 / Dong Hoon Lee, Xiaoyun Wang. — Berlin, Heidelberg: Springer, 2011. — P. 344–371. — ISBN 978-3-642-25385-0. — doi:10.1007/978-3-642-25385-0_19. Архивировано 20 августа 2020 года.

Литература

• Andrey Bogdanov, Dmitry Khovratovich, and Christian Rechberger. Biclique Cryptanalysis of the Full AES (англ.). — P. 1-33. Архивировано 6 марта 2016 года.