forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Avalanche_effect.tex
76 lines (61 loc) · 7.27 KB
/
Avalanche_effect.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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
\subsection{Лавинный эффект}
\selectlanguage{russian}
\subsubsection{Лавинный эффект в DES}
Оценим число раундов, за которое в DES достигается полный лавинный эффект\index{лавинный эффект}, предполагая \emph{случайное} расположение бит перед расширением, $s$-блоками ($s$ -- substitute, блоки замены) и XOR.
Пусть на входе правой части $R_i$ содержится $r$ бит, на которые уже распространилось влияние 1 вначале выбранного бита. После расширения получим
\[ n_1 \approx \min(1.5 \cdot r, 32) \]
зависимых бит. Предполагая случайные попадания в 8 $s$-блоков, согласно задаче о размещении, биты попадут в
\[ s_2 = 8 \left( 1 - \left( 1 - \frac{1}{8} \right)^{n_1} \right) \approx 8 \left( 1 - e^{-\frac{n_1}{8}} \right) \]
$s$-блоков. Одно из требований NSA к $s$-блокам заключалось в том, чтобы изменение каждого бита входа \emph{изменяло} 2 бита выхода. Мы предположим, что каждый бит входа $s$-блока \emph{влияет} на все 4 бита выхода. Зависимыми станут
\[ n_2 = 4 \cdot s_2 = 32 \left( 1 - e^{-\frac{n_1}{8}} \right) \]
бит. При дальнейшем XOR с величиной $L_i$, содержащей $l$ зависимых бит, результатом будет
\[ n_3 \approx n_2 + l - \frac{n_2 l}{32} \]
зависимых бит.
\begin{table}[h!]
\centering
\caption{Распространение влияния 1 бита левой части в DES\label{tab-DES-avalance-effect}}
\begin{tabular}{||c||c||c|c|c||}
\hline
\multirow{3}{*}{Раунд} & $L_i$ & \multicolumn{3}{|c||}{$R_i$} \\
\cline{2-5}
& & Расширение & $s$-блоки & $R_{i+1} = f(R_i) \oplus L_i$ \\
& $l$ & $r \rightarrow n_1$ & $n_1 \rightarrow n_2$ & $(n_2, l) \rightarrow n_3$ \\
\hline \hline
0 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & $(0,1) \rightarrow 1$ \\
2 & 1 & $1 \rightarrow 1.5$ & $1.5 \rightarrow 5.5$ & $(5.5, 0) \rightarrow 5.5$ \\
3 & 5.5 & $5.5 \rightarrow 8.2$ & $8.2 \rightarrow 20.5$ & $(20.5, 1) \rightarrow 20.9$ \\
4 & 20.9 & $20.9 \rightarrow 31.3$ & $31.3 \rightarrow 32$ & $(32, 20.9) \rightarrow 32$ \\
5 & 32 & 32 & 32 & 32 \\
\hline
\end{tabular}
\end{table}
В таблице \ref{tab-DES-avalance-effect} приводится расчет распространения 1 бита левой части. Посчитано число зависимых битов по раундам в предположении об их случайном расположении и том, что каждый бит на входе $s$-блока \emph{влияет} на все биты выхода. Полная диффузия достигается за 5 раундов, что совпадает с экспериментальной проверкой. Для достижения максимального лавинного эффекта требуется аккуратно выбрать расширение, $s$-блоки, а также перестановку в функции $F$.
\subsubsection{Лавинный эффект в ГОСТ 28147-89}
Лавинный эффект\index{лавинный эффект} по входу обеспечивается $(4 \times 4)$ $s$-блоками и циклическим сдвигом влево на $11 \neq 0 \mod 4$.
\begin{table}[h!]
\centering
\caption{Распространение влияния 1 бита левой части в ГОСТ 28147-89\label{tab:GOST-avalance-effect}}
\resizebox{\textwidth}{!}{ \begin{tabular}{||c||c|c|c|c|c|c|c|c||c|c|c|c|c|c|c|c||}
\hline
\multirow{2}{*}{Раунд} & \multicolumn{8}{|c||}{$L_i$} & \multicolumn{8}{|c||}{$R_i$} \\
\cline{2-17}
& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
\hline \hline
0 & & & & & & & & 1 & & & & & & & & \\
1 & & & & & & & & & & & & & & & & 1 \\
2 & & & & & & & & 1 & & & & & 3 & 1 & & \\
3 & & & & & 3 & 1 & & & & 3 & 4 & 1 & & & & 1 \\
4 & & 3 & 4 & 1 & & & & 1 & 4 & 1 & & & 3 & 1 & 3 & 4 \\
5 & 4 & 1 & & & 3 & 1 & 3 & 4 & & 3 & 4 & 4 & 4 & 4 & 4 & 1 \\
6 & & 3 & 4 & 4 & 4 & 4 & 4 & 1 & 4 & 4 & 4 & 4 & 4 & 3 & 3 & 4 \\
7 & 4 & 4 & 4 & 4 & 4 & 3 & 3 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\
8 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\
\hline
\end{tabular} }
\end{table}
Из таблицы \ref{tab:GOST-avalance-effect} видно, что на каждом раунде число зависимых битов увеличивается в среднем на 4 в результате сдвига и попадания выхода $s$-блока предыдущего раунда в два $s$-блока следующего раунда. Показано распространение зависимых битов в группах по 4 бита в левой и правой частях без учета сложения с ключом раунда. Предполагается, что каждый бит на входе $s$-блока влияет на все биты выхода. Число раундов для достижения полного лавинного эффекта без учета сложения с ключом -- 8. Экспериментальная проверка для $s$-блоков, используемых Центробанком РФ, показывает, что требуется 8 раундов.
\subsubsection{Лавинный эффект в AES}
В первом раунде один бит оказывает влияние на один байт в операции <<Замена байтов>> и затем на столбец из четырех байтов в операции <<Смешивание столбцов>>\index{лавинный эффект}.
Во втором раунде операция <<Сдвиг строки>> сдвигает байты измененного столбца на разное число байтов по строкам, получаем диагональное расположение измененных байт, то есть в каждой строке присутствует по измененному байту. Далее в результате операции <<Смешивание столбцов>> изменение распространяется от байта в столбце на весь столбец и, следовательно, на всю матрицу.
Диффузия по входу достигается за 2 раунда.