Атака з відомим відкритим текстом

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Атака з відомим відкритим текстом (з англійської "Known-plaintext attack") — вид криптоаналізу, який ґрунтується на знанні частини відкритого тексту, та зашифрованого тексту (шифротексту) повідомлення. Вони можуть бути використані для подальшого виявлення секретної інформації, такої, як секретні ключі і книги коду[en].

Часто з велокою імовірністю можна зробити припущення про зміст частини повідомлення. Це може статись під час використання стандартних бланків документів, поширених фраз («Добридень… З найкращими побажаннями») тощо. Шифровки різних країн часто містили специфічні вирази: Heil Hitler!, Banzai!, Пролетарии всех стран соединяйтесь! і т.п. Під час Другої світової війни англійські криптоаналітики називали такі уривки «підказками» (англ. Crib - підказка, шпаргалка)[1]

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

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

Опис методу[ред.ред. код]

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

Дано:

  • P1, P2, …, Pi — відкриті тексти
  • C1=Ek(P1), C2=Ek(P2), …, Ci=Ek(Pi) — відповідні їм шифротексти

Необхідно знайти:

  • k — ключ шифрування, або
  • D(C) — функцію дешифрування (не як функцію від ключа, але лише від шифротекста)

Відмінності від інших методів криптоаналізу[ред.ред. код]

Атака на основі тільки шифротексту[ред.ред. код]

Основна стаття: Атака на основі шифротексту

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

Атака на основі підібраного відкритого тексту[ред.ред. код]

Основна стаття: Атака на основі підібраного відкритого тексту[ru]

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

Атака на основі адаптивно підібраного відкритого тексту[ред.ред. код]

Основна стаття: Атака на основі адаптивно підібраного відкритого тексту[ru]

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

Приклади застосування в історії[ред.ред. код]

У випадку Енігми, Німецьке вище командування було дуже уважне у забезпеченні безпеки системи, так як вони усвідомлювали можливу проблему аналізу на основі відкритих текстів. Команда, яка працювала над розшифруванням, могла зробити припущення про зміст текстів грунтуючись на тому, коли були послані повідомлення. Наприклад, прогноз погоди передавався кожен день в один і той же час. Згідно з регламентом військових сполучень, кожне повідомлення містило слово «Погода» (Wetter) на одному і тому ж місці, а знання погоди в даній місцевості дуже допомагало в припущеннях про зміст решти повідомлення. Також дуже допомогли повідомлення офіцера, який посилав кожен раз «Нічого повідомити» (Nothing to report), надаючи матеріал для криптоаналізу. Інші командувачі теж посилали стандартні відповіді або їх відповіді містили стандартні частини.

Після того, як полонений німець на допиті зізнався, що операторам наказано шифрувати числа шляхом написання літерами кожної цифри, Алан Тьюринг переглянув повідомлення і визначив, що слово «eins» зустрічається в 90% повідомлень. На основі цього був створений Eins каталог, який містив всі можливі положення роторів, початкові позиції і набори ключів Енігми.

Сьогодні[ред.ред. код]

Сучасні шифри погано підлягають цим методом криптоаналізу. Наприклад, для злому DES необхідно приблизно пар «відкритий текст / зашифрований текст».

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

Основні методи[ред.ред. код]

Лінійний метод криптоаналізу[ред.ред. код]

Основна стаття: Лінійний криптоаналіз[ru] У відкритій пресі лінійний метод криптоаналізу вперше був запропонований японським математиком Мацуї. Метод передбачає, що криптоаналитик знає відкриті й відповідні зашифровані тексти. Найчастіше при шифруванні застосовується додавання по модулю 2 тексту з ключем і так само застосовуються операції перемішування і розсіювання. Завдання криптоаналитика полягає в тому щоб знайти таку лінійну апроксимацію

(1)

яка буде найкращою. Нехай p це ймовірність того що (1) виконується, зрозуміло що нам треба щоб p\approx 0.5, а також потрібно щоб величина | p-0.5 | була максимальна. У випадку коли ця величина досить велика і криптоаналітику відомо досить багато пар відкритого і відповідного йому шифрованого тексту, то сума по модулю 2 біт ключа на відповідній позиції в правій частині рівності (1) дорівнює найбільш ймовірного значенням суми по модулю 2 відповідних біт в відкритому і зашифрованому текстах в лівій частині. У разі, коли p>0.5 сума в правій частині (1) дорівнює нулю, коли сума біт в лівій частині дорівнює нулю більш, ніж в половині пар зашифрованих текстів. Сума біт в правій частині дорівнює одиниці, якщо сума біт в лівій частині дорівнює одиниці більш ніж в половині випадків текстів. Якщо p<0.5 то навпаки: сума біт в правій частині дорівнює одиниці якщо в лівій частині сума біт дорівнює нулю більш ніж для половини текстів. І сума біт в правій частині дорівнює нулю якщо сума біт в лівій частині дорівнює одиниці більш ніж в половині випадків. Для знаходження кожного біта ключа, тепер треба вирішити систему лінійних рівнянь для відповідних відомих комбінацій цих біт. Це не становить складності так як складність даної системи виражається поліномом не більше ніж третього ступеня від довжини ключа. Кількість необхідних пар відкритий / шифрований текст, для розкриття шифру оцінюється формулою . Для розкодування шифру DES таким методом виходить, що необхідно приблизно пар відкритий / зашифрований блок.

