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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Лавинный эффект (англ. 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}|\operatorname{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 лавинный эффект носит характер строгого лавинного эффекта и проявляется уже на четвёртом-пятом раунде[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 частей[9]: 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[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[править | править вики-текст]

В 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 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
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
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

Лавинный эффект в ГОСТ 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