Диференціальний криптоаналіз

Диференціальний криптоаналіз — це загальна форма криптоаналізу, застосовна насамперед до блокових шифрів, а також до потокових шифрів і криптографічних хеш-функцій. У найширшому сенсі це дослідження того, як відмінності у введеній інформації можуть вплинути на результативну різницю на виході. У випадку блокового шифру це належить до набору методів для відстеження відмінностей через мережу перетворення, виявлення, де шифр демонструє невипадкову поведінку, і використання таких властивостей для відновлення секретного ключа (криптографія).

Історія

Відкриття диференціального криптоаналізу, як правило, приписують Елі Біхаму та Аді Шаміру наприкінці 1980-х, які опублікували низку атак на різні блокові шифри та хеш-функції, включаючи теоретичну слабкість у стандарті шифрування даних (DES). Біхам і Шамір відзначили, що DES був напрочуд стійким до диференціального криптоаналізу, але невеликі модифікації алгоритму зробили б його більш сприйнятливим. [1]

У 1994 році член початкової команди IBM DES, Дон Копперсміт, опублікував документ, в якому говорилося, що диференціальний криптоаналіз був відомий IBM ще в 1974 році, і що захист від диференціального криптоаналізу був метою розробки. [2] За словами автора Стівена Леві[en], IBM відкрила диференційний криптоаналіз самостійно, і АНБ, очевидно, добре знало про цю техніку. [3] IBM зберігала деякі секрети, як пояснює Копперсміт: «Після обговорення з АНБ було вирішено, що розкриття міркувань дизайну розкриє техніку диференціального криптоаналізу, потужну техніку, яку можна використовувати проти багатьох шифрів. Це, у свою чергу, послабить конкурентну перевагу Сполучених Штатів над іншими країнами у сфері криптографії» [2] У IBM диференційний криптоаналіз був відомий як «T-attack» [2] або «Tickle attack». [4]

Хоча DES був розроблений з урахуванням стійкості до диференціального криптоаналізу, інші сучасні шифри виявилися вразливими. Першою метою атаки був блоковий шифр FEAL. Оригінально запропоновану версію з чотирма раундами (FEAL-4) можна зламати, використовуючи лише вісім вибраних відкритих текстів, і навіть версія FEAL на 31 раунд піддається атаці. На відміну від цього, схема може успішно аналізувати DES із зусиллям порядку 2 47 вибраних відкритих текстів.

Механіки атак

Диференціальний криптоаналіз, як правило, є атакою з вибраним відкритим текстом, це означає, що зловмисник повинен мати можливість - отримати зашифровані тексти для певного набору відкритих текстів на свій вибір. Однак існують розширення, які дозволяють атакувати відомий відкритий текст або навіть атакувати лише зашифрованим текстом . Основний метод використовує пари відкритого тексту, пов'язані постійною різницею . Різницю можна визначити кількома способами, але операція виключне АБО (XOR) є звичайною. Потім зловмисник обчислює відмінності відповідних зашифрованих текстів, сподіваючись виявити статистичні закономірності їх розподілу. Отримана пара різниць називається диференціалом . Їхні статистичні властивості залежать від природи S-боксів, які використовуються для шифрування, тому зловмисник аналізує різницю. де

(і ⊕ позначає виключне або) для кожного такого S-box S . Очікується, що в основній атаці одна конкретна відмінність шифротексту буде особливо частою. Таким чином, шифр можна відрізнити від випадкового . Більш складні варіанти дозволяють відновити ключ швидше, ніж вичерпний пошук .

У найпростішій формі відновлення ключа за допомогою диференціального криптоаналізу зловмисник запитує зашифровані тексти для великої кількості пар відкритого тексту, а потім припускає, що диференціал діє щонайменше r − 1 раундів, де r — загальна кількість раундів. Потім зловмисник визначає, які ключі раунду (для останнього раунду) можливі, припускаючи, що різниця між блоками до останнього раунду фіксована. Коли круглі ключі короткі, цього можна досягти шляхом простого вичерпного розшифрування пар зашифрованого тексту по одному раунду з кожним можливим круглим ключем. Коли один круглий ключ вважався потенційно круглим ключем значно частіше, ніж будь-який інший ключ, вважається, що це правильний круглий ключ.

Для будь-якого конкретного шифру вхідна різниця повинна бути ретельно відібрана, щоб атака була успішною. Проводиться аналіз внутрішніх компонентів алгоритму; Стандартний метод полягає в тому, щоб простежити шлях високоймовірних відмінностей на різних етапах шифрування, який називається диференціальною характеристикою .

