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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример атаки

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты

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

Литература

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