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

Лавинный эффект — понятие в криптографии, обычно применяемое к блочным шифрам и криптографическим хэш-функциям. Лавинный эффект проявляется в зависимости всех выходных битов от каждого входного бита. Термин введен Фейстелем, хотя концептуальное понятие использовалось еще Шенноном. В алгоритмах с несколькими проходами лавинный эффект обычно достигается благодаря тому, что на каждом проходе изменение одного входного бита ведёт к изменениям нескольких выходных.

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

Критерии

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

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

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

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

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

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

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

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

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

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

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

В DES лавинный эффект проявляется уже на четвёртом-пятом раунде, оценочно для каждой операции (считая, что к началу раунда изменение распространилось на R₀ битов в правой части и L₀ - в левой):

После расширения: $R_1 = \min(1{,}5\cdot R_0, 32)$
После восьми S-блоков: $R_2 = 4\cdot 8\cdot (1 - (1 - \frac{1}{8})^{R_1})$
После битового сложения левой и правой частей: $R_3 \approx R_2 + L_{0} - \frac{R_2\cdot L_{0}}{32}$

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

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

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

Примеры

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

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

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'

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

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

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'