Актуальність проблеми захисту інформаційних систем

Таблиця 3.2. Рівняння ефективних лінійних статистичних аналогів блоків . 

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

32	1	2	3	4	5	6	7	8	9
8	9	10	11	12	13	14	15	16	17
16	17	18	19	20	21	22	23	24	25
24	25	26	27	28	29	3	31	32	1

Таблиця 3.3. Перестановка із розширенням функції . 

можна легко  вирахувати, що насправді на 26-й позиції  насправді буде розташовуватись 17-й  біт. Аналогічним чином при виході із блока, вихідний вектор зазнає перестановки завдяки роботі блоку. Через це вихідні із блоку біти під номерами 17,18, 19 та 20 опиняться на 8, 14, 25 та 3 позиціях вихідного вектора, згідно з таблицею 2.11. 

Тоді  ефективне лінійне статистичне  рівняння буде мати наступний вигляд , причому .

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

Зауваження. Мацуі називає потрійною сумою для го раунду випадкову величину вигляду

,

де  – деякі рівноімовірносні булеві функції.

Лема 1. Якщо незалежні бінарні випадкові величини, то 

Доведення

      Доведемо  цю лему для двох незалежних величин. Так як й незалежні і при цьому , , та , то  

. 
 

Тепер розглянемо випадок із незалежними величинами. Нехай

  і .

Тоді  
 
 
 

Визначення 2. Послідовні потрійні суми та називаються зв’язаними, якщо . Із визначення випливає, що  

, де де .

Визначення 3. Якщо – зв’язані потрійні суми, то

                                                   (5)

і називається раундовою потрійною сумою. У випадку лінійних функцій формула (11) дає лінійне співвідношення вигляду:

                                            (6)

 що  виконується із співвідношенням,  детермінованим  і лемою 1.

Визначення  4. Ефективним лінійним статистичним називається лінійний статистичний аналог (6) із заданої множини з найбільшим .

Як бачимо метод лінійного криптоаналізу фактично являється частинним випадком узагальненого статистичного методу й полягає у використанні  виразів вигляду: 

Імовірність з якою виконується вищезазначена  рівність: 

       Розглянемо  найпростіший(не найефективніший) варіант  методу лінійного крипто аналізу  – алгоритм визначення одного біту ключа, що також має назву «Перший  алгоритм Мацуі». Цей алгоритм використовує безпосередньо відкритий та зашифрований тексти, тобто

,  

В даному варіанті метод лінійного крипто аналізу визначає лінійну комбінацію бітів ключа.

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

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

Інші  біти ключа визначаються методом  перебору.

       Вдосконалений другий алгоритм Мацуі являє собою узагальнення першого алгоритму й полягає у використанні виразів вигляду : 

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

При випадковому  рівно ймовірнісному виборі . Для отримання оцінки для всього алгоритму розглядають послідовності «узгоджених» лінійних співвідношень для сусідніх раундів ( тобто співвідношення, коли вихідна лінійна комбінація попереднього раунду співпадає із вхідною лінійною комбінацією наступного раунду ). 

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

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

Схема даного алгоритму представлена на малюнку:

Рисунок 3.3. Схема алгоритму спрощений  . 

       Вхідний блок являє собою послідовність  із 16 бітів, що розділяються на дві частини, права з яких проходить через  блок шифрування , після чого додається по модулю 2 до лівої частини. Вихідне зашифроване повідомлення складається із двох 8-бітних частин, права частина якого являється правою частиною вхідного повідомлення, а ліва – результат додавання по модулю 2.

       Розглянемо  більш детальніше блок. Вхідне 8-бітне повідомлення проходить через блок перестановки із розширенням так, що на виході ми отримуємо 12 бітів.

3

4

1

2

6

8

5

7

3

8

2

4

Таблиця 3.4. Перестановка з розширенням  функції раунду алгоритму спрощений . 

