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

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

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

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

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

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

$s=EN{C}_{K_2}(EN{C}_{K_1}(p))$$s=ENC_{K_{2}}(ENC_{K_{1}}(p))$ ,

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

$p=EN{C}_{K_1}^{-<!--\; -\; -->1}(EN{C}_{K_2}^{-<!--\; -\; -->1}(s))$$p=ENC_{K_{1}}^{-1}(ENC_{K_{2}}^{-1}(s))$ 

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

1. Все значения $m_1=EN{C}_{K_1}(p)$$m_{1}=ENC_{K_{1}}(p)$  для всех возможных значений $K_1$$K_1$ ,
2. Все значения $m_2=EN{C}_{K_2}^{-<!--\; -\; -->1}(s)$$m_{2}=ENC_{K_{2}}^{-1}(s)$  для всех возможных значений $K_2$$K_{2}$ .

Затем ему достаточно лишь найти совпадения в этих таблицах, то есть такие значения $m_1$$m_1$  и $m_2$$m_2$ , что $EN{C}_{K_1}(p)=EN{C}_{K_2}^{-<!--\; -\; -->1}(s)$$ENC_{K_{1}}(p)=ENC_{K_{2}}^{-1}(s)$ . Каждое совпадение соответствует набору ключей $(K_1,K_2)$$(K_{1},K_{2})$ , который удовлетворяет условию.

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

Решение в общем видеПравить

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

Заполнение памятиПравить

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

Определение ключаПравить

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

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

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

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

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

Фаза выделения ключейПравить

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

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

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

• Для каждого элемента из $A_0$$A_0$ 

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

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

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

ПримерПравить

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

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

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

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

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

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

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

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

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

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

РезультатыПравить

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

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

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

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

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

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

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

$C=EN{C}_{k_n}(EN{C}_{k_{n-<!--\; -\; -->1}}(...(EN{C}_{k_1}(P))...))$$C=ENC_{k_{n}}(ENC_{k_{n-1}}(...(ENC_{k_{1}}(P))...))$  $P=DE{C}_{k_1}(DE{C}_{k_2}(...(DE{C}_{k_n}(C))...))$$P=DEC_{k_{1}}(DEC_{k_{2}}(...(DEC_{k_{n}}(C))...))$ 

АлгоритмПравить

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

$s{C}_1=EN{C}_{f_1}(k_{f_1},P)$$sC_{1}=ENC_{f_{1}}(k_{f_{1}},P)$   $\mathrm{\forall <!--\; \forall \; -->}{k}_{f_1}\in <!--\; \in \; -->K$$\forall k_{f_{1}}\in K$ 

$s{C}_1$$sC_{1}$  сохраняется вместе с $k_1$$k_{1}$  d $H_1$$H_1$ .

$s{C}_{n+1}=DE{C}_{b_{n+1}}(k_{b_{n+1}},C)$$sC_{n+1}=DEC_{b_{n+1}}(k_{b_{n+1}},C)$   $\mathrm{\forall <!--\; \forall \; -->}{k}_{b_{n+1}}\in <!--\; \in \; -->K$$\forall k_{b_{n+1}}\in K$ 

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

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

$s{C}_1=DE{C}_{b_1}(k_{b_1},s_1)$$sC_{1}=DEC_{b_{1}}(k_{b_{1}},s_{1})$   $\mathrm{\forall <!--\; \forall \; -->}{k}_{b_1}\in <!--\; \in \; -->K$$\forall k_{b_{1}}\in K$ 

при каждом совпадении $s{C}_1$$sC_{1}$  с элементом из $H_1$$H_1$  в $T_1$$T_{1}$  сохраняются $k_{b_1}$$k_{b_{1}}$  и $k_{f_1}$$k_{f_{1}}$ .

$s{C}_2=EN{C}_{f_2}(k_{f_2},s_1)$$sC_{2}=ENC_{f_{2}}(k_{f_{2}},s_{1})$   $\mathrm{\forall <!--\; \forall \; -->}{k}_{f_2}\in <!--\; \in \; -->K$$\forall k_{f_{2}}\in K$ 

$s{C}_2$$sC_{2}$  сохраняется вместе с $k_{f_2}$$k_{f_{2}}$  в $H_2$$H_2$ .

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

$s{C}_2=DE{C}_{b_2}(k_{b_2},s_2)$$sC_{2}=DEC_{b_{2}}(k_{b_{2}},s_{2})$   $\mathrm{\forall <!--\; \forall \; -->}{k}_{b_2}\in <!--\; \in \; -->K$$\forall k_{b_{2}}\in K$ 

при каждом совпадении $s{C}_2$$sC_{2}$  с элементом из $H_2$$H_2$  проверяется совпадение с $T_1$$T_{1}$ , после чего в $T_2$$T_{2}$  сохраняются $k_{b_2}$$k_{b_{2}}$  и $k_{f_2}$$k_{f_{2}}$ .

$s{C}_3=EN{C}_{f_3}(k_{f_3},s_2)$$sC_{3}=ENC_{f_{3}}(k_{f_{3}},s_{2})$   $\mathrm{\forall <!--\; \forall \; -->}{k}_{f_3}\in <!--\; \in \; -->K$$\forall k_{f_{3}}\in K$ 

$s{C}_3$$sC_{3}$  сохраняется вместе с $k_{f_3}$$k_{f_{3}}$  в $H_3$$H_3$ .

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

$s{C}_n=DE{C}_{b_n}(k_{b_n},s_n)$$sC_{n}=DEC_{b_{n}}(k_{b_{n}},s_{n})$   $\mathrm{\forall <!--\; \forall \; -->}{k}_{b_n}\in <!--\; \in \; -->K$$\forall k_{b_{n}}\in K$  и при каждом совпадении $s{C}_n$$sC_{n}$  с элементом из $H_n$$H_n$  проверяется совпадение с $T_{n-<!--\; -\; -->1}$$T_{n-1}$ , после чего в $T_n$$T_{n}$  сохраняются $k_{b_n}$$k_{b_{n}}$  и $k_{f_n}$$k_{f_{n}}$ .

$s{C}_{n+1}=EN{C}_{f_{n+1}}(k_{f_{n+1}},s_n)$$sC_{n+1}=ENC_{f_{n+1}}(k_{f_{n+1}},s_{n})$   $\mathrm{\forall <!--\; \forall \; -->}{k}_{f_{n+1}}\in <!--\; \in \; -->K$$\forall k_{f_{n+1}}\in K$  и при каждом совпадении $s{C}_{n+1}$$sC_{n+1}$  с $H_{n+1}$$H_{n+1}$ , проверяется совпадение с $T_n$$T_{n}$ 

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

СложностьПравить

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

Временная сложность данной атаки составляет $2^{|k_{f_1}|}+2^{|k_{b_{n+1}}|}+2^{|s_1|}\cdot <!--\; \cdot \; -->(2^{|k_{b_1}|}+2^{|k_{f_2}|}+2^{|s_2|}\cdot <!--\; \cdot \; -->(2^{|k_{b_2}|}+2^{|k_{f_3}|}+...))$$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$$i$  на каждый $T_i$$T_{i}$  накладывается все больше ограничений, что уменьшает количество записываемых в него кандидатов. Это означает, что $T_2,T_3,...,T_n$$T_{2},T_{3},...,T_{n}$  значительно меньше $T_1$$T_{1}$ .

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

$2^{|k_{f_1}|}+2^{|k_{b_{n+1}}|}+2^{|k|-<!--\; -\; -->|s+n|}+...$$2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s+n|}+...$ 

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

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

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

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

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

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

ЛитератураПравить

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