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

Лавинный эффект (англ. 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\neq k$ , инвертирование бита $i$ на входе вызывает изменения битов $j$ и $k$ , причём эти изменения независимы. Для измерения независимости двух выходных битов вводят коэффициент корреляции $BIC(a_{j},a_{k})$ между $j$ -й и $k$ -й компонентой выходного вектора для изменённого выходного вектора, который называется лавинным вектором и обозначается как $A^{ei}$ .

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

.

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

BIC=\max _{1\leqslant j,k\leqslant n,j\neq 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]^{[нет в источнике]}^{[источник не указан 2931 день]}.

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

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

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

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

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

Предполагая случайные попадания в 8 S-блоков, согласно задаче о размещении, биты попадут в: $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 бита выхода. Зависимыми станут: $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)$ битов.

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

Таблица распространения влияния 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 → 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-блоки, а также перестановку в функции $F$ ^{[источник не указан 3013 дней]}.

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

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

Изменения во входном тексте		Изменения в ключе
Раунд	Количество измененных битов	Раунд	Количество измененных битов
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

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

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

В таблице приведены численные значения лавинного эффекта для S-блоков в AES. В первом случае байт «11» (в шестнадцатеричной записи) меняется на «10», во втором случае байт «11» меняется на «12», в третьем — «00» на «10». Соответственно посчитан коэффициент лавинного эффекта для каждого случая. По этим данным мы можем наглядно видеть, что зашифрованный выходной текст совсем не простой, при довольно простом входном тексте^[10]. А коэффициент лавинного эффекта близок к 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	0,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	0,4375(56)
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	0,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	0,5153(66)
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	0,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	0,4453(57)

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

Лавинный эффект по входу обеспечивается (4 на 4) S-блоками и циклическим сдвигом влево на $11\neq 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 раундов^{[источник не указан 3013 дней]}.

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

Для криптостойкости ключевыми требованиями к операциям преобразования битов в раунде шифрования являются нелинейность, то есть невозможность подобрать линейную функцию, хорошо аппроксимирующую данное преобразование, и лавинный эффект — выполнение этих требований затрудняет проведение линейного и дифференциального криптоанализа шифра соответственно. Если рассмотреть с этих позиций операции преобразования в раунде шифрования по ГОСТ 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'

Примечания

