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

Атака по полному двудольному графу (Шаблон:Lang-en) — одна из разновидностей атаки «встречи посередине». В данной атаке используется структура полного двудольного графа для увеличения количества попыток атаки посредника. Так как эта атака основа на методе атаки посредника, то она применима как к блочным шифрам, так и к криптографическим хеш-функциям. Данная атака известна тем, что позволяет вскрыть шифры 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, в которой показали, как можно применить концепцию полного двудольного графа к секретному ключу, включающий в себя блочный шифр.

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

Шаблон:Main В атаке посредника биты ключей $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\underset{f}{\overset{K[0,0]}{\to }}{C}_o$, где $f$ — это функция, которая отображает состояние в шифротекст, использую данный ключ.

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

• Первое множество ключей — это ключи, которые удовлетворяют дифференциальным требованиям функции $f$ на основе базовые вычислений: $0\underset{f}{\overset{{\mathrm{\Delta }}_i^K}{\to }}{\mathrm{\Delta }}_i$
• Второе множество ключей — это ключи, которые удовлетворяют дифференциальным требованиям функции $f$ на основе базовые вычислений: ${\mathrm{\nabla }}_j\underset{f}{\overset{\underset{j}{\overset{K}{\mathrm{\nabla }}}}{\to }}0$

Третий шаг: Заметим, что
$0\underset{f}{\overset{{\mathrm{\Delta }}_i^K}{\to }}{\mathrm{\Delta }}_i\oplus {\mathrm{\nabla }}_j\underset{f}{\overset{\underset{j}{\overset{K}{\mathrm{\nabla }}}}{\to }}0={\mathrm{\nabla }}_j\underset{f}{\overset{{\mathrm{\Delta }}_i^K\oplus \underset{j}{\overset{K}{\mathrm{\nabla }}}}{\to }}{\mathrm{\Delta }}_i$,
Также легко заметить, что кортеж $(S_0,C_0,K[0,0])$,так же удовлетворяем обоим дифференциалам. Подставляя $S_0,C_0$ $K[0,0]$ в любое из определений, получим $0\underset{f}{\overset{0}{\to }}0$, где ${\mathrm{\Delta }}_0=0,{\mathrm{\nabla }}_0=0$ и ${\mathrm{\Delta }}_0^K=0$.
Это означает, что к кортежу, полученному из базовых вычислений, также можно применять операцию XOR : $S_0\oplus {\mathrm{\nabla }}_j\underset{f}{\overset{K[0,0]\oplus {\mathrm{\Delta }}_i^K\oplus \underset{j}{\overset{K}{\mathrm{\nabla }}}}{\to }}{C}_0\oplus {\mathrm{\Delta }}_i$

Четвертый шаг: Легко заметить, что:
$S_j=S_0\oplus {\mathrm{\nabla }}_j$
$K[i,j]=K[0,0]\oplus {\mathrm{\Delta }}_i^K\oplus \underset{j}{\overset{K}{\mathrm{\nabla }}}$
$C_i=C_0\oplus {\mathrm{\Delta }}_i$
Таким образом, имеем:
$S_j\underset{f}{\overset{K[i,j]}{\to }}{C}_i$
Что совпадает с определением функции полного двудольного графа, показанной выше:
$\mathrm{\forall }i,j:S_j\underset{f}{\overset{K[i,j]}{\to }}{C}_i$

Таким образом, можно создать полный двудольный граф размера $2^{2d}$($2^{2d}$, так как $2^d$ ключей первого множества необходимо соединить с $2^d$ ключами второго множества). Это означает, что граф размером $2^{2d}$ можно построить, используя $2*2^d$ вычислений дифференциалов ${\mathrm{\Delta }}_i$ и ${\mathrm{\nabla }}_j$ и функции $f$. Если ${\mathrm{\Delta }}_i\ne {\mathrm{\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]$, используемый для вычисления. Данный ключ имеет следующий вид:

$\left[\begin{array}{cccc}-& -& -& 0\\ 0& -& -& -\\ -& -& -& -\\ -& -& -& -\end{array}\right]$

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

$\left[\begin{array}{cccc}-& -& i& i\\ j& -& j& -\\ -& -& -& -\\ -& -& -& -\end{array}\right]$

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

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

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

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

Как только граф построен, можно начинать атаку посредника. До начала атаки $2^d$ состояний из открытого текста:
$P_i\underset{}{\overset{K[i,0]}{\to }}\underset{v_i}{\overset{}{\to }}$,
$2^d$ состояний из шифротекста:
$\underset{v_j}{\overset{}{\leftarrow }}\underset{}{\overset{K[0,j]}{\leftarrow }}{S}_j$,
и соответствующие состояния и множества ключей $K[i,0]$ или $K[0,j]$ уже посчитаны.

Теперь можно начинать атаку посредника. Чтобы проверить ключ $K[i,j]$, необходимо только пересчитать части шифра, который будет лежать между значениями $P_i\underset{}{\overset{K[i,0]}{\to }}\underset{v_i}{\overset{}{\to }}$ и $P_i\underset{}{\overset{K[i,j]}{\to }}\underset{v_i}{\overset{}{\to }}$. Для обратных вычислений с $S_j$ к $\underset{v_j}{\overset{}{\leftarrow }}$, необходимо пересчитать только 4 S-блока. Для дальнейших вычислений с $P_i$ к $\underset{v_i}{\overset{}{\to }}$, всего 3 S-блока.

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

Результаты

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

Литература

• Шаблон:Статья