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

 

       2.5 Кількість раундів 

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

       2.6 Слабкості  

       Потягом минулих років криптоаналітики знайшли деякі вразливості стандарту шифрування.

блоки. В літературі вказуються три проблеми блоків:

1. В четвертому блоці три біти виходу можуть бути отримані таким же способом, що й перший біт виходу: доповненням деяких із вхідних бітів
2. Два спеціально обраних входи в масив блоку можуть створити аналогічний вихід4
3. Можна отримати той же самий вихід в одному єдиному раунді, змінюючи біти тільки в трьох сусідніх блоках.

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

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

Таким чином маємо 

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

       Експериментальним чином встановлено, що робоча станція  середньостатистичної потужності за хвилину  перевіряє 8670 ключів. Множина із ключів містить значень. Таким чином, на атаку методом «грубої сили» потрібно затратити близько хвилин або років. Це принципово робить атаку методом тотального перебору неможливою чи хоча б неактуальною, без використання спеціалізованого обладнання.

     Слабкі  ключі

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

Ключі до видалення бітів  парності (64 біти)	Діючі ключі (56 біт)

Таблиця 2.15.Слабкі ключі . 

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

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

       Напівслабкі ключі

       Існують шість пар ключів, що називається  напівслабкими. Вони подані в таблиці нижче: 

Перший  ключ пари	Другий  ключ пари

Таблиця 2.16. Напівслабкі ключі . 

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

 

3. Лінійний  криптоаналіз

 
 

       3.1 Обґрунтування лінійного криптоаналізу 

       Лінійний  крипто аналіз був запропонований Міцуро Мацуі  в його роботі

«M. Matsui. Linear cryptanalysis method for DES cipher. In Advances in

Cryptology – EUROCRYPT’93», volume 765 of LNCS, pages 386–397.

Springer-Verlag, 1993, де він провів його детальний  аналіз та обґрунтування та  узагальнив отримані результати, взявши за основу федеральний  стандарт шифрування Data Encryption Standard. Ним було показано, що може бути успішно атакований за допомогою пар відкритих текстів-шифротекстів, причому швидше ніж повним вичерпним перебором. Пізніше в своїй роботі   «M. Matsui. The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO’94», volume 839 of LNCS, pages 1–11. Springer-Verlag, 1994 Мацуі вдосконалює свою техніку і доводить, що достатньо взагалі відомих пар ( в 16 раз менше! ), причому обґрунтовані нововведення отримали практичне застосування: він реалізовує атаку на протягом 50 днів за допомогою 12 робочих станцій . В свій час атака мала лише теоретичне значення, але це ні в якому разі не виключає можливості її застосування в реальних умовах, оскільки лінійний крипто аналіз по праву вважається одним із найпотужніших способів атаки на .

       Лінійний  криптоаналіз базується на знаннях криптоаналітиком відкритого та зашифрованого текстів в контексті використання блочних схем  шифрування даних, та йому подібних (, ГОСТ тощо). У зв’язку з тим, що стандарт шифрування являється відкритим, тобто заздалегідь відомі всі його таблиці перестановок і підстановок, Мацуі обирає його за основу свого методу крипто аналізу.

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

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

Розглянемо  схему випадкового блочного шифру  в  циклі.

      

Рисунок 3.1. Схема випадкового блочного шифру. 

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

                                               (1)

Позначимо в якості скалярного добутку двох двійкових векторів та вираз наступного вигляду: 

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

Визначення 1. Лінійним статистичним аналогом нелінійної функції (1) будемо називати випадкову величину

                                          (2)

  якщо ймовірність для випадково обраного відкритого тексту . Відхилення визначає ефективність лінійного статистичного аналогу (2). Для застосування лінійного крипто аналізу необхідно вирішити наступні питання:

1. Знайти ефективний статистичний аналог та обчислити його імовірність.
2. Визначити ключ чи деякі біти ключа за допомогою використання лінійного статистичного аналогу.

 

       3.2 Знаходження статистичних аналогів для 1-го циклу алгоритму  

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

Рисунок 3.2. Один раунд (цикл) перетворення. 

Нелінійна функція, що реалізує й блок алгоритму може бути записана у вигляді

  ,                                  (3)

Лінійним  статистичним аналогом кожного із можливих рівнянь (3) буде рівняння вигляду :

, де , , .                           (4)

Позначимо через  – число ненульових для го блоку таких, що для та виконується рівність (4). В цьому випадку значення буде визначати кількість збігів суми по модулю 2 деяких бітів вхідних даних із сумою по модулю 2 деяких бітів вихідних даних. Так як сума по модулю 2 двох однакових бітів ( 1 та 1 чи 0 та 0 ) в результаті лає 0, то фактично буде показувати скільки разів із можливих 64 комбінацій виконується формула (2) із результатом 0. Так яв всього 64 можливі комбінації, то при маємо що

, а .

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

буде  вважатись ефективним лінійним статистичним аналогом для го блоку в класі всіх лінійних статистичних аналогів вигляду (4) з імовірністю . Аналіз всіх восьми блоків показує, що найбільше відхилення від присутнє в блоці. Проаналізуємо його. Шестибітовим входам однозначно відповідають чотирьох бітові виходи. В ході аналізу ми відслідковуємо всі можливі комбінації двійкових векторів та . Кожну пару векторів використовуємо в якості маски, яку накладаємо на всі можливі пари вхід/вихід блоку заміни. Ці маски вказують на біти входу й виходу відповідно, що необхідно скласти по модулю 2, а потім співставити отримані результати. Результат аналізу зображений в таблиці

Таблиця 3.1. Аналіз п’ятого блоку алгоритму шифрування . 

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

       Маємо що , де , для 12 пар входів-виходів блока із наявних 64. Іншими словами, в більшості випадків вони будуть нерівні між собою, а отже, в більшості випадків їх сума по модулю буде дорівнювати 1. Тобто виходить, що  по рівнянню (2) в більшості випадків . Додавши по модулю 2 до правої та лівої частин рівняння отримаємо ефективний статистичний лінійний аналог блоку.  

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

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