WikiSort.ru - Не сортированное

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

Вначале данной фазы шифр делится на 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]

Алгоритм

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

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