Метод встречи посередине

В криптоанализе методом встречи посередине или атакой «встречи посередине» (англ. meet-in-the-middle attack) называется класс атак на криптографические алгоритмы, асимптотически уменьшающих время полного перебора за счет принципа «разделяй и властвуй», а также увеличения объема требуемой памяти. Впервые данный метод был предложен Уитфилдом Диффи и Мартином Хеллманом в 1977 году.

Начальные условия

Даны открытый (незашифрованный) и шифрованный тексты. Криптосистема состоит из $h$ циклов шифрования. Цикловые ключи независимы и не имеют общих битов. Ключ $K$ системы представляет собой сочетание из $h$-цикловых ключей $k_{1},k_{2}...k_{h}$. Задача состоит в нахождении ключа $K$.

Решение простого случая

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

$s=ENC_{K_{2}}(ENC_{K_{1}}(p))$,

где $p$ — это открытый текст, $s$ — шифротекст, а $ENC_{K_{i}}()$ — операция однократного шифрования ключом $K_{i}$. Соответственно, обратная операция — расшифрование — выглядит так:

$p=ENC_{K_{1}}^{-1}(ENC_{K_{2}}^{-1}(s))$

На первый взгляд кажется, что применение двойного шифрования многократно увеличивает стойкость всей схемы, поскольку перебирать теперь нужно два ключа, а не один. В случае алгорима DES стойкость увеличивается с $2^{56}$ до $2^{112}$. Однако это не так. Атакующий может составить две таблицы:

1. Все значения $m_{1}=ENC_{K_{1}}(p)$ для всех возможных значений $K_{1}$,
2. Все значения $m_{2}=ENC_{K_{2}}^{-1}(s)$ для всех возможных значений $K_{2}$.

Затем ему достаточно лишь найти совпадения в этих таблицах, то есть такие значения $m_{1}$ и $m_{2}$, что $ENC_{K_{1}}(p)=ENC_{K_{2}}^{-1}(s)$. Каждое совпадение соответствует набору ключей $(K_{1},K_{2})$, который удовлетворяет условию.

Для данной атаки потребовалось $2^{57}$ операций шифрования-расшифрования (лишь в два раза больше, чем для перебора одного ключа) и $2^{57}$ памяти. Дополнительные оптимизации — использование хеш-таблиц, вычисления только для половины ключей (для DES полный перебор, на самом деле, требует лишь $2^{55}$ операций) — могут снизить эти требования. Главный результат атаки состоит в том, что последовательное шифрование двумя ключами увеличивает время перебора лишь в два раза.

Решение в общем виде

Обозначим преобразование алгоритма как $E_{k}(a)=b$, где $a$ -открытый текст, а $b$ -шифротекст. Его можно представить как композицию $E_{k_{1}}E_{k_{2}}...E_{k_{h}}(a)=b$, где $E_{k_{i}}$ — цикловое преобразование на ключе $k_{i}$. Каждый ключ $k_{i}$ представляет собой двоичный вектор длины $n$, а общий ключ системы — вектор длины $n\times h$.

Заполнение памяти

Перебираются все значения $k'=(k_{1},k_{2}...k_{r})$, т.е первые $r$ цикловых ключей. На каждом таком ключе $k'$ зашифровываем открытый текст $a$ — $E_{k'}(a)=E_{k_{1}}E_{k_{2}}...E_{k_{r}}(a)=S$ (то есть проходим $r$ циклов шифрования вместо $h$). Будем считать $S$ неким адресом памяти и по этому адресу запишем значение $k'$. Необходимо перебрать все значения $k'$.

Определение ключа

Перебираются все возможные $k''=(k_{r+1},k_{r+2}...k_{h})$. На получаемых ключах расшифровывается шифротекст $b$ — $E_{k''}^{-1}(b)=E_{k_{h}}^{-1}...E_{k_{r+1}}^{-1}(b)=S'$ . Если по адресу $S'$ не пусто, то достаем оттуда ключ $k'$ и получаем кандидат в ключи $(k',k'')=k$.

Однако нужно заметить, что первый же полученный кандидат $k$ не обязательно является истинным ключом. Да, для данных $a$ и $b$ выполняется $E_{k}(a)=b$, но на других значениях открытого текста $a'$ шифротекста $b'$, полученного из $a'$ на истинном ключе, равенство может нарушаться. Все зависит от конкретных характеристик криптосистемы. Но иногда бывает достаточно получить такой «псевдоэквивалентный» ключ. В противном же случае после завершения процедур будет получено некое множество ключей ${k',k''...}$, среди которых находится истинный ключ.

Если рассматривать конкретное применение, то шифротекст и открытый текст могут быть большого объема (например, графические файлы) и представлять собой достаточно большое число блоков для блочного шифра. В данном случае для ускорения процесса можно зашифровывать и расшифровывать не весь текст, а только его первый блок (что намного быстрее) и затем, получив множество кандидатов, искать в нем истинный ключ, проверяя его на остальных блоках.

Атака с разбиением ключевой последовательности на 3 части