↑ Horst Feistel, «Cryptography and Computer Privacy.» Scientific American, Vol. 228, No. 5, 1973. (Отсканированные изображения в формате JPEG) Архивная копия от 6 июня 2019 на Wayback Machine
↑ Richard A. Mollin, «Codes: the guide to secrecy from ancient to modern times», Chapman & Hall/CRC, 2005, стр. 142. (Просмотр на Google Books) Архивная копия от 2 января 2015 на Wayback Machine
↑ ¹ ² William Stallings, «Cryptography and network security: principles and practice», Prentice Hall, 1999, стр. 80. (Просмотр на Google Books) Архивная копия от 2 января 2015 на Wayback Machine
↑ ¹ ² ³ 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. Архивировано 12 марта 2005 года. Архивированная копия (неопр.). Дата обращения: 9 ноября 2009. Архивировано 12 марта 2005 года.
↑ ¹ ² Thomas W. Cusick, Pantelimon Stanica, Pantelimon Stănică. Cryptographic Boolean Functions and Applications. — Academic Press, 2009. — С. 25.
↑ 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) Архивная копия от 19 мая 2003 на Wayback Machine.
↑ Федеральное агентство по образованию Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева. АКТУАЛЬНЫЕ ПРОБЛЕМЫ БЕЗОПАСНОСТИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ (Ссылка на PDF) Архивная копия от 5 мая 2021 на Wayback Machine
↑ Shannon C. Communication Theory of Secrecy Systems (англ.) // Bell System Technical Journal — Short Hills: 1949. — Vol. 28, Iss. 4. — P. 656—715. — ISSN 0005-8580; 2376-7154 — doi:10.1002/J.1538-7305.1949.TB00928.X
↑ Sourav Mukhopadhyay. Chapter 2 // Cryptography and Network Security. — India: Department of Mathematics Indian Institute of Technology Kharagpur. — С. 20. Архивировано 20 ноября 2016 года. Архивированная копия (неопр.). Дата обращения: 4 ноября 2012. Архивировано 20 ноября 2016 года.
↑ Amish Kumar , Mrs. Namita Tiwari. Vol. 1 // EFFECTIVE IMPLEMENTATION AND AVALANCHE EFFECT OF AES. — Department of CSE MANIT-Bhopal: IJSPTM, August 2012. — С. 34. Архивировано 3 июня 2018 года.
↑ C. Charnes, O`Connor, J.Pieprzyk, R. Safavi-Naini, Y. Zheng. Futher Comments Soviet Encryption Algorithm. — June 1,1994. — С. 1—8. (недоступная ссылка)
↑ АКТУАЛЬНЫЕ ПРОБЛЕМЫ БЕЗОПАСНОСТИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ. Сборник материалов III Международной научно-практической конференции Красноярск 2009. (Ссылка на PDF) Архивная копия от 5 мая 2021 на Wayback Machine
↑ «a» = 0110 0001, «c» = 0110 0011

[feistelSciAm-1] Horst Feistel, «Cryptography and Computer Privacy.» Scientific American, Vol. 228, No. 5, 1973. (Отсканированные изображения в формате JPEG) Архивная копия от 6 июня 2019 на Wayback Machine

[MollinCodes-2] Richard A. Mollin, «Codes: the guide to secrecy from ancient to modern times», Chapman & Hall/CRC, 2005, стр. 142. (Просмотр на Google Books) Архивная копия от 2 января 2015 на Wayback Machine

[StallingsCryptography-3] ¹ ² William Stallings, «Cryptography and network security: principles and practice», Prentice Hall, 1999, стр. 80. (Просмотр на Google Books) Архивная копия от 2 января 2015 на Wayback Machine

[Vergili-4] ¹ ² ³ 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. Архивировано 12 марта 2005 года. Архивированная копия (неопр.). Дата обращения: 9 ноября 2009. Архивировано 12 марта 2005 года.

[Cusick-5] ¹ ² Thomas W. Cusick, Pantelimon Stanica, Pantelimon Stănică. Cryptographic Boolean Functions and Applications. — Academic Press, 2009. — С. 25.

[SAC-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) Архивная копия от 19 мая 2003 на Wayback Machine.

[7] Федеральное агентство по образованию Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева. АКТУАЛЬНЫЕ ПРОБЛЕМЫ БЕЗОПАСНОСТИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ (Ссылка на PDF) Архивная копия от 5 мая 2021 на Wayback Machine

[Shannon-8] Shannon C. Communication Theory of Secrecy Systems (англ.) // Bell System Technical Journal — Short Hills: 1949. — Vol. 28, Iss. 4. — P. 656—715. — ISSN 0005-8580; 2376-7154 — doi:10.1002/J.1538-7305.1949.TB00928.X

[Sourav-9] Sourav Mukhopadhyay. Chapter 2 // Cryptography and Network Security. — India: Department of Mathematics Indian Institute of Technology Kharagpur. — С. 20. Архивировано 20 ноября 2016 года. Архивированная копия (неопр.). Дата обращения: 4 ноября 2012. Архивировано 20 ноября 2016 года.

[Kumar-10] Amish Kumar , Mrs. Namita Tiwari. Vol. 1 // EFFECTIVE IMPLEMENTATION AND AVALANCHE EFFECT OF AES. — Department of CSE MANIT-Bhopal: IJSPTM, August 2012. — С. 34. Архивировано 3 июня 2018 года.

[Charnes-11] C. Charnes, O`Connor, J.Pieprzyk, R. Safavi-Naini, Y. Zheng. Futher Comments Soviet Encryption Algorithm. — June 1,1994. — С. 1—8. (недоступная ссылка)

[12] АКТУАЛЬНЫЕ ПРОБЛЕМЫ БЕЗОПАСНОСТИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ. Сборник материалов III Международной научно-практической конференции Красноярск 2009. (Ссылка на PDF) Архивная копия от 5 мая 2021 на Wayback Machine

[13] «a» = 0110 0001, «c» = 0110 0011

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]