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

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

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

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

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

Опис методу

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

Дано:

• P₁, P₂, …, P_i — відкриті тексти
• C₁=E_k(P₁), C₂=E_k(P₂), …, C_i=E_k(P_i) — відповідні їм шифротексти

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сьогодні

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

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

Основні методи

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

Основна стаття: Лінійний криптоаналіз

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

$x_{i1}+...+x_{ir}+y_{j1}+y_{js}=z_{k1}+...+z_{kt}$ (1)

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

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

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

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

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

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

Покажемо що марковський r-циклічний шифр з незалежними підключами є вразливим для ДКА тоді і тільки тоді коли для одного циклу ключ легко обчислюється за відомих трьох параметрів $(y,y^{*},\Delta x)$. Також існує (r-1) диференціал $(\alpha ,\beta )$ ^r-1 причому його ймовірність задовольняє виразу $P(\Delta y(r-1)=\beta |\Delta x=\alpha )>>2^{-n},$ де n — кількість біт в блоці шифруємого тексу. Складність знаходження ключа r-циклічного шифру Q(r) визначається, як число шифрувань, що використовуються, з подальшим знаходженням ключа: $Q(r)\geq 2/(P_{max}-1/(2^{n}-1)),$ де $P_{max}=max(\alpha )max(\beta )(P(\Delta y(r-1)=\beta |\Delta x=\alpha )).$ Зокрема у випадку якщо $P_{max}\approx 1/(2^{n}-1)$, то така атака не буде успішною. Так як операція знаходження підключа більш трудомістка ніж операція шифрування, то одиницею виміру складності є складність знаходження можливих підключів для одного циклу по відомим трійкам $(\Delta y(r-1),y(r),y^{*}(r)).$ Відмінною рисою диференціального криптоаналізу є те, що він майже не використовує алгебраїчних властивостей шифру (таких як лінійність, замкнутість, афінність та інші.) Він заснований тільки на нерівномірності розподілу ймовірностей диференціалів.

Застосування

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

• Шифр XOR
• Шифр Віженера
• Підстановочний шифр

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

Література

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