Диференціальний метод криптоаналізу[ред.ред. код]

Основна стаття: Диференціальний криптоаналіз

Диференціальний метод криптоаналізу (ДКА) у 1990 році був запропонований Е.Біхамом та А.Шаміром. Диференціальний криптоаналіз - це спроба розкрити секретний ключ блокових шифрів, які засновані на повторному застосуванні криптографічно слабких операцій шифрування r раз. Під час криптоаналізу передбачається, що на кожному циклі шифрування використовується свій підключ шифрування. ДКА може використовувати як вибрані, так і відомі відкриті тексти. Головною умовою успіху розкодування r-циклічного шифру є існування диференціалів (r-1)-го циклу, які мають велику ймовірність. Диференціал i-го циклу визначається як пара чисел , таких, що пара різних відкритих текстів x і x* з різницею може після i-го циклу дати на виході пару y і y* з різницею . Ймовірність i-циклового диференціала це умовна ймовірність того, що різниця y і y* після i-го циклу дорівнює з умовою, що спочатку были x і x* с різницею . Відкритий текст x і підключі {к1 , к2 ,…., кi} вважаємо незалежними і випадковими.

Процедура ДКА r-циклічного шифру з вибраними відкритими текстами може бути наступною:

  1. Даний етап є етапом попередніх обчислень. На ньому ми шукаємо множину (r-1)-циклових диференціалів . Упорядковуємо цю множину згідно з величиною ймовірностей елементів.
  2. Наступний етап вимагає від нас вибору x і x*, так щоб їх різниця дорівнювала , для них маємо пару шифртекстів y(r), y*(r). Вважаємо, що на виході передостаннього циклу різниця дорівнювала найбільш віоргідній . Для троьх елементів знаходимо кожне можливе значення підключа k(r). Збільшуємо лічільник появи кожного такого значення підключа к(r).
  3. На даному етапі повторюємо попередній пункт до тих пір поки один або кілька подключей не почнуть з'являтися частіше за інших. Обираємо даний ключ (або множину ключів) як рішення к(r).
  4. На даному етапі ми повторюємо пункти 1-3 для (r-1) -го циклу при цьому значення y (r-1) обчислюються розшифруванням y(r) з використанням ключа k(r), знайденого в попередньому пункті. І повторюємо ці дії поки не знайдемо ключі всіх циклів.

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

Покажемо що марковський r-циклічний шифр з незалежними підключами є вразливим для ДКА тоді і тільки тоді коли для одного циклу ключ легко обчислюється за відомих трьох параметрів . Також існує (r-1) диференціал r-1 причому його ймовірність задовольняє виразу де n - кількість біт в блоці шифруємого тексу. Складність знаходження ключа r-циклічного шифру Q(r) визначається, як число використовуємих шифрувань з подальшим знаходженням ключа: де Зокрема у випадку якщо , то така атака не буде успішною. Так як операція знаходження підключа більш трудомістка ніж операція шифрування, то одиницею виміру складності є складність знаходження можливих подключей для одного циклу по відомим трійкам Відмінною рисою диференціального криптоаналізу є те, що він майже не використовує алгебраїчних властивостей шифру (таких як лінійність, замкнутість, афінність та інші.) Він заснований тільки на нерівномірності розподілу ймовірностей диференціалів.

Застосування[ред.ред. код]

Найефективніший для криптоаналізу класичних шифрів, наприклад для таких як:

Шифр XOR,

Шифр Віженера,

Підстановочний шифр.

Але також використовується як елемент криптоаналізу сучасних шифрів.

Література[ред.ред. код]

  • Владислав Козачук, Енігма: Як німецький машинний шифр був зламаний, і як він був прочитаний союзниками під час Другої світової війни, 1984, ISBN 0-89093-547-5. (англ.)
  1. Слово crib (як іменник, так і дієслово) має в англійському десятки значень, в тому числі сленгових. Зокрема, шкільним сленгом crib означає підказку, шпаргалку та інші незаконні методи складання іспитів