Русская Википедия:Атака по полному двудольному графу
Атака по полному двудольному графу (Шаблон:Lang-en) — одна из разновидностей атаки «встречи посередине»[1]. В данной атаке используется структура полного двудольного графа для увеличения количества попыток атаки посредника. Так как эта атака основа на методе атаки посредника, то она применима как к блочным шифрам, так и к криптографическим хеш-функциям. Данная атака известна тем, что позволяет вскрыть шифры AES[2] и IDEA[3], хотя по скорости лишь немного обгоняет метод полного перебора. Вычислительная сложность атаки составляет <math>2^{126.1}</math>, <math>2^{189.7}</math> и <math>2^{254.4}</math> для AES128, AES192 и AES256 соответственно. Так как вычислительная сложность – теоретическое значение, то это означает, что AES не был взломан и его использование остается относительно безопасным. Также эта атака поставила под сомнение достаточность количества раундов, используемых в AES.
История
Метод атаки посредника был впервые предложен Диффи и Хеллманом в 1977 году в процессе обсуждения свойств алгоритма DES.[4] Они рассуждали о том, что размер ключа был слишком мал, и что повторное использование DES с разными ключами могло быть решением данной проблемы. Однако, было предложено не использовать "double DES", а сразу применять как минимум triple DES из-за особенностей атаки посредника. С тех пор, как Диффи и Хеллман предложили метод атаки посредника, появилось много вариаций, которые могут использоваться, когда классический вариант MITM неприменимы. Идея атаки по полному двудольному графу была впервые высказана Хоратовичем, Рехбергером и Савельевой для варианта с использованием хеш-функций.[5] Впоследствии Богданов, Хоратович и Рехбергер опубликовали атаку на AES, в которой показали, как можно применить концепцию полного двудольного графа к секретному ключу, включающий в себя блочный шифр[6].
Полный двудольный граф
Шаблон:Main В атаке посредника биты ключей <math>K_1</math> и <math>K_2</math>, соответствующие первому и второму шифрам подстановки, должны быть не зависимы друг от друга, иначе совпадающие промежуточные значения открытого и зашифрованного текстов не смогут быть вычислены независимо в атаке посредника. Это свойство часто бывает трудно использовать в течение большого количества раундов, за счет диффузии атакуемого шифра.
Проще говоря, чем больше итераций будет использоваться в атаке, тем больший шифр подстановки будет “на выходе”, что в свою очередь приведёт к уменьшению числа независимых битов ключа между шифрами подстановки, которые придется взламывать полным перебором.
В данном случае, полный двудольный граф помогает в решении этой проблемы. Например, если проводить 7 раундов атаки посредника на AES, и затем использовать полный двудольный граф длиной 3 (покрывающий 3 итерации шифра), то будет возможность сопоставить промежуточное состояние в начале 7 итерации с промежуточным состоянием последней итерации (с 10, в случае с AES128). Таким образом, получается атака на все раунды шифра, хотя в классической атаке посредника это могло быть невозможно.
Суть атаки по полному двудольному графу состоит в том, чтобы построить эффективный полный двудольный граф, который в зависимости от битов ключей <math>K_1</math> и <math>K_2</math> мог сопоставлять текущее промежуточное значение соответствующему шифртексту.
Построение полного двудольного графа
Данный метод был предложен Богдановым, Ховратовичем и Рехбергером в работе Biclique Cryptanalysis of the Full AES.
Необходимо помнить, что основная функция полного двудольного графа состоит в том, чтобы строить связи между состояниями <math>S</math> и шфиротекстами <math>C</math>, используя ключи <math>K[i,j]</math>:
Построение:
Первый шаг: Выбираем состояние(<math>S_0</math>), шифротекст(<math>C_0</math>) и ключ(<math>K[0,0]</math>) так, что: <math>S_0\xrightarrow[f]{K[0,0]}C_o</math>, где <math>f</math> — это функция, которая отображает состояние в шифротекст, использую данный ключ.
Второй шаг: Выбирается два множества ключей, каждое размером <math>2^d</math>, таким образом, что:
- Первое множество ключей — это ключи, которые удовлетворяют дифференциальным требованиям функции <math>f</math> на основе базовые вычислений: <math>0\xrightarrow[f]{\Delta^K_i}\Delta_i </math>
- Второе множество ключей — это ключи, которые удовлетворяют дифференциальным требованиям функции <math>f</math> на основе базовые вычислений: <math>\nabla_j \xrightarrow[f]{\nabla^K_j}0</math>
Третий шаг: Заметим, что
<math>0\xrightarrow[f]{\Delta^K_i}\Delta_i \oplus \nabla_j \xrightarrow[f]{\nabla^K_j}0 = \nabla_j \xrightarrow[f]{\Delta^K_i \oplus \nabla^K_j}\Delta_i</math>,
Также легко заметить, что кортеж <math>(S_0, C_0, K[0,0])</math>,так же удовлетворяем обоим дифференциалам. Подставляя <math>S_0, C_0</math> <math>K[0,0]</math> в любое из определений, получим <math>0\xrightarrow[f]{0}0</math>, где <math>\Delta_0 = 0, \nabla_0 = 0</math> и <math>\Delta^K_0 = 0</math>.
Это означает, что к кортежу, полученному из базовых вычислений, также можно применять операцию XOR :
<math>S_0 \oplus \nabla_j \xrightarrow[f]{K[0,0] \oplus \Delta^K_i \oplus \nabla^K_j}C_0 \oplus \Delta_i</math>
Четвертый шаг: Легко заметить, что:
<math>S_j = S_0 \oplus \nabla_j</math>
<math>K[i,j] = K[0,0] \oplus \Delta^K_i \oplus \nabla^K_j</math>
<math>C_i = C_0 \oplus \Delta_i </math>
Таким образом, имеем:
<math>S_j \xrightarrow[f]{K[i,j]}C_i</math>
Что совпадает с определением функции полного двудольного графа, показанной выше:
<math>\forall i,j : S_j \xrightarrow[f]{K[i,j]}C_i </math>
Таким образом, можно создать полный двудольный граф размера <math>2^{2d}</math>(<math>2^{2d}</math>, так как <math>2^d</math> ключей первого множества необходимо соединить с <math>2^d</math> ключами второго множества). Это означает, что граф размером <math>2^{2d}</math> можно построить, используя <math>2*2^d</math> вычислений дифференциалов <math>\Delta_i</math> и <math>\nabla_j</math> и функции <math>f</math>. Если <math>\Delta_i \neq \nabla_j</math> для <math>i+j>0</math> , тогда все ключи <math>K[i,j]</math> будут различными во всем графе.
Криптографический анализ атаки
1. Криптоаналитик собирает все возможные ключи в подмножества ключей размером <math>2^{2d}</math>, где <math>d</math> некоторое число. Ключ в группе обозначается как <math>K[i,j]</math> в матрице размера <math>2^d \times 2^d</math>. Далее криптоаналитик разделят шифр на два шифра подстановки, <math>f</math> и <math>g</math> (такие, что <math>E = f \circ g</math>), так же, как и в атаке посредника. Множества ключей для каждого шифра подстановки имеют мощности <math>2^d</math>, и обозначаются <math>K[i,0]</math> и <math>K[0,j]</math>. Объединение ключей обоих шифров подстановки выражается через вышеупомянутую матрицу <math>K[i, j]</math>.
2. Криптоаналитик строит полный двудольный граф для каждой группы <math>2^{2d}</math> ключей. Граф имеет размерность <math>d</math>, так как он сопоставляет <math>2^d</math> внутренних состояний, <math>S_j</math>, с <math>2^d</math> шифротекстами, <math>C_i</math>, используя <math>2^{2d}</math> ключей. В данном случае полный двудольный граф строится на основе отличий двух множеств ключей, <math>K[i,0]</math> и <math>K[0,j]</math>.
3. Криптоаналитик выбирает <math>2^d</math> возможных шифротекстов, <math>C_i</math>, и запрашивает соответствующие им открытые тексты, <math>P_i</math>.
4. Злоумышленник выбирает внутреннее состояние, <math>S_j</math> и соответствующий ему открытый текст, <math>P_i</math>, и производит классическую атаку посредника, используя <math>f</math> и <math>g</math>.
5. Как только находиться ключ, сопоставляющий <math>S_j</math> с <math>P_i</math>, он тестируется на другой паре 'внутреннее состояние-шифротекст'. Если ключ работает и на этой паре, то с большой долей вероятности это корректный ключ.
Пример атаки
Ниже представлен пример атаки на AES128. Атака состоит из 7 раундовой атаки посредника, полный двудольный граф используется в 3 последних итерациях.
Разделение ключей
Ключи разделены на <math>2^{112}</math> групп, каждая группа состоит из <math>2^{16}</math> ключей. Для каждой группы используется уникальный базовый ключ <math>K[0,0]</math>, используемый для вычисления. Данный ключ имеет следующий вид:
- <math>
\begin{bmatrix} - & - & - & 0 \\ 0 & - & - & - \\ - & - & - & - \\ - & - & - & - \end{bmatrix} </math>
Оставшиеся 14 байт (112 бит) заполняются последовательно. Таким образом получается <math>2^{112}</math> уникальных базовых ключей; по одному на каждую группу ключей.
Обычно <math>2^{16}</math> ключей в каждой группе выбираются в соответствии с базовым ключом группы. Они отличаются только 2 байтами (либо из <math>i</math>, либо из <math>j</math>) из представленных ниже 4 байт:
- <math>
\begin{bmatrix} - & - & i & i \\ j & - & j & - \\ - & - & - & - \\ - & - & - & - \end{bmatrix} </math> Таким образом, получается<math>2^8 K[i,0]</math> и <math>2^8 K[0,j]</math>, что в сумме даёт <math>2^{16}</math> различных ключей, <math>K[i,j]</math>.
Построение графа
Полный двудольный граф размером <math>2^{112}</math> строится так, как это указано в разделе "Построение полного двудольного графа".
Атака посредника
Как только граф построен, можно начинать атаку посредника. До начала атаки <math>2^d</math> состояний из открытого текста:
<math>P_i\xrightarrow[]{K[i,0]}\xrightarrow[v_i]{}</math>,
<math>2^d</math> состояний из шифротекста:
<math>\xleftarrow[v_j]{}\xleftarrow[]{K[0,j]}S_j</math>,
и соответствующие состояния и множества ключей <math>K[i,0]</math> или <math>K[0,j]</math> уже посчитаны.
Теперь можно начинать атаку посредника. Чтобы проверить ключ <math>K[i,j]</math>, необходимо только пересчитать части шифра, который будет лежать между значениями <math>P_i\xrightarrow[]{K[i,0]}\xrightarrow[v_i]{}</math> и <math>P_i\xrightarrow[]{K[i,j]}\xrightarrow[v_i]{}</math>. Для обратных вычислений с <math>S_j</math> к <math>\xleftarrow[v_j]{}</math>, необходимо пересчитать только 4 S-блока. Для дальнейших вычислений с <math>P_i</math> к <math>\xrightarrow[v_i]{}</math>, всего 3 S-блока.
Когда состояния совпадут, ключ-кандидат <math>K[i,j]</math>, принимающий значения от <math>P_i</math> до <math>S_j</math> найден. Далее этот ключ тестируется на другой паре открытый-/шифротекст
Результаты
Эта атака позволяет уменьшить сложность вычислений для взлома AES128 до <math>2^{126.18}</math>, что в свою очередь в 3-5 раз быстрее метода полного перебора.
Примечания
Литература
