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

 

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

 
 

       4.1 Обґрунтування диференціального криптоаналізу 

       Термін  диференціальний крипто аналіз вперше був введений в 1990 році Єлі Біхамом та Аді Шаміром. Використовуючи цей алгоритм, Біхам та Шамір знайшли спосіб атаки на із використанням підібраного відкритого тексту, що виявився ефективнішим ніж атака методом тотального перебору.

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

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

 

Рисунок 4.1. Різності одного циклу перетворення . 

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

Значення  на виході суматора по модулю 2 невідомі, але відома їх різність , причому вона дорівнює : 

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

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

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

Кількість циклів	Вибрані відкриті тексти	Відомі  відкриті текти	Проаналізовані  відкриті тексти	Складність  атаки
8			4	29
9			2
10
11			2
12
13			2
14
15			27
16

складність  може бути зменшена за рахунок збільшення числа відкритх текстів і методу групувань

Таблиця 4.1. Найкращі результати успішного диференціального аналізу . 

     Метод диференційного криптоаналізу вперше був застосований для атаки на блочний шифр . В подальшому він вдосконалюється і успішно застосовується для атаки на стандарт шифрування . Метод диференціального криптоаналізу в свій час дозволив отримати відповідь на питання про число циклів криптографічного перетворення стандарту. Він особливо значущий з точки зору розробки ефективних методів крипто аналізу довільних ітеративних блочних шифрів конструкції Фейстеля. «Питання» формулюється наступним чином: чому число циклів перетворення дорівнює шістнадцяти, не більше й не менше?. Відомо, що після п’яти циклів кожен біт шифротексту являється функцією всіх бітів відкритого тексту й ключа, а після восьми – спостерігається «лавинний ефект» , шифротекст являється випадковою функцією всіх бітів відкритого тексту й ключа. Успішні атаки на з трьома, чотирма та шістьома циклами підтвердили результати досліджень «лавинного ефекту». На перший погляд, криптосистема із кількістю циклів шифрування більше 8 є неоправданою з точки зору ефективності реалізації. Але успішний диференціальний криптоаналіз з кількістю циклів меншим за 16  довів набагато нижчий об’єм перебору ні при атаці методом грубої сили.

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

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

       4.2 Атака методом диференціального криптоаналізу 

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

Вхід  в блок перестановок	Вихід блоку
0000	100	011	01
0001	110	101	10
0010	001	111	11
0011	011	010	01
0100	101	100	10
0101	111	110	11
0110	010	001	01
0111	101	111	10
1000	101	100	11
1001	111	110	01
1010	010	00	10
1011	100	011	11
1100	110	101	01
1101	001	111	10
1110	011	010	11
1111	110	001	01

Таблиця 4.2. Залежність виходів блоків заміни від входів у спрощеному . 

Тепер можна почати аналіз блоків заміни та побудову таблиць залежностей  від

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

Таблиця 4.3. Всі можливі варіанти отримання різниці .

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

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

     Після того як аналіз проведений і таблиці  побудовані можна розпочати визначення найкращого і відповідного йому значення . Аналіз таблиць стверджує, що для блоків 2 та 3 однозначно визначена найкраща пара. Для другого блоку це пара , а для третього відповідно . Таким чином із впевненістю можна ствердити, що однозначно визначені останні 8 бітів , а саме і, звичайно, визначені останні 5 бітів відповідного . Певного роду складнощі виникають у зв’язку з аналізом першого блоку. Якщо уважно поглянути на неї, то стає зрозумілим той факт, що в ній присутні дві рівноймовірнісні пари . А саме: і . Це, в свою чергу, спричиняє появу двох можливих варіантів 12-бітного . Але тут необхідно взяти до уваги наступний важливий факт: дорівнює сумі по модулю 2 розширених і переставлених вхідних бітів. Тому у відповідності до перестановки з розширенням, що використовується в даному алгоритмі шифрування, ідентичними мають бути наступні пари бітів: 1 й 9, 2 й 12, 4 й 11 та 6 і 10. Виходячи з цих міркувань, ми обираємо із двох можливих варіантів єдиний правильний, тобто та відповідне йому . Провівши вдалий аналіз блоків замін й отримавши значення , продовжуємо атаку методом диференціального аналізу безпосередньо користуючись саме цими значеннями.

     Нам знадобиться деяка кількість  пар відкритих текстів та відповідних  їм шифротекстів, таких що т

а .

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

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

  та . Застосуємо відповідні перетворення, щоб отримати для кожного тексту значення та . Маємо:

  ,

,

Як бачимо обрана нами пара правильна, згідно вище сказаному, оскільки відповідає найкращій  парі . Дійсно: 
 

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

  та , після чого на виході буде отримано та . Очевидно, що

, а .

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

Розв’язавши їх, одержимо можливе значення перших чотирьох бітів ключа:

  та 

Розглянемо  другий текст. Значення на виході блоку можна отримати (користуємось таблицею залежностей виходів блоків замін від вхідних даних), якщо на вході у нас або . Таким чином ми отримали два лінійні рівняння: 
 

Розв’язавши їх, одержимо можливе значення перших чотирьох бітів ключа:

  та .

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

  та , після чого на виході буде отримано та . Очевидно, що

, а .

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

Розв’язавши їх, одержимо можливе значення другої четвірки бітів ключа:

  та