Лінійний криптоаналіз для чайників

Привіт,% username%!

Багато хто знає, що стандартом за замовчуванням у області симетричного шифрування довгий час вважався алгоритм DES. Перша успішна атака на цей невбиваний алгоритм була опублікована в 1993 році, через 16 років після прийняття його в якості стандарту. Метод, який автор назвав лінійним криптоаналізом, за наявності 2⁴⁷ пар відкритих/зашифрованих текстів, дозволяє розкрити секретний ключ шифра DES за 2⁴³ операцій.

Під палачами я спробую коротко викласти основні моменти цієї атаки.

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

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

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

У першу чергу зловмисник проводить дослідження шифру і знаходить т. зв. статистичний аналог, тобто рівняння наступного виду, що виконується з імовірністю P  1/2 для довільної пари відкритий/закритий текст і фіксованого ключа:

P_I1 ⊕ P_I2 ⊕… ⊕ P_Ia ⊕ C_I1 ⊕ C_I2 ⊕… ⊕ C_Ib = K_I1 ⊕ K_I2 ⊕… ⊕ K_Ic (1),

де P_n, C_n, K_n - n-біти тексту, шифртекста і ключа.

Після того як подібне рівняння буде знайдено атакуючий може відновити 1 біт інформації про ключ, використовуючи наступний алгоритм

Алгоритм 1

Нехай T - кількість текстів, для яких ліва частина рівняння (1) дорівнює 0, тоді

Якщо T > N/2, де N - число відомих відкритих текстів.

Припустити, що K_I1 ⊕ K_I2 ⊕... ⊕ _KIc = 0 (коли P > 1/2) або 1 (коли P < 1/2).

Інакше

Припустити, що K_I1 ⊕ K_I2 ⊕... ⊕ _KIc = 1 (коли P > 1/2) або 0 (коли P < 1/2).

Очевидно, що успіх алгоритму безпосередньо залежить від значення |P - 1/2| і від кількості доступних пар відкритий/закритий текст N. Чим більше ймовірність P рівності (1) відрізняється від 1/2, тим менше кількість відкритих текстів N необхідно для атаки.

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

• Як знайти ефективне рівняння вигляду (1).
• Як за допомогою такого рівняння отримати більше одного біта інформації про ключ.

Розглянемо вирішення цих питань на прикладі шифру DES.

Опис DES

Але для початку коротко опишемо роботу алгоритму. Про DES сказано вже достатньо. Повний опис шифру можна знайти на Вікіпедії. Однак для подальшого пояснення атаки нам буде потрібно ряд визначень які краще ввести заздалегідь.

Отже, DES це блочний шифр, заснований на мережі Фейстеля. Шифр має розмір блоку 64 біти і розмір ключа 56 біт. Розгляньмо схему шифрування алгоритму DES.

Як видно з зображення, під час шифрування тексту виконуються такі дії:

1. Початкова перестановка біт. На цьому етапі біти вхідного блоку перемішуються в певному порядку.
2. Після цього перемішані біти розбиваються на дві половини, які надходять на вхід функції Фейстеля. Для стандартного DES мережа Фейстеля включає 16 раундів, але існують і інші варіанти алгоритму.
3. Два блоки, отриманих на останньому раунді перетворення об'єднуються і над отриманим блоком проводиться ще одна перестановка.

На кожному раунді мережі Фейстеля 32 молодших біти повідомлення проходять через функцію f:

Розглянемо операції, що виконуються на цьому етапі:

1. Вхідний блок проходить через функцію розширення E, яка перетворює 32-бітовий блок на блок довжиною 48 біт.
2. Отриманий блок складається з раундовим ключем K_i.
3. Результат попереднього кроку розбивається на 8 блоків по 6 біт кожен.
4. Кожен з отриманих блоків B_i проходить через функцію підстановки S-Box_i, яка замінює 6-бітну послідовність, 4-бітним блоком.
5. Отриманий в результаті 32-бітний блок проходить через перестановку P і повертається в якості результату функції f.

Найбільший інтерес, з точки зору криптоаналізу шифру, для нас представляють S блоки, призначені для приховування зв'язку між вхідними і вихідними даними функції f. Для успішної атаки на DES ми спершу побудуємо статистичні аналоги для кожного з S-блоків, а потім поширимо їх на весь шифр.

Аналіз S блоків

Кожен S-блок приймає на вхід 6-бітову послідовність, і для кожної такої послідовності повертається фіксоване 4-бітове значення. Тобто. є всього 64 варіанти вхідних і вихідних даних. Наше завдання показати взаємозв'язок між вхідними і вихідними даними S блоків. Наприклад, для третього S-блоку шифра DES, 3-й біт вхідної послідовності дорівнює 3-му біту вихідної послідовності в 38 випадках з 64. Отже, ми знайшли наступний статистичний аналог для третього S-блоку:

S₃ (x) [3] = x [3], який виконується з імовірністю P = 38/64.

