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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Временная сложность данной атаки составляет ${\displaystyle 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}}|}+...))}$

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

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

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

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

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

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

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

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

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

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