forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdouble_and_triple_ciphering.tex
53 lines (33 loc) · 6.84 KB
/
double_and_triple_ciphering.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
\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}$ бит $= 512$ PiB, учитывая прямой доступ по значению к возможным ключам. При нахождении соответствия берётся другая пара (открытый текст, шифртекст) и проверяется равенство для определения, правильные ключи или нет.
По отношению к CCA и CPA криптостойкость 2DES\index{шифр!2DES} эквивалентна обычному DES\index{шифр!DES} с использованием 26 GiB памяти.
\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.