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

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

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

Даны открытый (незашифрованный) и шифрованный тексты. Криптосистема состоит из [math]\displaystyle{ h }[/math] циклов шифрования. Цикловые ключи независимы и не имеют общих битов. Ключ [math]\displaystyle{ K }[/math] системы представляет собой сочетание из [math]\displaystyle{ h }[/math]-цикловых ключей [math]\displaystyle{ k_1, k_2 ... k_h }[/math]. Задача состоит в нахождении ключа [math]\displaystyle{ K }[/math].

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

Простым примером является двойное последовательное шифрование блочным алгоритмом двумя различными ключами [math]\displaystyle{ K_1 }[/math] и [math]\displaystyle{ K_2 }[/math]. Процесс шифрования выглядит так:

[math]\displaystyle{ s = ENC_{K_2}(ENC_{K_1}(p)) }[/math],

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

[math]\displaystyle{ p = ENC^{-1}_{K_1}(ENC^{-1}_{K_2}(s)) }[/math]

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

1. Все значения [math]\displaystyle{ m_1 = ENC_{K_1}(p) }[/math] для всех возможных значений [math]\displaystyle{ K_1 }[/math],
2. Все значения [math]\displaystyle{ m_2 = ENC^{-1}_{K_2}(s) }[/math] для всех возможных значений [math]\displaystyle{ K_2 }[/math].

Затем ему достаточно лишь найти совпадения в этих таблицах, то есть такие значения [math]\displaystyle{ m_1 }[/math] и [math]\displaystyle{ m_2 }[/math], что [math]\displaystyle{ ENC_{K_1}(p) = ENC^{-1}_{K_2}(s) }[/math]. Каждое совпадение соответствует набору ключей [math]\displaystyle{ (K_1,K_2) }[/math], который удовлетворяет условию.

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

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

Обозначим преобразование алгоритма как [math]\displaystyle{ E_k(a)=b }[/math], где [math]\displaystyle{ a }[/math] -открытый текст, а [math]\displaystyle{ b }[/math] -шифротекст. Его можно представить как композицию [math]\displaystyle{ E_{k_1}E_{k_2}...E_{k_h}(a)=b }[/math], где [math]\displaystyle{ E_{k_i} }[/math] — цикловое преобразование на ключе [math]\displaystyle{ k_i }[/math]. Каждый ключ [math]\displaystyle{ k_i }[/math] представляет собой двоичный вектор длины [math]\displaystyle{ n }[/math], а общий ключ системы — вектор длины [math]\displaystyle{ n \times h }[/math].

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

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

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

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

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

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

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

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

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

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

1. [math]\displaystyle{ A_0 }[/math] — пересечение множеств [math]\displaystyle{ k_f }[/math] и [math]\displaystyle{ k_g }[/math],
2. [math]\displaystyle{ A_1 }[/math] — ключевые биты, которые есть только в [math]\displaystyle{ k_f }[/math],
3. [math]\displaystyle{ A_2 }[/math] — ключевые биты, которые есть только в [math]\displaystyle{ k_g }[/math].

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

• Для каждого элемента из [math]\displaystyle{ A_0 }[/math]

1. Вычислить промежуточное значение [math]\displaystyle{ i=f(k_f,a) }[/math], где [math]\displaystyle{ a }[/math] — открытый текст, а [math]\displaystyle{ k_f }[/math] — некоторые ключевые биты из [math]\displaystyle{ A_0 }[/math] и [math]\displaystyle{ A_1 }[/math], то есть [math]\displaystyle{ i }[/math] — результат промежуточного шифрования открытого текста на ключе [math]\displaystyle{ k_f }[/math].
2. Вычислить промежуточное значение [math]\displaystyle{ j=g^{-1}(k_g,b) }[/math], где [math]\displaystyle{ b }[/math] — закрытый текст, а [math]\displaystyle{ k_g }[/math] — некоторые ключевые биты из [math]\displaystyle{ A_0 }[/math] и [math]\displaystyle{ A_2 }[/math], то есть [math]\displaystyle{ j }[/math] — результат промежуточного расшифровывания закрытого текста на ключе [math]\displaystyle{ k_g }[/math].
3. Сравнить [math]\displaystyle{ i }[/math] и [math]\displaystyle{ j }[/math]. В случае совпадения получаем кандидата в ключи.

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

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

Пример

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

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

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

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

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

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

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

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

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

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

Результаты

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

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

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

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

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

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

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

