forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathAvalanche_effect.texe
76 lines (61 loc) · 7.34 KB
/
Avalanche_effect.texe
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$ бит, на которые уже распространилось влияние одного бита, выбранного вначале. После расширения получим
\[ n_1 \approx \min(1.5 \cdot r, 32) \]
зависимых бит. Предполагая случайные попадания в 8 s-блоков, мы увидим, что, согласно задаче о размещении, биты попадут в
\[ s_2 = 8 \left( 1 - \left( 1 - \frac{1}{{8}{n_1}} \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 \approx 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}[!ht]
\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}[!ht]
\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 раунда.