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

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

ИсторияПравить

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

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

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

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

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

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

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

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

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

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

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

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

Третий шаг: Заметим, что
$0\underset{f}{\overset{{\mathrm{\Delta <!--\; \Delta \; -->}}_i^K}{\to }}{\mathrm{\Delta <!--\; \Delta \; -->}}_i\oplus <!--\; \oplus \; -->{\mathrm{\nabla <!--\; \nabla \; -->}}_j\underset{f}{\overset{{\mathrm{\nabla <!--\; \nabla \; -->}}_j^K}{\to }}0={\mathrm{\nabla <!--\; \nabla \; -->}}_j\underset{f}{\overset{{\mathrm{\Delta <!--\; \Delta \; -->}}_i^K\oplus <!--\; \oplus \; -->{\mathrm{\nabla <!--\; \nabla \; -->}}_j^K}{\to }}{\mathrm{\Delta <!--\; \Delta \; -->}}_i$$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])$ ,так же удовлетворяем обоим дифференциалам. Подставляя $S_0,C_0$$S_{0},C_{0}$  $K[0,0]$$K[0,0]$  в любое из определений, получим $0\underset{f}{\overset{0}{\to }}0$$0{\xrightarrow[{f}]{0}}0$ , где ${\mathrm{\Delta <!--\; \Delta \; -->}}_0=0,{\mathrm{\nabla <!--\; \nabla \; -->}}_0=0$$\Delta _{0}=0,\nabla _{0}=0$  и ${\mathrm{\Delta <!--\; \Delta \; -->}}_0^K=0$$\Delta _{0}^{K}=0$ .
Это означает, что к кортежу, полученному из базовых вычислений, также можно применять операцию XOR : $S_0\oplus <!--\; \oplus \; -->{\mathrm{\nabla <!--\; \nabla \; -->}}_j\underset{f}{\overset{K[0,0]\oplus <!--\; \oplus \; -->{\mathrm{\Delta <!--\; \Delta \; -->}}_i^K\oplus <!--\; \oplus \; -->{\mathrm{\nabla <!--\; \nabla \; -->}}_j^K}{\to }}{C}_0\oplus <!--\; \oplus \; -->{\mathrm{\Delta <!--\; \Delta \; -->}}_i$$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 <!--\; \oplus \; -->{\mathrm{\nabla <!--\; \nabla \; -->}}_j$$S_{j}=S_{0}\oplus \nabla _{j}$ 
$K[i,j]=K[0,0]\oplus <!--\; \oplus \; -->{\mathrm{\Delta <!--\; \Delta \; -->}}_i^K\oplus <!--\; \oplus \; -->{\mathrm{\nabla <!--\; \nabla \; -->}}_j^K$$K[i,j]=K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}$ 
$C_i=C_0\oplus <!--\; \oplus \; -->{\mathrm{\Delta <!--\; \Delta \; -->}}_i$$C_{i}=C_{0}\oplus \Delta _{i}$ 
Таким образом, имеем:
$S_j\underset{f}{\overset{K[i,j]}{\to }}{C}_i$$S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}$ 
Что совпадает с определением функции полного двудольного графа, показанной выше:
$\mathrm{\forall <!--\; \forall \; -->}i,j:S_j\underset{f}{\overset{K[i,j]}{\to }}{C}_i$$\forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}$ 

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

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

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

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

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

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

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

Пример атакиПравить

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

Разделение ключейПравить

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

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

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

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

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

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

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

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

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

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

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

РезультатыПравить

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

ЛитератураПравить

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