Обидві частини рівняння представляють 1 біт інформації. Тому у випадку якщо б ліва і права частини були незалежні один від одного, рівняння повинно було б виконуватися з ймовірністю рівною 1/2. Таким чином, ми тільки що продемонстрували зв'язок між вхідними і вихідними даними 3-го S-блоку алгоритму DES.

Розглянемо як можна знайти статистичний аналог S-блоку в загальному випадку.

Для S-блоку S_a, 1-1-3 і 1-1-15 значення NS_a (В'єрх) описує скільки разів з 64 можливих XOR вхідних біт S_a накладених на біти дорівнюють XOR вихідних біт, накладених на біти, тобто:

де символ • - логічне І.

Значення порожніх, для яких NS_a (В) найбільше відрізняється від 32, описують найефективніший статистичний аналог S-блоку S_a.

Найбільш ефективний аналог був знайдений в 5-му S-блоці шифру DES для  = 16 і  = 15 NS₅ (16, 15) = 12. Це означає, що справедливо таке рівняння: Z [2] = Y [1] ⊕ Y [2] ⊕ Y [3] ⊕ Y [4], де Z - вхідна послідовність S-блоку, а Y - вихідна послідовність.

Або з урахуванням того, що в алгоритмі DES перед входом в S-блок дані складаються за модулем 2 з раундовим ключем, тобто Z [2] = X [2] ⊕ K [2] отримуємо

X [2] ⊕ Y [1] ⊕ Y [2] ⊕ Y [3] ⊕ Y [4] = K [2], де X і Y - вхідні та вихідні дані функції f без урахування перестановок.

Отримане рівняння виконується на всіх раундах алгоритму DES з однаковою ймовірністю P = 12/64.

На наступній таблиці наведено список ефективних, тобто таких, що мають найбільше відхилення від P = 1/2, статистичних аналогів для кожного s-блоку алгоритму DES.

Побудова статистичних аналогів для декількох раундів DES

Покажемо тепер яким чином можна об'єднати статистичні аналоги декількох раундів DES і в підсумку отримати статистичний аналог для всього шифру.

Для цього розглянемо трираундову версію алгоритму:

Застосуємо ефективний статистичний аналог 5-го s-блоку для обчислення певних біт значення X (2).

Ми знаємо що з ймовірністю 12/64 у f-функції виконується рівність X [2] ⊕ Y [1] ⊕ Y [2] ⊕ Y [3] ⊕ Y [4] = K [2], де X [2] - другий вхідний біт 5-го S-блоку, він по суті є 26-м битом послідовності, отриманої після розширення вхідних біт. Аналізуючи функцію розширення можна встановити що на місці 26 біта виявляється 17-й біт послідовності X (1).

Аналогічним чином, Y [1],..., Y [4] по суті є 17-м, 18-м, 19-м і 20-м битом послідовності отриманої до перестановки P. Дослідивши перестановку P, отримуємо що біти Y [1],..., Y [4] насправді є битами Y (1) [3], Y (1) [8], Y (1) [14], Y (25)

Біт ключа K [2] залучений до рівняння є 26 битом підключення першого раунду K1 і тоді статистичний аналог набуває наступної форми:

X(1)[17] ⊕ Y(1)[3] ⊕ Y(1)[8] ⊕ Y1[14] ⊕ Y(1)[25] = K1[26].

Отже, X (1) [17] ⊕ K1 [26] = Y (1) [3] ⊕ Y (1) [8] ⊕ Y (1) [14] ⊕ Y (1) [25] (2) з ймовірністю P = 12/64.

Знаючи 3, 8, 14, 25 біти послідовності Y (1) можна знайти 3, 8, 14, 25 біти послідовності X (2):

X (2) [3] ⊕ X (2) [8] ⊕ X (2) [14] ⊕ X (2) [25] = PL [3] ⊕ PL [8] ⊕ PL [14] ⊕ PL [25] ⊕ Y (1) [3] ⊕ Y (1) [8] ⊕ Y (1) [14] ⊕ Y (1) [25] або з урахуванням рівнянності (2)

X (2) [3] ⊕ X (2) [8] ⊕ X (2) [14] ⊕ X (2) [25] = PL [3] ⊕ PL [8] ⊕ PL [14] ⊕ PL [25] ⊕ X (1) [17] ⊕ K1 [26] (3) з імовірністю 12/64.

Знайдемо подібний вираз використовуючи останній раунд. Цього разу ми маємо рівняння

X(3)[17] ⊕ K3[26] = Y(3)[3] ⊕ Y(3)[8] ⊕ Y(3)[14] ⊕ Y(3)[25].

Так як

X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] = СL[3] ⊕ СL[8] ⊕ СL[14] ⊕ СL[25] ⊕ Y(3)[3] ⊕ Y(3)[8] ⊕ Y(3)[14] ⊕ Y(3)[25]

отримуємо, що

X (2) [3] ⊕ X (2) [8] ⊕ X (2) [14] ⊕ X (2) [25] = CL [3] ⊕ CL [8] ⊕ CL [14] ⊕ CL [25] ⊕ X (3) [17] ⊕ K3 [26] (4) з імовірністю 12/64.

Прирівняти праві частини рівнянь (3) і (4) отримуємо