Після цього 12-бітний ключ раунду і перетворене вхідне повідомлення додаються по модулю 2. Результат розділяється на три групи по чотири біти, кожна із яких відповідно проходить через три блоки відповідно : , , . При цьому на виході із перших двох блоків ми отримуємо по три біти, а із другого – два.

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

       Проведемо аналіз першого  блоку підстановок. Розгляд таблиці накладання масок для першого  блоку вказує , що найбільш ефективним лінійним статистичним аналогом буде той, який відповідає парі , хоча очевидно, що одного лінійного рівняння для блоку буде замало. Побудуємо наш лінійний статистичний аналог. В блок підстановки згідно таблиці перестановки із розширенням входять наступні біти у зазначеній послідовності , а вихідні біти після перестановки із стисканням потрапляють на позиції , тобто стають бітами Тепер візьмемо до уваги той факт, що ми працюємо із правою 8-бітною частиною вихідного 16-бітового повідомлення відкритого тексту і врахувавши додавання по модулю 2 лівої частини відкритого тексту із результатом функції отримуємо наступне рівняння: 

Накладання  маски при аналізі блоку  показало, що парі відповідає значення 7. Тому виведене рівняння виконується з імовірністю , відповідно .

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

виконується з імовірністю , та 

виконується з імовірністю , .

Аналогічним чином складаємо рівняння, на основі аналізу двох інших  блоків: другого та третього. Представимо отримані дані у вигляді наступної таблиці:

№ блоку	Ефективне лінійне  рівняння
1.
2.
3.

Таблиця 3.5. Ефективні лінійні статистичні аналоги алгоритму спрощений . 

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

       Використавши  рівняння (2) й (4) отримуємо, що , аналіз (1) й (4) рівнянь системи діє нам інформацію про . Так як , то можливі два варіанти : або , , або ж , . Сьомий біт ключа однозначно визначений третім рівнянням системи: . Користуючись рівнянням (7) , а ця інформація разом із шостим рівнянням визначає . Отже, можливі два варіанти : або , , або ж , .

Отож, провівши аналіз двох блоків маємо 4 можливі  варіанти перших восьми бітів ключа: 
 
 
 

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

       3.4 Висновки 

       Лінійний  криптоаналіз по праву вважається одним із наймогутніших методів атаки, зокрема на симетричні блочні шифри. Для оцінки його ефективності візьмемо метод тотального перебору. Розглянемо найгірший випадок: шуканий ключ буде підібраний останнім. Тепер виникає питання як генерувати ключі. Існують два можливих випадки. Можна зберігати всю множину ключів в пам’яті ЕОМ, але це досить ресурсномісткий варіант. Навіть спрощений варіант DES потребує бітів. Ключі більшої довжини спричинять різке зростання потрібного об’єму пам’яті. Альтернативним варіантом являється застосування алгоритму динамічного генерування ключів. На кожному етапі перевірки нам потрібен об’єм пам’яті для зберігання лише одного ключа, яким ми нехтуємо, проте різко зростає час атаки, оскільки деяка частина процесорного часу буде використовуватись для процедури генерування. Лінійний же крпптоаналіз в даному випадку використав 10 пар відкритий текст-зашифрований текст, що становить бітів. Знову ж , якщо використовувати послідовне генерування ключів, то процесорним часом для 10 пар можна знехтувати. Тепер проаналізуємо складність обох алгоритмів. Таким параметром як час, що витрачається на перевірку одного ключа під час методу тотального перебору чи пари при текстів при застосуванні лінійного крипто аналізу, можна нехтувати, оскільки це значення надзвичайно мізерне і фактично час атаки повністю буде залежати від кількості перевірених текстів/пар. Таким чином складність методу повного перебору для даного прикладу становитиме . Лінійний криптоаналіз був проведений за допомогою 10 пар, що перевірялись для 8 лінійних рівнянь. Врахуємо той факт, що останні 4 біти ми підібрали методом тотального перебору, тобто можливих варіантів, причому для 4 комбінацій попередніх 8-ми бітів. Таким чином складність лінійного крипто аналізу для даного прикладу: . Отже, з упевненістю можна зазначити, що лінійний крипто аналіз виявився ефективнішим в рази. Враховуючи простоту і незначний розмір застосовуваних даних, робимо висновок, що атака методом лінійного крипто аналізу оправдала себе.