Покажем, что обратимость схемы Фейстеля не зависит от выбора функции $F$.
Напомним, что схема Фейстеля – это итеративное шифрование, в котором выход подаётся на вход следующей итерации по правилу:
При расшифровании используется та же схема, только левая и правая части меняются местами перед началом итераций, а ключи раунда подаются в обратном порядке:
Пусть функция $F$ является простой линейной комбинацией некоторых битов правой части и ключа раунда относительно операции XOR. Тогда можно записать систему линейных уравнений битов выхода $y_i$ относительно битов входа $x_i$ и ключа $k_i$ после всех 16 раундов в виде
где суммирование производится по модулю 2, коэффициенты $a_i$ и $b_i$ известны и равны 0 или 1, количество битов в блоке открытого текста равно $n_1$, количество битов ключа равно $n_2$.
Имея открытый текст и шифртекст, легко найти ключ. Без знания открытых текстов, выполняя XOR шифртекстов, можно найти XOR открытых текстов, что может привести к возникновению благоприятных для взлома шифра условий. Во-первых, это может позволить провести атаку на различение сообщений. Во-вторых, в широко распространенных случаях, когда известны форматы сообщений, отдельные поля или распределение символов открытого текста, появляется возможность осуществить атаку перебором с учётом множества уравнений, полученных XOR шифртекстов.
Для предотвращения подобных атак используются s-блоки замены для создания нелинейности в уравнениях выхода $y_i$ относительно сообщения и ключа.
В отличие от устаревшего алгоритма DES блочный шифр ГОСТ без s-блоков намного сложнее для взлома, так как для него нельзя записать систему линейных уравнений:
Операция $\boxplus$ нелинейна по XOR. Например, только на трёх операциях $\oplus$, $\boxplus$ и $\lll f(R_i)$ без использования s-блоков построен блочный шифр RC5, который по состоянию на 2010 г. не был взломан.
Оценим число раундов, за которое в DES достигается полный лавинный эффект, предполагая случайное расположение бит перед расширением, s-блоками ($s$ – substitute, блоки замены) и XOR.
Пусть на входе правой части $R_i$ содержится $r$ бит, на которые уже распространилось влияние одного бита, выбранного вначале. После расширения получим
зависимых бит. Предполагая случайные попадания в 8 s-блоков, мы увидим, что, согласно задаче о размещении, биты попадут в
s-блоков. Одно из требований NSA к s-блокам заключалось в том, чтобы изменение каждого бита входа изменяло 2 бита выхода. Мы предположим, что каждый бит входа s-блока влияет на все 4 бита выхода. Зависимыми станут
бит. При дальнейшем XOR с величиной $L_i$, содержащей $l$ зависимых бит, результатом будет
зависимых бит.
| Раунд | $L_i$ | $R_i$ | ||
| Расширение | 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$ | |
| 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 |
В таблице [tab-DES-avalance-effect] приводится расчёт распространения одного бита левой части. Посчитано число зависимых битов по раундам в предположении об их случайном расположении и о том, что каждый бит на входе s-блока влияет на все биты выхода. Полная диффузия достигается за 5 раундов, что совпадает с экспериментальной проверкой. Для достижения максимального лавинного эффекта требуется аккуратно выбрать расширение, s-блоки, а также перестановку в функции $F$.
Лавинный эффект по входу обеспечивается $(4 \times 4)$ s-блоками и циклическим сдвигом влево на $11 \neq 0 \mod 4$.
| Раунд | $L_i$ | $R_i$ | ||||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 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 |
Из таблицы [tab:GOST-avalance-effect] видно, что на каждом раунде число зависимых битов увеличивается в среднем на 4 в результате сдвига и попадания выхода s-блока предыдущего раунда в два s-блока следующего раунда. Показано распространение зависимых битов в группах по 4 бита в левой и правой частях без учёта сложения с ключом раунда. Предполагается, что каждый бит на входе s-блока влияет на все биты выхода. Число раундов для достижения полного лавинного эффекта без учёта сложения с ключом – 8. Экспериментальная проверка для s-блоков, используемых Центробанком РФ, показывает, что требуется 8 раундов.
В первом раунде один бит оказывает влияние на один байт в операции «замена байтов» и затем на столбец из четырёх байтов в операции «перемешивание столбцов».
Во втором раунде операция «сдвиг строк» сдвигает байты изменённого столбца на разное число байтов по строкам, в результате получаем диагональное расположение изменённых байтов, то есть в каждой строке присутствует по изменённому байту. Далее, в результате операции «перемешивания столбцов» изменение распространяется от байта в столбце на весь столбец и, следовательно, на всю матрицу.
Диффузия по входу достигается за 2 раунда.
В конце XX-го века, когда ненадёжность существующего стандарта DES уже была очевидна, а нового стандарта ещё не было, стали распространены техники двойного и тройного шифрования, когда к одному блоку текста последовательно применяется несколько преобразований на разных ключах.
Например, двойное шифрование 2DES использует два разных ключа $K_1$ и $K_2$ для шифрования одного блока текста дважды:
Так как функция шифрования DES не образует группу ([22, 50]), то данное преобразование не эквивалентно однократному шифрованию на каком-нибудь третьем ключе. То есть для произвольных $K_1$ и $K_2$ нельзя подобрать такой $K_3$, что
Тем самым размер ключевого пространства (количество различных ключей шифрования, если считать за ключ пару $K_1$ и $K_2$) увеличивается с $2^{56}$ до $2^{112}$ (без учёта проверочных бит). Однако из-за атаки «встреча посередине» (англ. meet in the middle) фактическая криптостойкость увеличилась не более чем до $2^{57}$.
Тройной DES (англ. triple DES, 3DES) использует тройное преобразование. Причём в качестве второй функции используется функция расшифрования:
Оценим сложность атак на 2DES и 3DES.
Атака основана на предположении, что у криптоаналитика есть возможность получить либо шифртекст для любого открытого текста (англ. Chosen Plaintext Attack, CPA), либо открытый текст по шифртексту (англ. Chosen Ciphertext Attack, CCA), но неизвестен ключ шифрования, который и нужно найти.
Запишем $D_{K_1}(C) = E_{K_2}(M)$. Пусть время одного шифрования – $T_E$, время одного сравнения блоков $T_{=} \approx 2^{-10} T_E$.
Атака для нахождения ключей без использования памяти занимает время
Можно заранее вычислить значения $E_{K_2}(M)$ для всех ключей и построить таблицу: индекс – $E_{K_2}(M)$, значения поля – набор ключей $K_2$, которые соответствуют этому значению. Атака для нахождения ключей требует времени
и памяти $M = 56 \cdot 2^{56} \approx 2^{62}$ бит ($\approx 504$ Пбайт), учитывая прямой доступ по значению к возможным ключам. При нахождении соответствия берётся другая пара (открытый текст, шифртекст) и проверяется равенство для определения, являются ли ключи правильными или нет.
По отношению к CCA и CPA криптостойкость 2DES эквивалентна обычному DES с использованием 26 ГиБ памяти.
Атака для нахождения ключей (CCA, CPA) на наиболее стойкий вариант 3DES (все три ключа $K_1$, $K_2$ и $K_3$ выбираются независимо) требует времени $T \approx 2^{168} T_E$ без использования дополнительной памяти.
Для построения таблицы запишем
Таблица строится аналогично 2DES для $E_{K_3}(M)$. С использованием памяти атака занимает время $T = 2^{112} T_E$ и память $M = 26$ GiB.