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

Лавинный эффект (англ. Avalanche effect) — понятие в криптографии, обычно применяемое к блочным шифрам и криптографическим хэш-функциям. Важное криптографическое свойство для шифрования, которое означает, что изменение значения малого количества битов во входном тексте или в ключе ведет к "лавинному" изменению значений выходных битов шифротекста. Другими словами это зависимость всех выходных битов от каждого входного бита.
Термин лавинный эффект впервые введен Фейстелем в статье Cryptography and Computer Privacy, опубликованной в журнале Scientific American в Мае 1973 года.^[1], хотя концептуальное понятие использовалось еще Шенноном.
В алгоритмах с несколькими проходами лавинный эффект обычно достигается благодаря тому, что на каждом проходе изменение одного входного бита ведёт к изменениям нескольких выходных^[2].
Если криптографический алгоритм не обладает лавинным эффектом в достаточной степени, криптоаналитик может сделать предположение о входной информации, основываясь на выходной информации. Таким образом, достижение лавинного эффекта является важной целью при разработке криптографического алгоритма^[3].

Критерии

Для того, чтобы проверить наличие хорошего лавинного эффекта в конкретном алгоритме, используется несколько критериев^[4]:

Лавинный критерий

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

Строгий лавинный критерий

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

Определение

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

Пример

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

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

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

Критерий независимости битов

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

Определение