CL [3] ⊕ CL [8] ⊕ CL [14] ⊕ CL [25] ⊕ X (3) [17] ⊕ K3 [26] = PL [3] ⊕ PL [8] ⊕ PL [14] ⊕ PL [25] ⊕ X (1) [17] ⊕ K1 [26] з імовірністю (12/⁶4) 2 + (1-12/64) 2).

З урахуванням того, що X (1) = PR і X (3) = CR отримуємо статистичний аналог

СL[3, 8, 14, 25] ⊕ CR[17] ⊕ PL[3, 8, 14, 25] ⊕ PR[17] = K1[26] ⊕ K3[26] (5),

який виконується з імовірністю (12/64) ² + (1-12/64) ² = 0.7.

Описаний вище статистичний аналог можна уявити графічно наступним чином (біти на малюнку пронумеровані справа наліво і починаючи з нуля):

Всі біти в лівій частині рівняння відомі атакуючому, отже він може застосувати алгоритм 1 і дізнатися значення K1 [17] ⊕ K3 [17]. Покажемо як за допомогою даного статистичного аналога можна розкрити не 1, а 12 біт ключа шифрування K.

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

Наведемо спосіб за допомогою якого можна розширити атаку і отримати відразу 6 біт підключення першого раунду.

Складаючи рівняння (5) ми брали до уваги той факт, що нам невідоме значення F1 (PR, K1) [3, 8, 14, 25]. Тому ми використовували його статистичний аналог K1 [26] ⊕ PR [17].

Повернемо замість виразу K1 [26] ⊕ PR [17] значення F1 (PR, K1) [3, 8, 14, 25] і отримаємо таке рівняння:

CL [3, 8, 14, 25] ⊕ CR [17] ⊕ PL [3, 8, 14, 25] ⊕ F1 (PR, K1) [3, 8, 14, 25] = K3 [26] (6), яке виконуватиметься з імовірністю 12/64. Ймовірність змінилася так як ми залишили тільки статистичний аналог з третього раунду, всі інші значення фіксовані.

Вище ми вже визначили, що на значення F1 (PR, K1) [3, 8, 14, 25] впливають вхідні біти 5-го S-блоку, а саме біти ключа K1 [25 млрд 30] і біти блоку PR [16 млрд 21]. Якщо буде позначено цей пункт, ви зможете відновити K1 [25... 30] лише набором відкритих або закритих текстів. Для цього скористаємося алгоритмом 2.

Алгоритм 2

Нехай N - кількість відомих перед атакою пар відкритий/закритий текст. Тоді для розтину ключа необхідно виконати наступні кроки.

For (i=0; i<64; i++) do

{

For(j=0; j<N; j++) do

{

if(СL_j[3, 8, 14, 25] ⊕ CR_j[17] ⊕ PL_j[3, 8, 14, 25] ⊕ F1(PR_j, i)[3, 8, 14, 25]=0) then

T_i=T_i+1

}

}

Як ймовірну послідовність K1 [25 млрд 30] приймається таке значення i, при якому вираз |T_i - N/2| має максимальне значення.

При достатній кількості відомих відкритих текстів алгоритм буде з великою ймовірністю повертати коректне значення шести біт з'єднання першого раунду K1 [25 млрд 30]. Пояснюється тим, що якщо змінна i не дорівнює K1 [25 млрд 30], тоді значення функції F1 (PR_j, K) [3, 8, 14, 25] буде випадковим і кількість рівнянь для такого значення i, при якому ліва частина дорівнює нулю буде прагнути до N/2. У разі ж якщо  вгаданий вірно, ліва частина буде з імовірністю 12/64 дорівнює фіксованому біту K3 [26]. Тобто. спостерігатиметься значне відхилення від N/2.

Отримавши 6 біт з «єднання K1, ви можете розкрити 6 біт з» єднання K3. Все що для цього потрібно, це замінити в рівнянні (6) C на P і K1 на K3:

PL[3, 8, 14, 25] ⊕ PR[17] ⊕ CL[3, 8, 14, 25] ⊕ F3(CR, K3)[3, 8, 14, 25] = K1[26].

Алгоритм 2 повертає коректне значення K3 [25 ауд 30] тому що процес розшифрування алгоритму DES ідентичний процесу шифрування, просто послідовність ключів змінюється місцями. Так, на першому раунді розшифрування використовується ключ K3, а на останньому ключ K1.

Отримавши по 6 біт підключів K1 і K3 зловмисник відновлює 12 біт загального ключа шифра K, оскільки раундові ключі є звичайною перестановкою ключа K. Кількість відкритих текстів необхідних для успішної атаки залежить від ймовірності статистичного аналога. Для розтину 12 біт ключа 3-раундового DES достатньо 100 пар відкритих/закритих текстів. Для розтину 12 біт ключа 16-раундового DES потрібно близько 2⁴⁴ пар текстів. Інші 44 біти ключа розкриваються звичайним перебором.

Посилання

Mitsuru Matsui — Linear cryptanalysis method of DES cipher

Tutorial on Linear and Differential Cryptanalysis