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

Лавинный эффект (англ. Avalanche effect) — понятие в криптографии, обычно применяемое к блочным шифрам и криптографическим хеш-функциям. Важное криптографическое свойство для шифрования, которое означает, что изменение значения малого количества битов во входном тексте или в ключе ведет к «лавинному» изменению значений выходных битов шифротекста. Другими словами, это зависимость всех выходных битов от каждого входного бита.

Термин «лавинный эффект» впервые введён Фейстелем в статье Cryptography and Computer Privacy, опубликованной в журнале Scientific American в мае 1973 года^[1], хотя концептуальное понятие использовалось ещё Шенноном.

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

Если криптографический алгоритм не обладает лавинным эффектом в достаточной степени, криптоаналитик может сделать предположение о входной информации, основываясь на выходной информации. Таким образом, достижение лавинного эффекта является важной целью при разработке криптографического алгоритма^[3].

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

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

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

Функция ${\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].

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

Диффузия — метод, при котором избыточность в статистике входных данных «распределяется» по всей структуре выходных данных. При этом большие объёмы выходных данных требуются для статистического анализа, скрывается структура исходного текста. Реализуется при помощи P-блоков^[англ.], иными словами, каждый бит незашифрованного текста должен влиять на каждый бит зашифрованного текста. Распространение одного незашифрованного бита на большое количество зашифрованных битов скрывает статистическую структуру незашифрованного текста. Определить, как статистические характеристики зашифрованного текста зависят от статистических характеристик незашифрованного текста, должно быть непросто.

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

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

В 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}$ частей^{[источник не указан 2951 день]}: ${\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}$^{[источник не указан 2951 день]}.

Следующая таблица показывает количество изменённых на каждом раунде выходных битов при условии изменения одного бита исходного текста и одного бита ключа. ^[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 раундов^{[источник не указан 2951 день]}.

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