double_and_triple_ciphering.tex

\subsection{Двойное и тройное шифрования}\index{шифрование!двойное}\index{шифрование!тройное}
\selectlanguage{russian}

В конце XX-го века, когда ненадёжность существующего стандарта DES\index{шифр!DES} уже была очевидна, а нового стандарта ещё не было, стали распространены техники двойного и тройного шифрования, когда к одному блоку текста последовательно применяется несколько преобразований на разных ключах.

Например, двойное шифрование\index{шифрование!двойное} 2DES\index{шифр!2DES} использует два разных ключа $K_1$ и $K_2$ для шифрования одного блока текста дважды:
\[ E_{K1, K2} \left( M \right) \equiv E_{K1} \left( E_{K2} \left( M \right) \right). \]

Так как функция шифрования\index{функция!шифрования} DES не образует группу\index{группа} (\cite{Kaliski:Rivest:Sherman:1988, Campbell:Wiener:1993}), то данное преобразование не эквивалентно однократному шифрованию на каком-нибудь третьем ключе. То есть для произвольных $K_1$ и $K_2$ нельзя подобрать такой $K_3$, что
\[E_{K1} \left( E_{K2} \left( M \right) \right) \equiv E_{K3} \left( M \right).\]

Тем самым размер ключевого пространства (количество различных ключей шифрования, если считать за ключ пару $K_1$ и $K_2$) увеличивается с $2^{56}$ до $2^{112}$ (без учёта проверочных бит). Однако из-за атаки <<встреча посередине>>\index{атака!встреча посередине} (\langen{meet in the middle}) фактическая криптостойкость увеличилась не более чем до $2^{57}$.

Тройной DES (\langen{triple DES, 3DES})\index{шифрование!тройное}\index{шифр!3DES} использует тройное преобразование. Причём в качестве второй функции используется функция \emph{расшифрования}:
\[ E_{K1, K2, K3} \left( M \right) \equiv E_{K1} \left( D_{K2} \left( E_{K3} \left( M \right) \right) \right). \]

\begin{itemize}
	\item Вариант $K_1 \neq K_2 \neq K_3$ является наиболее защищённым, ключевое пространство увеличивается до $2^{168}$.
	\item Вариант $K_1 \neq K_2$, $K_1 = K_3$ увеличивает ключевое пространство до $2^{112}$, но защищён от атаки <<встреча посередине>>\index{атака!встреча посередине}, в отличие от 2DES\index{шифр!2DES}.
	\item Вариант $K_1 = K_2 = K_3$ эквивалентен однократному преобразованию DES\index{шифр!DES}. Его можно использовать для обеспечения совместимости.
\end{itemize}

Оценим сложность атак на 2DES\index{шифр!2DES} и 3DES\index{шифр!3DES}.

\subsubsection{Атака на двойное шифрование}

%Для упрощения записи введём обозначение последовательного шифрования $E_{K_1}( E_{K_2}( \dots E_{K_n}(M) \dots)) \equiv E{K_1} \circ E_{K_2} (M)$ и назовём его суперпозицией функций $E_{K_i}$.

Атака основана на предположении, что у криптоаналитика есть возможность получить либо шифртекст для любого открытого текста\index{атака!с известным шифртекстом} (\langen{Chosen Plaintext Attack, CPA}), либо открытый текст по шифртексту\index{атака!с известным открытым текстом} (\langen{Chosen Ciphertext Attack, CCA}), но неизвестен ключ шифрования, который и нужно найти.

Шифрование в 2DES\index{шифр!2DES}:
    \[ C = E_{K_1}( E_{K_2}(M)). \]
Запишем $D_{K_1}(C) = E_{K_2}(M)$. Пусть время одного шифрования -- $T_E$, время одного сравнения блоков $T_{=} \approx 2^{-10} T_E$.

Атака для нахождения ключей без использования памяти занимает время
    \[ T = 2^{56 + 56} (T_E + T_{=}) \approx 2^{112} T_E. \]

Можно заранее вычислить значения $E_{K_2}(M)$ для всех ключей и построить таблицу: индекс -- $E_{K_2}(M)$, значения поля -- набор ключей $K_2$, которые соответствуют этому значению. Атака для нахождения ключей требует времени
    \[ T = 2 \cdot 2^{56} T_E + 2^{56} T_{=} \approx 2^{57} T_E \]
и памяти $M = 56 \cdot 2^{56} \approx 2^{62}$ бит ($\approx 504$ Пбайт), учитывая прямой доступ по значению к возможным ключам. При нахождении соответствия берётся другая пара (открытый текст, шифртекст) и проверяется равенство для определения, являются ли ключи правильными или нет.

По отношению к CCA и CPA криптостойкость 2DES\index{шифр!2DES} эквивалентна обычному DES\index{шифр!DES} с использованием 26 ГиБ памяти.

\subsubsection{Атака на тройное шифрование}

Атака для нахождения ключей (CCA\index{атака!с известным шифртекстом}, CPA\index{атака!с известным открытым текстом}) на наиболее стойкий вариант 3DES\index{шифр!3DES} (все три ключа $K_1$, $K_2$ и $K_3$ выбираются независимо) требует времени $T \approx 2^{168} T_E$ без использования дополнительной памяти.

Для построения таблицы запишем
    \[ D_{K_2}( D_{K_1}( C)) = E_{K_3} (M). \]
Таблица строится аналогично 2DES\index{шифр!2DES} для $E_{K_3}(M)$. С использованием памяти атака занимает время $T = 2^{112} T_E$ и память $M = 26$ GiB.