Лавинный эффект

Криптографический алгоритм удовлетворяет лавинному критерию, если при изменении одного бита входной последовательности изменяется в среднем половина выходных битов.

Формально для функции может быть дано такое определение:

Функция ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}^{n}}$ удовлетворяет лавинному критерию, если изменение одного бита на входе вызывает изменение в среднем половины выходных битов[4].

Определение строго лавинного критерия (СЛК) впервые было дано C. Таваресом и А. Вебстером в работе по исследованию и проектированию S-блоков.

Булеву функцию можно рассматривать как часть структуры S-блоков. Дизайн S-блоков на основе булевых функций, удовлетворяющих СЛК, был изучен в работах Адамса и C. Тавареса, Kwangio Kim. Начиная с 1990 года СЛК изучается в контексте булевых функций[5].

Булева функция ${\displaystyle f(x)}$, где ${\displaystyle x}$ — вектор из ${\displaystyle n}$ переменных, удовлетворяет СЛК, если при изменении одного из ${\displaystyle n}$ входных битов выходной бит меняется с вероятностью ровно ${\displaystyle 1/2}$.

Пример булевой функции трёх переменных, удовлетворяющей СЛК[5]:

Входные биты ${\displaystyle x}$	000	001	010	011	100	101	110	111
Выходной бит ${\displaystyle f(x)}$	1	1	1	0	0	1	1	1

Говорят, что криптографический алгоритм удовлетворяет строгому лавинному критерию[6], если при изменении одного бита входной последовательности каждый бит выходной последовательности изменяется с вероятностью одна вторая.

C. Таварес и А. Вебстер в своей работе по изучению и описанию S-блоков определили ещё один критерий для булевой функции, называемый критерий независимости битов, согласно которому при изменении одного входного бита любые два выходные бита меняются независимо друг от друга.

Функция ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}^{n}}$ удовлетворяет критерию независимости битов, если для любых ${\displaystyle i,j,k\in \{1,2,...,n\}}$, где ${\displaystyle j\neq k}$, инвертирование бита ${\displaystyle i}$ на входе вызывает изменения битов ${\displaystyle j}$ и ${\displaystyle k}$, причём эти изменения независимы. Для измерения независимости двух выходных битов вводят коэффициент корреляции ${\displaystyle BIC(a_{j},a_{k})}$ между ${\displaystyle j}$-й и ${\displaystyle k}$-й компонентой выходного вектора для изменённого выходного вектора, который называется лавинным вектором и обозначается как ${\displaystyle A^{ei}}$.