Функция $f: \{0,1\}^n \to \{0,1\}^n$ удовлетворяет критерию независимости битов, если для любых $i, j, k \in\{1, 2,...,n\}$, где $j\ne k$, инвертирование бита $i$ на входе вызывает изменения битов $j$ и $k$, причем эти изменения независимы. Для измерения независимости двух выходных бит вводят коэффициент корреляции $BIC(a_j,a_k)$ между $j$ и $k$ компонентой выходного вектора для измененного выходного вектора, который называется лавинным вектором и обозначается как $A^{ei}$.
$BIC(a_i,a_j) = \max_{1\leqslant i \leqslant n}|corr(a^{e_j}_{k},a^{e_i'}_{k})|$.
Параметр $BIC$ независимости бит для функции $f$ находится как:
$BIC = \max_{1\leqslant j, k \leqslant n, j \ne k} BIC(a_j,a_k)$.
Этот параметр демонстрирует насколько функция $f$ удовлетворяет критерию независимости битов. Он принимает значения в промежутке $[0,1]$, и в наилучшем случае равен 0 и можно говорить о независимости, в наихудшем 1, когда имеется зависимость. ^[4]
Говорят, криптографический алгоритм удовлетворяет критерию независимости битов, если при изменении любого входного бита любые два выходных бита изменяются независимо.

Гарантированный лавинный эффект порядка $\gamma$

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

Конфузия и диффузия

Основная статья: Конфузия и диффузия

Шеннон ввёл понятия конфузии и диффузии в качестве методов, усложняющих статистический криптоанализ. Согласно Шеннону:

Диффузия — метод, при котором избыточность в статистике входных данных "распределяется" по всей структуре выходных данных. При этом большие объёмы выходных данных требуются для статистического анализа, скрывается структура исходного текста. Реализуется при помощи P-блоков (англ.).

Конфузия — метод, при котором зависимость ключа и выходных данных делается как можно более сложной, в частности, нелинейной. При этом становится сложнее делать заключения о ключе по выходным данным, а также об исходных данных, если известна часть ключа. Реализуется при помощи S-блоков (англ.).

Лавинный эффект является следствием хорошей конфузии и диффузии. ^[8]

Лавинный эффект в популярных алгоритмах

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

Основная статья: DES

Подсчет зависимых выходных бит

В DES лавинный эффект носит характер строгого лавинного эффекта и проявляется уже на четвёртом-пятом раунде^[3], оценочно для каждой операции (считая, что к началу раунда влияние одного вначале выбранного бита распространилось на $R_0$ битов в правой части и $L_0$ - в левой):

После расширения: $R_1 = \min(1{,}5\cdot R_0, 32)$
Предполагая случайные попадания в 8 S-блоков, согласно задаче о размещении, биты попадут в : $S_2 = 8\cdot (1 - (1 - \frac{1}{8})^{R_1})\approx 8\cdot (1-e^{-\frac{R_1}{8}})$ S-блоков.
Одно из требований NSA к S-блокам заключалось в том, чтобы изменение каждого бита входа изменяло 2 бита выхода. Мы предположим, что каждый бит входа S-блока влияет на все 4 бита выхода. Зависимыми станут:
$S_2 = 4\cdot 8\cdot (1 - (1 - \frac{1}{8})^{R_1})\approx 4\cdot 8\cdot (1-e^{-\frac{R_1}{8}})$ бит.
После битового сложения левой $L$ и правой $R$ частей: $R_3 \approx R_2 + L_0 - \frac{R_2\cdot L_0}{32}$ ^[9]

Таблица распространения влияния 1 бита левой части в DES

Раунд	$L_{i}$	$R_{i}$
	$l$	Расширение $r \to R_{1}$	S-блоки $R_{1} \to R_{2}$	$R_{i+1} = f(R_{1})\oplus L_{i}$ $(R_{2},l) \to R_{3}$
0	1	0	0	0
1	0	0	0	(0,1)$\to$ 1
2	1	1 $\to$ 1.5	1.5 $\to$ 5.5	(5.5,0) $\to$ 5.5
3	5.5	5.5 $\to$ 8.3	8.2 $\to$ 20.5	(20.5,1) $\to$ 20.9
4	20.9	20.9$\to$31.3	31.3 $\to$ 32	(32,20.9) $\to$ 32
5	32	32	32	32

Для достижения максимального лавинного эффекта требуется аккуратно выбрать расширение, S-блоки, а также перестановку в функции $F$ ^[9]

Таблица зависимости количества измененных бит на каждом раунде

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

Изменения во входном тексте		Изменения в ключе
Раунд	Количество измененных бит	Раунд	Количество измененных бит
0	1	0	0
1	6	1	2
2	21	2	14
3	35	3	28
4	39	4	32
5	34	5	30
6	32	6	32
7	31	7	35
8	29	8	34
9	42	9	40
10	44	10	38
11	32	11	31
12	30	12	33
13	30	13	28
14	26	14	26
15	29	15	34
16	34	16	35

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

Основная статья: Advanced Encryption Standard

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

Тест лавинного эффекта в AES

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

Входной текст	Зашифрованный текст	Лавинный эффект
11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11	79 f8 cc 24 01 82 dd 7f 2d 89 f7 e7 78 b7 ee 30	.4375(56)
11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 10	9d 4c 1d b4 6a 93 27 b5 20 64 37 d1 3d 9d 2a
11 22 33 66 55 44 55 44 77 88 99 66 44 45 36 12	4a a9 16 11 e2 8a 9f 67 35 30 1f 80 16 c5 b7 cd	.5153(66)
11 22 33 66 55 44 55 44 77 88 99 66 44 45 36 11	D7 00 43 2d 51 78 f7 65 50 03 03 75 b1 e4 2d a0
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00	C6 a1 3b 37 87 8f 5b 82 6f 4f 81 62 a1 c8 79	.4453(57)
10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00	0d 19 33 06 27 42 fe 01 9c fe 06 e1 a8 1a a0 01

Лавинный эффект в ГОСТ 28147-89

Основная статья: ГОСТ 28147-89

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

Таблица распространения влияния 1 бита левой части в ГОСТ 28147-89

Раунд	$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
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 раундов. ^[9]

Значение лавинного эффекта в ГОСТ 28147-89

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

Примеры

Примеры для хэш-функций

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

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'

Примеры для шифров

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

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'

Примечания

1. ↑ Horst Feistel, "Cryptography and Computer Privacy." Scientific American, Vol. 228, No. 5, 1973. (Отсканированные изображения в формате JPEG)
2. ↑ Richard A. Mollin, "Codes: the guide to secrecy from ancient to modern times", Chapman & Hall/CRC, 2005, стр. 142. (Просмотр на Google Books)
3. ↑ ^{1 2} William Stallings, "Cryptography and network security: principles and practice", Prentice Hall, 1999, стр. 80. (Просмотр на Google Books)
4. ↑ ^{1 2 3} Isl VERGILI, Melek D. YUCEL VOL.9 // Avalanche and Bit Independence Properties for the Ensembles of Randomly Chosen n X n S-Boxes. — Turk J Elec Engin, 2001. — С. 137.
5. ↑ ^{1 2} Thomas W. Cusick, Pantelimon Stanica, Pantelimon Stănică Cryptographic Boolean Functions and Applications. — Academic Press, 2009. — С. 25.
6. ↑ Réjane Forré, "The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition", Proceedings on Advances in cryptology, Springer-Verlag New York, Inc, 1990, стр. 450. (Ссылка на PDF).
7. ↑ Федеральное агентство по образованию Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева. АКТУАЛЬНЫЕ ПРОБЛЕМЫ БЕЗОПАСНОСТИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ(Ссылка на PDF)
8. ↑ C. E. Shannon Vol 28 // Communication Theory of Secrecy Systems. — Oct 1949. — С. 656-715.
9. ↑ ^{1 2 3} Э. М. Габидулин, А. С. Кшевецкий, А. И. Колыбельников Защита информации // М.: МФТИ, 2011. — C. 11,12. — ISBN 978-5-7417-0377-9.
10. ↑ Sourav Mukhopadhyay Chapter 2 // Cryptography and Network Security. — India: Department of Mathematics Indian Institute of Technology Kharagpur. — С. 20.
11. ↑ Amish Kumar , Mrs. Namita Tiwari Vol. 1 // EFFECTIVE IMPLEMENTATION AND AVALANCHE EFFECT OF AES. — Department of CSE MANIT-Bhopal: IJSPTM, August 2012. — С. 34.
12. ↑ C. Charnes, O`Connor, J.Pieprzyk, R. Safavi-Naini, Y. Zheng Futher Comments Soviet Encryption Algorithm. — June 1,1994. — С. 1-8.
13. ↑ АКТУАЛЬНЫЕ ПРОБЛЕМЫ БЕЗОПАСНОСТИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ. Сборник материалов III Международной научно-практической конференции Красноярск 2009. (Ссылка на PDF)
14. ↑ "a" = 0110 0001, "c" = 0110 0011

Эта статья выставлена на рецензию. Пожалуйста, выскажите своё мнение о ней на подстранице рецензии.