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

Метод атаки посредника был впервые предложен Диффи и Хеллманом в 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 последних итерациях.

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