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

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

Даны открытый (незашифрованный) и шифрованный тексты. Криптосистема состоит из ${\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 части

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

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

Вначале данной фазы шифр делится на 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}$ . В случае совпадения получаем кандидата в ключи.

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

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

Пример

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

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

Каждый из 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 году была совершена атака , сокращающая вычислительную сложность алгоритма до ${\displaystyle 2^{72,9}}$ с использованием четырех пар открытого-закрытого текста.

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

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

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

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

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

${\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}}$ . Это вносит элемент экспоненциальной сложности в данный алгоритм .

Сложность

Временная сложность данной атаки составляет ${\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. (неопр.) . — 2010. — 16 November. — С. 2 .