В некоторых случаях бывает сложно разделить биты последовательности ключей на части, относящиеся к разным ключам. В таком случае применяют алгоритм 3-subset MITM attack, предложенный Богдановым и Ричбергером в 2011 году на основе обычного метода встречи посередине. Данный алгоритм применим, когда нет возможности разделить последовательности ключевых битов на две независимые части. Состоит из двух фаз: выделения и проверки ключей.

Фаза выделения ключей

Вначале данной фазы шифр делится на 2 подшифра $f$ и $g$, как и в общем случае атаки, однако допуская возможное использование некоторых битов одного подшифра в другом. Так, если $b=E_{k}(a)$, то $E_{k}(*)=f(g(*))$; при этом биты ключа $k$, использующиеся в $f$ обозначим $k_{f}$, а в $g$ — $k_{g}$. Тогда ключевую последовательность можно разделить на 3 части:

1. $A_{0}$ — пересечение множеств $k_{f}$ и $k_{g}$,
2. $A_{1}$ — ключевые биты, которые есть только в $k_{f}$,
3. $A_{2}$ — ключевые биты, которые есть только в $k_{g}$.

Далее проводится атака методом встречи посередине по следующему алгоритму:

• Для каждого элемента из $A_{0}$

1. Вычислить промежуточное значение $i=f(k_{f},a)$, где $a$ — открытый текст, а $k_{f}$ — некоторые ключевые биты из $A_{0}$ и $A_{1}$, то есть $i$ — результат промежуточного шифрования открытого текста на ключе $k_{f}$.
2. Вычислить промежуточное значение $j=g^{-1}(k_{g},b)$, где $b$ — закрытый текст, а $k_{g}$ — некоторые ключевые биты из $A_{0}$ и $A_{2}$, то есть $j$ — результат промежуточного расшифровывания закрытого текста на ключе $k_{g}$.
3. Сравнить $i$ и $j$. В случае совпадения получаем кандидата в ключи.

Фаза проверки ключей

Для проверки ключей полученные кандидаты проверяют на нескольких парах известных открытых-закрытых текстов. Обычно для проверки требуется не очень большое количество таких пар текстов.

Пример

В качестве примера приведем атаку на семейство шифров KTANTAN, которая позволила сократить вычислительную сложность получения ключа с $2^{80}$ (атака полным перебором) до $2^{75,170}$.

Подготовка атаки

Каждый из 254 раундов шифрования с использованием KTANTAN использует 2 случайных бита ключа из 80-битного набора. Это делает сложность алгоритма зависимой только от количества раундов. Приступая к атаке, авторы заметили следующие особенности:

• В раундах с 1 по 111 не были использованы следующие биты ключа: $k_{32},k_{39},k_{44},k_{61},k_{66},k_{75}$.
• В раундах со 131 по 254 не были использованы следующие биты ключа: $k_{3},k_{20},k_{41},k_{47},k_{63},k_{74}$.

Это позволило разделить биты ключа на следующие группы:

1. $A_{0}$ — общие биты ключа: те 68 бит, не упомянутые выше.
2. $A_{1}$ — биты, используемые только в первом блоке раундов (с 1 по 111),
3. $A_{2}$ — биты, используемые только во втором блоке раундов (со 131 по 254).

Первая фаза: выделение ключей

Возникала проблема вычисления описанных выше значений $i$ и $j$, так как в рассмотрении отсутствуют раунды со 112 по 130, однако тогда было проведено частичное сравнение: авторы атаки заметили совпадение 8 бит в $i$ и $j$, проверив их обычной атакой методом встречи посередине на 127 раунде. В связи с этим в данной фазе сравнивались значения именно этих 8 бит в подшифрах $i$ и $j$. Это увеличило количество кандидатов в ключи, но не сложность вычислений.

Вторая фаза: проверка ключей

Для проверки кандидатов в ключи алгоритма KTANTAN32 потребовалось в среднем еще две пары открытого-закрытого текстов для выделения ключа.

Результаты

• KTANTAN32: вычислительная сложность подбора ключа сократилась до $2^{75,170}$ с использованием трех пар открытого-закрытого текста.
• KTANTAN48: вычислительная сложность подбора ключа сократилась до $2^{75,044}$ с использованием двух пар открытого-закрытого текста.
• KTANTAN64: вычислительная сложность подбора ключа сократилась до $2^{75,584}$ с использованием двух пар открытого-закрытого текста.

Тем не менее, это не лучшая атака на семейство шифров KTANTAN. В 2011 году была совершена атака, сокращающая вычислительную сложность алгоритма до $2^{72,9}$ с использованием четырех пар открытого-закрытого текста.

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

Атака по полному двудольному графу применяется для увеличения количества попыток атаки посредника с помощью построения полного двудольного графа. Предложена Диффи и Хеллманом в 1977 году.

Многомерный алгоритм

Многомерный алгоритм метода встречи посередине применяется при использовании большого количества циклов шифрования разными ключами на блочных шифрах. Вместо обычной «встречи посередине» в данном алгоритме используется разделение криптотекста несколькими промежуточными точками.

