Чи залежить безпека блокових шифрів від багаторазового поєднання операцій плутанини та дифузії?
Безпека блокових шифрів фундаментально вкорінена в ітеративному застосуванні операцій плутанини та дифузії. Цю концепцію вперше формалізував Клод Шеннон у своїй фундаментальній роботі з теорії комунікації систем секретності, де він сформулював необхідність як плутанини, так і дифузії в криптографічних системах для запобігання статистичним та структурним атакам. Розуміння того, чому потрібні кілька раундів цих операцій, і як вони взаємопов'язані, має вирішальне значення для оцінки розробки та безпеки сучасних блокових шифрів, таких як стандарт шифрування даних (DES) та розширений стандарт шифрування (AES).
Плутанина та дифузія: визначення та ролі
Плутанина прагне зробити зв'язок між шифротекстом і ключем якомога складнішим. Це досягається шляхом маскування статистичної структури відкритого тексту, часто за допомогою нелінійних підстановок (наприклад, S-блоків у DES та AES). Чим нелінійніше та складніше це відображення, тим важче зловмиснику вивести інформацію про ключ, навіть маючи доступ до багатьох пар відкритого тексту та шифротексту.
Дифузія, з іншого боку, спрямована на розподіл впливу кожного біта відкритого тексту на багато бітів шифротексту, так що зміна одного вхідного біта призводить до змін багатьох вихідних бітів. Ця властивість гарантує, що статистичні властивості відкритого тексту розсіюються по всьому шифротексту, що робить неможливим для зловмисників використання закономірностей за допомогою частотного аналізу або подібних методів. Дифузія зазвичай досягається за допомогою операцій лінійного змішування, таких як перестановка, побітові операції XOR або матричні множення (як в операції MixColumns в AES).
Структура ітеративних блокових шифрів
Більшість блокових шифрів структуровані як ітеровані шифри, тобто вони застосовують просту функцію раунду кілька разів для досягнення високого рівня безпеки. Функція раунду зазвичай поєднує як плутанину (наприклад, через застосування S-блоку), так і дифузію (наприклад, через кроки перестановки або змішування). Обґрунтування використання кількох раундів полягає в тому, що одного застосування плутанини та дифузії недостатньо, щоб приховати всі структурні зв'язки між відкритим текстом, шифротекстом і ключем. Кожен раунд поступово збільшує складність цих зв'язків, і лише після кількох раундів шифр досягає бажаного рівня безпеки від відомих криптоаналітичних атак.
Наприклад, якщо розглядати шифр AES, кожен раунд шифрування складається з таких ключових кроків:
1. Підбайти (Плутанина): Кожен байт у матриці станів замінюється іншим відповідно до фіксованого нелінійного S-блоку, що вводить нелінійність.
2. ShiftRows (Дифузія): Рядки матриці станів циклічно зсуваються, переміщуючи байти до різних стовпців та сприяючи змішуванню значень.
3. Змішані колонки (дифузія): Стовпці стану змішуються за допомогою множення матриць у скінченному полі, що ще більше розподіляє вплив кожного вхідного байта.
4. AddRoundKey (Плутанина): Матриця станів поєднується з підрозділом, отриманим з головного ключа, що вводить залежність ключа на кожному раунді.
Ефективність шифру залежить не лише від сили кожної окремої операції, але й від кількості разів, коли ці операції застосовуються. Криптоаналітики продемонстрували, що зменшення кількості раундів у шифрі, такому як AES або DES, може зробити його вразливим до атак, таких як диференціальний та лінійний криптоаналіз. Наприклад, хоча повний AES-128 використовує 10 раундів, версії лише з 6 раундами вразливі до певних криптоаналітичних методів.
Необхідність кількох раундів
Для подальшого уточнення розглянемо, що станеться, якщо застосувати лише один раунд плутанини та дифузії. Навіть якщо використовуються сильні S-блоки та шари змішування, статистичні зв'язки та закономірності можуть зберігатися. Зловмисники можуть використовувати ці залишкові закономірності за допомогою атак з вибраним або відомим відкритим текстом. Кілька раундів гарантують, що вплив кожного ключа та біта відкритого тексту ретельно розподілений по всьому зашифрованому тексту, що робить неможливим проведення таких атак.
Центральним тут є поняття «ефекту лавини». Надійний шифр гарантує, що невелика зміна у відкритому тексті (наприклад, перевертання одного біта) призводить до зміни приблизно половини бітів шифротексту, і ця властивість досягається лише після кількох раундів плутанини та дифузії. Ітеративна структура сучасних блокових шифрів спеціально розроблена для посилення цього ефекту, роблячи шифр стійким до атак, які спираються на відстеження зв'язків вхід-вихід.
Приклади: DES та AES
Історичний шифр DES добре ілюструє цей принцип. DES використовує 16 раундів у своїй структурі мережі Фейстеля, кожен з яких складається з розширення, S-блокової підстановки (плутанини) та перестановки (дифузії). Широкий криптоаналіз показав, що використання менше 16 раундів призводить до слабких місць; диференціальний криптоаналіз ефективний проти версій з меншою кількістю раундів. Розробники обрали 16 раундів, щоб забезпечити запас безпеки від досягнень у криптоаналізі, підкреслюючи важливість кількох ітерацій.
AES, розроблений десятиліттями пізніше, застосовує 10, 12 або 14 раундів залежно від розміру ключа (128, 192 або 256 бітів відповідно). Кожен раунд включає комбіновані ефекти плутанини та дифузії через кроки SubBytes, ShiftRows та MixColumns. Кількість раундів була ретельно обрана на основі криптоаналітичних даних для балансу безпеки та продуктивності.
Режими роботи та їх взаємозв'язок
Хоча внутрішня безпека блокових шифрів визначається багаторазовою плутаниною та розповсюдженням, режим роботи (наприклад, ECB, CBC, CFB, OFB, CTR) визначає, як блокові шифри застосовуються до даних, більших за один блок. Властивості безпеки блокового шифру в заданому режимі принципово залежать від стійкості блокового шифру до атак, що, у свою чергу, є функцією того, наскільки ретельно досягаються плутанина та розповсюдження протягом кількох раундів. Якщо базовий блоковий шифр слабкий (наприклад, із занадто малою кількістю раундів), жоден режим роботи не може компенсувати цей недолік.
Криптоаналітичні атаки та раунди
Кілька криптоаналітичних атак використовують недостатню плутанину та дифузію в блокових шифрах. Диференціальний криптоаналіз, наприклад, вивчає, як відмінності у відкритих текстах впливають на результуючі відмінності в шифротекстах. Якщо шифр не має адекватного розсіяння вхідних відмінностей, зловмисник може передбачити, як ці відмінності поширюються, і використовувати ці знання для відновлення ключа. Аналогічно, лінійний криптоаналіз шукає лінійні наближення між відкритим текстом, шифротекстом та бітами ключа. Ефективність цих атак зменшується зі збільшенням кількості раундів, за умови, що кожен раунд ефективно реалізує плутанину та дифузію.
Для ілюстрації, DES з 8 раундами (половина стандартної кількості) є чутливим до диференціального криптоаналізу, але з 16 раундами ймовірність поширення корисного диференціального сліду по всіх раундах стає незначною. Це демонструє, що ітеративна структура, і зокрема кількість раундів, є фундаментальною для досягнення практичної безпеки.
Компроміси дизайну
Розробники шифрів повинні збалансувати кількість раундів з вимогами до продуктивності. Більша кількість раундів зазвичай означає більшу безпеку, але також і більші обчислювальні витрати. Кількість раундів зазвичай вибирається для забезпечення запасу безпеки порівняно з найвідомішими атаками на момент розробки, з розрахунком на те, що майбутні досягнення в криптоаналізі можуть зменшити цей запас. Такий консервативний підхід гарантує, що шифр залишатиметься безпечним протягом очікуваного терміну служби.
Математичне обґрунтування
З теоретичної точки зору, ітеративні блокові шифри можна розглядати крізь призму моделі "ітерованого шифру продукту". За певних припущень було показано, що композиція кількох слабких шифрів (кожен з яких реалізує слабку плутанину та/або дифузію) може створити надійний загальний шифр, за умови, що компоненти достатньо незалежні, а кількість раундів велика. Це виправдовує ітеративний підхід до плутанини та дифузії в практичному проектуванні шифрів.
Практичні приклади
Показовим прикладом є структура мережі підстановки-перестановки (SPN), що використовується AES. У SPN відкритий текст піддається чергуванню шарів підстановки (плутанини) та перестановки (дифузії). Після кількох раундів кожен вихідний біт залежить від кожного вхідного біта дуже нелінійним чином. Ця властивість не досягається за один раунд; саме кумулятивний ефект кількох раундів гарантує, що кожен біт зашифрованого тексту є складною функцією кожного біта відкритого тексту та ключа, властивість, відома як повна дифузія.
Мережа Фейстеля, яка використовується в DES, досягає подібної безпеки шляхом ітеративного застосування функції раунду, яка поєднує підстановку та перестановку, причому вихід кожного раунду передається в наступний. Безпека таких конструкцій зростає експоненціально з кількістю раундів, за умови, що сама функція раунду не є тривіально оборотною або лінійною.
Висновок: Залежність безпеки від ітерації
Міцність блокових шифрів тісно пов'язана з багаторазовим застосуванням операцій плутанини та дифузії. Сучасні шифри розробляються з достатньою кількістю раундів, щоб гарантувати усунення будь-яких залишкових статистичних зв'язків з відкритим текстом або ключем, і щоб кожен біт шифротексту залежав від кожного біта відкритого тексту та ключа. Цей ітеративний процес є не просто деталлю реалізації, а основоположним принципом безпеки шифрів. Кількість раундів вибирається на основі ретельного криптоаналізу, щоб забезпечити запас міцності, і періодично переглядається в міру появи нових атак. У всіх практичних і теоретичних аспектах безпека блокових шифрів дійсно залежить від багаторазового поєднання операцій плутанини та дифузії.
Інші останні запитання та відповіді щодо Застосування блочних шифрів:
- Що повинен містити блоковий шифр, згідно з Шенноном?
- Чи означає дифузія, що окремі біти шифротексту залежать від багатьох бітів відкритого тексту?
- Чи режим ECB розбиває великий вхідний відкритий текст на наступні блоки
- Чи можемо ми використовувати блоковий шифр для створення хеш-функції або MAC?
- Чи можна використовувати режим OFB як генератор потоку ключів?
- Чи може шифрування бути детермінованим?
- Які існують режими роботи?
- Що робить режим ECB з простими блоковими шифрами
- Чи можна створити PSRNG за допомогою блокових шифрів?
- Чи можна створити MAC за допомогою блокових шифрів?
Більше запитань і відповідей див. у розділі Застосування блокових шифрів