Лавиновий ефект
Лавиновий ефект (англ. avalanche effect) — посилається на бажану властивість криптографічного алгоритму, зазвичай блочних шифрів і криптографічних геш-функцій. Лавиновий ефект очевидний у випадку коли за умови дуже маленької зміни даних на вході (наприклад, змінився один біт) результовні дані змінюються значно (наприклад, змінюється половина бітів). У випадку якісних блочних шифрів, подібна маленька зміна або в ключі, або у відкритому тексті повинна спричинити значну зміну шифротексту. Цей термін вперше використав Хорст Фейстель,[1] хоча саме поняття поринає назад щонайменше до поширення Шеннона.
Якщо блочні шифри або криптографічні геш-функції не проявляють лавиновий ефект значного ступеня, тоді це недостатнє перемішування, і звідси криптоаналітик, маючи лише результовні дані, може зробити передбачення щодо вхідних даних. Цього може вистачити, щоб частково або повністю зламати алгоритм. Отже лавиновий ефект є бажаним з точки зору розробника криптографічного алгоритму.
Розробка шифру або гешу, що виявляв би значний лавиновий ефект становить одну з першочергових цілей дизайну. Саме через це більшість блочних шифрів є послідовністю перетворень таких як заміна, переставка або модульна арифметика. Через це й геш-функції мають великий розмір блоків. Обидві ці властивості дозволяють маленьким змінам через ітерації алгоритму швидко поширитись так, що кожен біт результовних даних залежатиме від усіх бітів даних на вході ще до завершення алгоритму.[джерело?]
Сувора умова лавиновості (англ. strict avalanche criterion) — це узагальнення лавинового ефекту. Вона виконується якщо, завжди коли один вхідний біт був змінений, кожен біт на виході змінюється з імовірністю 50%. Умова покладається на концепцію повноти і лавиновість і була введена Вебстером і Таваресом (англ. Webster, Tavares) 1985.[2]
Умова незалежності бітів (англ. bit independence criterion) стверджує, що біти j і k мають змінюватись незалежно при зміні одного вхідного біту i, для всіх i, j і k.
Для криптостійкості ключовими вимогами до операцій перетворення бітів в раунді шифрування є нелінійність, тобто неможливість підібрати лінійну функцію, що добре апроксимує дане перетворення, та лавинний ефект — виконання цих вимог ускладнює проведення лінійного та диференціальн��го криптоаналізу. Якщо розглянути з цих позицій операції перетворення в раунді шифрування за ГОСТ 28147-89, то легко переконатися, що криптостійкість забезпечують лише операції складання з ключем і виконання заміни бітів по таблиці, так як операції бітового зсуву і підсумовування за модулем 2 є лінійними та не мають лавинного ефекту. Виходячи з цього можна дійти висновку, що визначальним чинником надійності шифрування з ГОСТ 28147-89 є належним чином обрана ключова інформація (ключ і таблиця замін). У разі зашифровування даних з нульовим ключем та тривіальною таблицею замін, всі вузли якої містять числа від 0 до 15 у порядку зростання, знайти за відомим шифротекстом відкритий текст досить просто за допомогою як лінійного, так і диференціального криптоаналізу.
Операція додавання даних з підключенням не може забезпечити достатнього лавинного ефекту, оскільки при зміні одного біта на вході цієї процедури лише один біт на виході змінюється з ймовірністю 0,5, інші біти змінюються з ймовірністю істотно меншою.[3] Це говорить про те, що для забезпечення криптостійкості шифрування недостатньо лише забезпечення достатньої якості ключа — необхідно також використовувати сильні таблиці замін з високими показниками нелінійності та лавинного ефекту.[4]
- ↑ Feistel, Horst (1973). Cryptography and Computer Privacy. Scientific American. 228 (5). Архів оригіналу за 6 червня 2019. Процитовано 3 травня 2012.
- ↑ Webster, A. F.; Tavares, Stafford E. (1985). On the design of S-boxes. Advances in Cryptology - Crypto '85. Lecture Notes in Computer Science. Т. 219. New York, NY,: Springer-Verlag New York, Inc. с. 523—534. ISBN 0-387-16463-4.
- ↑ C. Charnes, O`Connor, J.Pieprzyk, R. Safavi-Naini, Y. Zheng. Futher Comments Soviet Encryption Algorithm. — June 1,1994. — С. 1—8.[недоступне посилання з Октябрь 2018]
- ↑ АКТУАЛЬНЫЕ ПРОБЛЕМЫ БЕЗОПАСНОСТИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ. Сборник материалов III Международной научно-практической конференции Красноярск 2009. (Ссылка на PDF) [Архівовано 5 травня 2021 у Wayback Machine.]