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

Перебираются все значения ${\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''...}}$, среди которых находится истинный ключ.

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

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

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

${\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 }$ парами открытого-закрытого ключа.