З тих пір, як диференціальний криптоаналіз став загальновідомим, він став основною проблемою розробників шифрів. Нові конструкції, як очікується, буде супроводжуватися доказом того, що алгоритм стійкий до цієї атаки.

Атаки в деталях

Атака ґрунтується на тому факті, що дана різниця між входами/виходами виникає лише для певних значень вхідних даних. Зазвичай атака застосовується до нелінійних компонентів, також якщо б вони були суцільним компонентом (зазвичай це насправді таблиці пошуку або S-блоки ). Спостереження за бажаною різницею вихідних даних (між двома вибраними або відомими вводами відкритого тексту) пропонує можливі значення ключів.

Наприклад, якщо диференціал 1 => 1 (що означає різницю в найменшому значущому біті (LSB) вхідного сигналу призводить до вихідної різниці в LSB), яка виникає з імовірністю 4/256 (можливо з нелінійною функцією наприклад, у шифрі AES ), тоді цей диференціал можливий лише для 4 значень (або 2 пар) вхідних даних. Припустимо, що у нас є нелінійна функція, де перед обчисленням ключ подається XOR, а значення, які допускають диференціал, є {2,3} і {4,5}. Якщо зловмисник надсилає значення {6, 7} і спостерігає правильну різницю вихідних даних, це означає, що ключ або 6 ⊕ K = 2, або 6 ⊕ K = 4, тобто ключ K — 2 або 4.

По суті, для n-бітової нелінійної функції в ідеалі слід шукати якомога ближче до 2 −( n − 1), щоб досягти диференціальної однорідності . Коли це відбувається, диференціальна атака вимагає такої ж роботи, щоб визначити ключ, як і просто грубе накладання ключа.

Нелінійна функція AES має максимальну диференціальну ймовірність 4/256 (однак більшість записів є 0 або 2). Це означає, що теоретично можна було б визначити ключ із вдвічі меншою роботою, ніж грубою силою, однак висока гілка AES запобігає існуванню будь-яких слідів з високою ймовірністю протягом кількох раундів. Насправді, шифр AES був би так само захищеним від диференціальних і лінійних атак із набагато слабкішою нелінійною функцією. Неймовірно висока гілка (активна кількість S-box) 25 на 4R означає, що протягом 8 раундів жодна атака не включає менше 50 нелінійних перетворень, а це означає, що ймовірність успіху не перевищує Pr[атака] ≤ Pr[краща атака на S-box] 50 . Наприклад, з поточним S-box AES не випромінює фіксованого диференціала з імовірністю вище (4/256) 50 або 2 -300, що набагато нижче, ніж необхідний поріг 2 -128 для 128-бітового блокового шифру. Це дало б місце для більш ефективного S-бокса, навіть якщо він 16-уніфікований, ймовірність атаки все одно була б 2 -200 .

Для входів/виходів рівного розміру з 2-рівномірністю не існує збігів. Вони існують у непарних полях (наприклад, GF(2 7 )) з використанням кубування або інверсії (є також інші показники, які також можна використовувати). Наприклад, S(x) = x 3 у будь-якому непарному двійковому полі є несприйнятливим до диференціального та лінійного криптоаналізу. Частково тому в конструкції MISTY використовуються 7- і 9-розрядні функції в 16-розрядній нелінійній функції. Те, що ці функції отримують у імунітеті до диференціальних і лінійних атак, вони втрачають алгебраїчним атакам.  ] Тобто їх можна описати та вирішити за допомогою SAT-вирішувача . Частково тому AES (наприклад) має афінне відображення після інверсії.

Спеціалізовані види

Дивіться також

Посилання

 

  1. ↑ Biham and Shamir, 1993, pp. 8-9
  2. ↑ а б в Coppersmith, Don (May 1994). The Data Encryption Standard (DES) and its strength against attacks (PDF). IBM Journal of Research and Development. 38 (3): 243—250. doi:10.1147/rd.383.0243. Архів оригіналу (PDF) за 14 листопада 2020. Процитовано 24 грудня 2021. (subscription required)
  3. ↑ Levy, Steven (2001). Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age. Penguin Books. с. 55—56. ISBN 0-14-024432-8.
  4. ↑ Matt Blaze, sci.crypt, 15 August 1996, Re: Reverse engineering and the Clipper chip" [Архівовано 22 жовтня 2012 у Wayback Machine.]
Загальне
  • Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
  • Biham, E. and A. Shamir. (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology — CRYPTO '90. Springer-Verlag. 2–21.
  • Eli Biham, Adi Shamir,"Differential Cryptanalysis of the Full 16-Round DES," CS 708, Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, December 1991. (Postscript)