[math]\displaystyle{ C = ENC_{k_n}(ENC_{k_{n-1}}(...(ENC_{k_1}(P))...)) }[/math] [math]\displaystyle{ P = DEC_{k_1}(DEC_{k_2}(...(DEC_{k_n}(C))...)) }[/math]

Алгоритм

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

[math]\displaystyle{ sC_1 = ENC_{f_1}(k_{f_1},P) }[/math]  [math]\displaystyle{ \forall k_{f_1} \in K }[/math]

[math]\displaystyle{ sC_1 }[/math] сохраняется вместе с [math]\displaystyle{ k_1 }[/math] d [math]\displaystyle{ H_1 }[/math].

[math]\displaystyle{ sC_{n+1} = DEC_{b_{n+1}}(k_{b_{n+1}},C) }[/math]  [math]\displaystyle{ \forall k_{b_{n+1}} \in K }[/math]

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

• Для каждого возможного промежуточного состояния [math]\displaystyle{ s_1 }[/math] вычисляется:

[math]\displaystyle{ sC_1 = DEC_{b_1}(k_{b_1},s_1) }[/math]  [math]\displaystyle{ \forall k_{b_1} \in K }[/math]

при каждом совпадении [math]\displaystyle{ sC_1 }[/math] с элементом из [math]\displaystyle{ H_1 }[/math] в [math]\displaystyle{ T_1 }[/math] сохраняются [math]\displaystyle{ k_{b_1} }[/math] и [math]\displaystyle{ k_{f_1} }[/math].

[math]\displaystyle{ sC_2 = ENC_{f_2}(k_{f_2},s_1) }[/math]  [math]\displaystyle{ \forall k_{f_2} \in K }[/math]

[math]\displaystyle{ sC_2 }[/math] сохраняется вместе с [math]\displaystyle{ k_{f_2} }[/math] в [math]\displaystyle{ H_2 }[/math].

• Для каждого возможного промежуточного состояния [math]\displaystyle{ s_2 }[/math] вычисляется:

[math]\displaystyle{ sC_2 = DEC_{b_2}(k_{b_2},s_2) }[/math]  [math]\displaystyle{ \forall k_{b_2} \in K }[/math]

при каждом совпадении [math]\displaystyle{ sC_2 }[/math] с элементом из [math]\displaystyle{ H_2 }[/math] проверяется совпадение с [math]\displaystyle{ T_1 }[/math], после чего в [math]\displaystyle{ T_2 }[/math] сохраняются [math]\displaystyle{ k_{b_2} }[/math] и [math]\displaystyle{ k_{f_2} }[/math].

[math]\displaystyle{ sC_3 = ENC_{f_3}(k_{f_3},s_2) }[/math]  [math]\displaystyle{ \forall k_{f_3} \in K }[/math]

[math]\displaystyle{ sC_3 }[/math] сохраняется вместе с [math]\displaystyle{ k_{f_3} }[/math] в [math]\displaystyle{ H_3 }[/math].

• Для каждого возможного промежуточного состояния [math]\displaystyle{ s_n }[/math] вычисляется:

[math]\displaystyle{ sC_n = DEC_{b_n}(k_{b_n},s_n) }[/math]  [math]\displaystyle{ \forall k_{b_n} \in K }[/math] и при каждом совпадении [math]\displaystyle{ sC_n }[/math] с элементом из [math]\displaystyle{ H_n }[/math] проверяется совпадение с [math]\displaystyle{ T_{n-1} }[/math], после чего в [math]\displaystyle{ T_n }[/math] сохраняются [math]\displaystyle{ k_{b_n} }[/math] и [math]\displaystyle{ k_{f_n} }[/math].

[math]\displaystyle{ sC_{n+1} = ENC_{f_{n+1}}(k_{f_{n+1}},s_n) }[/math]  [math]\displaystyle{ \forall k_{f_{n+1}} \in K }[/math] и при каждом совпадении [math]\displaystyle{ sC_{n+1} }[/math] с [math]\displaystyle{ H_{n+1} }[/math], проверяется совпадение с [math]\displaystyle{ T_n }[/math]

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

Сложность

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

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

Говоря об использовании памяти, легко заметить что с увеличением [math]\displaystyle{ i }[/math] на каждый [math]\displaystyle{ T_i }[/math] накладывается все больше ограничений, что уменьшает количество записываемых в него кандидатов. Это означает, что [math]\displaystyle{ T_2, T_3, ..., T_n }[/math] значительно меньше [math]\displaystyle{ T_1 }[/math].

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

[math]\displaystyle{ 2^{|k_{f_1}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s+n|}+... }[/math]

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

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

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

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

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

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

Литература

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