Предполагается, что атакуемый текст зашифрован некоторое количество раз блочным шифром:

$C=ENC_{k_{n}}(ENC_{k_{n-1}}(...(ENC_{k_{1}}(P))...))$ $P=DEC_{k_{1}}(DEC_{k_{2}}(...(DEC_{k_{n}}(C))...))$

Алгоритм

• Вычисляется:

$sC_{1}=ENC_{f_{1}}(k_{f_{1}},P)$  $\forall k_{f_{1}}\in K$

$sC_{1}$ сохраняется вместе с $k_{1}$ d $H_{1}$.

$sC_{n+1}=DEC_{b_{n+1}}(k_{b_{n+1}},C)$  $\forall k_{b_{n+1}}\in K$

$sC_{n+1}$ сохраняется вместе с $k_{b_{n+1}}$ d $H_{b_{n+1}}$.

• Для каждого возможного промежуточного состояния $s_{1}$ вычисляется:

$sC_{1}=DEC_{b_{1}}(k_{b_{1}},s_{1})$  $\forall k_{b_{1}}\in K$

при каждом совпадении $sC_{1}$ с элементом из $H_{1}$ в $T_{1}$ сохраняются $k_{b_{1}}$ и $k_{f_{1}}$.

$sC_{2}=ENC_{f_{2}}(k_{f_{2}},s_{1})$  $\forall k_{f_{2}}\in K$

$sC_{2}$ сохраняется вместе с $k_{f_{2}}$ в $H_{2}$.

• Для каждого возможного промежуточного состояния $s_{2}$ вычисляется:

$sC_{2}=DEC_{b_{2}}(k_{b_{2}},s_{2})$  $\forall k_{b_{2}}\in K$

при каждом совпадении $sC_{2}$ с элементом из $H_{2}$ проверяется совпадение с $T_{1}$, после чего в $T_{2}$ сохраняются $k_{b_{2}}$ и $k_{f_{2}}$.

$sC_{3}=ENC_{f_{3}}(k_{f_{3}},s_{2})$  $\forall k_{f_{3}}\in K$

$sC_{3}$ сохраняется вместе с $k_{f_{3}}$ в $H_{3}$.

• Для каждого возможного промежуточного состояния $s_{n}$ вычисляется:

$sC_{n}=DEC_{b_{n}}(k_{b_{n}},s_{n})$  $\forall k_{b_{n}}\in K$ и при каждом совпадении $sC_{n}$ с элементом из $H_{n}$ проверяется совпадение с $T_{n-1}$, после чего в $T_{n}$ сохраняются $k_{b_{n}}$ и $k_{f_{n}}$.

$sC_{n+1}=ENC_{f_{n+1}}(k_{f_{n+1}},s_{n})$  $\forall k_{f_{n+1}}\in K$ и при каждом совпадении $sC_{n+1}$ с $H_{n+1}$, проверяется совпадение с $T_{n}$

Далее найденная последовательность кандидатов тестируется на иной паре открытого-закрытого текста для подтверждения истинности ключей. Следует заметить рекурсивность в алгоритме: подбор ключей для состояния $s_{j}$ происходит на основе результатов для состояния $s_{j-1}$. Это вносит элемент экспоненциальной сложности в данный алгоритм.

Сложность

Основной источник:

Временная сложность данной атаки составляет $2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|s_{1}|}\cdot (2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}+2^{|s_{2}|}\cdot (2^{|k_{b_{2}}|}+2^{|k_{f_{3}}|}+...))$

Говоря об использовании памяти, легко заметить что с увеличением $i$ на каждый $T_{i}$ накладывается все больше ограничений, что уменьшает количество записываемых в него кандидатов. Это означает, что $T_{2},T_{3},...,T_{n}$ значительно меньше $T_{1}$.

Верхняя граница объема используемой памяти:

$2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s+n|}+...$

где $k$ — общая длина ключа.

Сложность использования данных зависит от вероятности «прохождения» ложного ключа. Эта вероятность равна $1/2^{l}$, где $l$ — длина первого промежуточного состояния, которая чаще всего равна размеру блока. Учитывая количество кандидатов в ключи после первой фазы, сложность равна $2^{|k|-|l|}$.

В итоге получаем $2^{|k|-2b}$, где $|b|$ — размер блока.

Каждый раз, когда последовательность кандидатов в ключи тестируется на новой паре открытого-закрытого текста, количество успешно проходящих проверку ключей умножается на вероятность прохождения ключа, которая равна $1/2^{|b|}$.

Часть атаки полным перебором (проверка ключей но новых парах открытого-закрытого текстов) имеет временную сложность $2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+...$, в которой, очевидно, последующие слагаемые все быстрее стремятся к нулю.

В итоге, сложность данных по аналогичным суждениям ограничена приблизительно $\left\lceil |k|/n\right\rceil$ парами открытого-закрытого ключа.

Литература

• Moore, Stephane. Meet-in-the-Middle Attacks (неопр.). — 2010. — 16 November. — С. 2.