double_and_triple_ciphering.tex

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

Для криптосистем с малым размером ключа, который позволяет осуществить взлом перебором всех ключей, чаще всего используется последовательное шифрование на разных ключах: двойное шифрование
    \[ E_{K_1}( E_{K_2}( M)) \]
и тройное шифрование
    \[ E_{K_1}( E_{K_2}( E_{K_3} (M))). \]
Это осуществляется для повышения стойкости шифров ко взлому, путем подбора ключа.
Например, в случае DES с размером ключа 56 битов до сих пор применяется 2DES на двух ключах, 3DES на двух или трех ключах. Для DES последовательное шифрование на двух ключах не эквивалентно шифрованию на каком-то третьем ключе
    \[ E_{K_1}( E_{K_2} (M)) \neq E_{K_3}(M). \]
Для данных ключей $K_1, K_2$ и одного сообщения $M$ возможно и существует ключ $K_3$, но для множества сообщений не существует одного ключа $K_3$, удовлетворяющего равенству.

Оценим сложность атак на примере 2DES\index{2DES}, 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}$.

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

Шифрование в 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^{64}$ бит $= 26$ GiB, учитывая прямой доступ по значению к возможным ключам. При нахождении соответствия берется другая пара (открытый текст, шифротекст) и проверяется равенство для определения, правильные ключи или нет.

По отношению к CCA, CPA криптостойкость 2DES эквивалентна обычному DES с использованием 26 GiB памяти.


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

3DES определяется как\index{3DES}
    \[ C = E_{K_1}( E_{K_2}( E_{K_3}( M))) \]
или
    \[ C = E_{K_1}( D_{K_2}( E_{K_3}( M))) \]
со следующими вариантами ключей:
\begin{itemize}
    \item $K_1, K_2, K_3$ -- независимы,
    \item $K_1 = K_3, K_2$ -- независимы,
    \item $K_1 = K_2 = K_3$.
\end{itemize}

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