${\displaystyle BIC(a_{i},a_{j})=\max _{1\leqslant i\leqslant n}|\operatorname {corr} (a_{k}^{e_{j}},a_{k}^{e_{i}'})|}$.

Параметр ${\displaystyle BIC}$ независимости битов для функции ${\displaystyle f}$ находится как:

${\displaystyle BIC=\max _{1\leqslant j,k\leqslant n,j\neq k}BIC(a_{j},a_{k})}$.

Этот параметр демонстрирует насколько функция ${\displaystyle f}$ удовлетворяет критерию независимости битов. Он принимает значения в промежутке ${\displaystyle [0,1]}$, и в наилучшем случае равен 0 и можно говорить о независимости, в наихудшем 1, когда имеется зависимость[4].

Говорят, что криптографический алгоритм удовлетворяет критерию независимости битов, если при изменении любого входного бита любые два выходных бита изменяются независимо.

Выделяют также гарантированный лавинный эффект порядка ${\displaystyle \gamma }$.

Критерий гарантированного лавинного эффекта (англ. GAC – guaranteed avalanche criterion) порядка ${\displaystyle \gamma }$ выполняется, если при изменении одного бита на входе узла замен на выходе меняются как минимум ${\displaystyle \gamma }$ выходных битов. Выполнение GAC порядка ${\displaystyle \gamma }$ в диапазоне от 2 до 5 для узлов замен обеспечивает любому шифру очень высокий лавинный эффект вследствие распространения изменений в битах при прохождении данных по раундам шифрования в схеме Фейстеля[7].

В DES лавинный эффект носит характер строгого лавинного эффекта и проявляется уже на четвёртом-пятом раунде[3], оценочно для каждой операции (считая, что к началу раунда влияние одного вначале выбранного бита распространилось на ${\displaystyle R_{0}}$ битов в правой части и ${\displaystyle L_{0}}$ — в левой):

После расширения: ${\displaystyle R_{1}=\min(1{,}5\cdot R_{0},32).}$

Предполагая случайные попадания в 8 S-блоков, согласно задаче о размещении, биты попадут в: ${\displaystyle S_{2}=8\cdot \left(1-(1-{\tfrac {1}{8}})^{R_{1}}\right)\approx 8\cdot \left(1-e^{-{\frac {R_{1}}{8}}}\right)}$ S-блоков.

Одно из требований NSA к S-блокам заключалось в том, чтобы изменение каждого бита входа изменяло 2 бита выхода. Мы предположим, что каждый бит входа S-блока влияет на все 4 бита выхода. Зависимыми станут: ${\displaystyle S_{2}=4\cdot 8\cdot \left(1-(1-{\tfrac {1}{8}})^{R_{1}}\right)\approx 4\cdot 8\cdot \left(1-e^{-{\frac {R_{1}}{8}}}\right)}$ битов.

После битового сложения левой ${\displaystyle L}$ и правой ${\displaystyle R}$ частей: ${\displaystyle R_{3}\approx R_{2}+L_{0}-{\frac {R_{2}\cdot L_{0}}{32}}.}$

Раунд	${\displaystyle L_{i}}$	${\displaystyle R_{i}}$
	${\displaystyle l}$	Расширение ${\displaystyle r\to R_{1}}$	S-блоки ${\displaystyle R_{1}\to R_{2}}$	${\displaystyle R_{i+1}=f(R_{1})\oplus L_{i}}$ ${\displaystyle (R_{2},l)\to R_{3}}$
0	1	0	0	0
1	0	0	0	(0, 1)${\displaystyle \to }$ 1
2	1	1 → 1,5	1,5 → 5,5	(5,5, 0) → 5,5
3	5,5	5,5 → 8,3	8,2 → 20,5	(20,5, 1) → 20,9
4	20,9	20,9 → 31.3	31,3 → 32	(32, 20,9) → 32
5	32	32	32	32

Для достижения максимального лавинного эффекта требуется аккуратно выбрать расширение, S-блоки, а также перестановку в функции ${\displaystyle F}$.

Следующая таблица показывает количество изменённых на каждом раунде выходных битов при условии изменения одного бита исходного текста и одного бита ключа. [9]

В AES лавинный эффект появляется следующим образом: в первом раунде операция MixColumns() распространяет изменения одного байта на все 4 байта колонки, после чего во втором раунде применение операций ShiftRows() и MixColumns() распространяет изменения на всю таблицу. Таким образом, полная диффузия достигается уже на втором раунде. Конфузия обеспечивается операцией SubBytes().

В таблице приведены численные значения лавинного эффекта для S-блоков в AES. В первом случае байт «11» (в шестнадцатеричной записи) меняется на «10», во втором случае байт «11» меняется на «12», в третьем — «00» на «10». Соответственно посчитан коэффициент лавинного эффекта для каждого случая. По этим данным мы можем наглядно видеть, что зашифрованный выходной текст совсем не простой, при довольно простом входном тексте[10]. А коэффициент лавинного эффекта близок к 0,5, что означает хорошее выполнение лавинного критерия.

Лавинный эффект по входу обеспечивается (4 на 4) S-блоками и циклическим сдвигом влево на ${\displaystyle 11\neq 0\mod 4}$

Раунд	${\displaystyle L_{i}}$								${\displaystyle 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
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

Из таблицы видно, что на каждом раунде число независимых битов увеличивается в среднем в 4 раза в результате сдвига и попадания выхода S-блока предыдущего раунда в 2 S-блока следующего раунда. Показано распространение зависимых битов в группах по 4 бита в левой и правой частях без учета сложения с ключом раунда. Предполагается, что каждый бит на входе S-блока влияет на все биты выхода. Число раундов для достижения полного лавинного эффекта без учета сложения с ключом — 8. Экспериментальная проверка для S-блоков, используемых Центробанком РФ, показывает, что требуется 8 раундов.

Для криптостойкости ключевыми требованиями к операциям преобразования битов в раунде шифрования являются нелинейность, то есть невозможность подобрать линейную функцию, хорошо аппроксимирующую данное преобразование, и лавинный эффект — выполнение этих требований затрудняет проведение линейного и дифференциального криптоанализа шифра соответственно. Если рассмотреть с этих позиций операции преобразования в раунде шифрования по ГОСТ 28147-89, то легко убедиться в том, что криптостойкость обеспечивают лишь операции сложения с ключом и выполнения замены битов по таблице, так как операции побитового сдвига и суммирования по модулю 2 являются линейными и не обладают лавинным эффектом. Из этого можно сделать вывод, что определяющим фактором надежности шифрования по ГОСТ 28147-89 является надлежащим образом выбранная ключевая информация (ключ и таблица замен). В случае зашифрования данных с нулевым ключом и тривиальной таблицей замен, все узлы которой содержат числа от 0 до 15 в порядке возрастания, найти по известному шифртексту открытый текст достаточно просто при помощи как линейного, так и дифференциального криптоанализа.

Как показано[11], операция сложения данных с подключом не может обеспечить достаточного лавинного эффекта, поскольку при изменении одного бита на входе этой процедуры лишь один бит на выходе меняется с вероятностью 0,5, остальные биты меняются с вероятностью существенно меньшей. Это говорит о том, что для обеспечения криптостойкости шифрования недостаточно только обеспечения достаточного качества ключа — необходимо также использовать сильные таблицы замен с высокими показателями нелинейности и лавинного эффекта[12].

В примерах демонстрируется изменение хэша при изменении одного бита во входной последовательности.

SHA-1:

SHA-1(0110 0001 0110 0001 0110 0001 0110 0001) = '70c881d4a26984ddce795f6f71817c9cf4480e79'
SHA-1(0110 0001 0110 0011 0110 0001 0110 0001) = 'c6fdc1a445881de1f33e09cf00420a57b493b96d'
SHA-1(0110 0001 0110 0001 0110 0001 0110 0011) = '00b25f15212ed225d3389b5f75369c82084b3a76'

MD5:

MD5(0110 0001 0110 0001 0110 0001 0110 0001)  = '74b87337454200d4d33f80c4663dc5e5'
MD5(0110 0001 0110 0011 0110 0001 0110 0001)  = 'ca7de9e17429612452a717a44c36e688'
MD5(0110 0001 0110 0001 0110 0001 0110 0011)  = '3963a2ba65ac8eb1c6e2140460031925'

В примерах демонстрируется изменение шифрованного сообщения при изменении одного бита[13] во входной последовательности или в ключе.

AES:

AES(ключ = "aaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa")   = '5188c6474b228cbdd242e9125ebe1d53'
AES(ключ = "aaaaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa")   = 'f7e5c1118f5cb86198e37ff7a29974bc'
AES(ключ = "aacaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa")   = '2c50b5cac9c755d67aa61b87c26248eb'
AES(ключ = "aacaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa")   = '87c09128de852b990b3dfbd65c7d9094'

RC4:

RC4(ключ = "aaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa")   = '71ddf97f23b8e42a4f0ccc463d7da4aa'
RC4(ключ = "aaaaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa")   = '3d0feab630a32d1d0654c5481bd9ddd9'
RC4(ключ = "aacaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa")   = '476266d77453695b6cee682f23b0c51d'
RC4(ключ = "aacaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa")   = '3139d4506185d48e9b9e3dbbd4b57ec2'

Шифр Цезаря не реализует лавинного эффекта:

E(k = 3, "aaaaaaaaaaaaaaaa") = 'dddddddddddddddd'
E(k = 3, "acaaaaaaaaaaaaaa") = 'dfdddddddddddddd'