Метод зустрічі посередині

У криптоаналізі методом зустрічі посередині або атакою «зустріч посередині» (Шаблон:Lang-en) називається клас атак на криптографічні алгоритми, які асимптотично зменшують час повного перебору за рахунок принципу «розділяй і володарюй», а також збільшення об'єму необхідної пам'яті. Вперше цей метод був запропонований Уітфілдом Діффі і Мартіном Геллманом у 1977 році.^[1]

Початкові умови

Існують відкритий (незашифрований) і шифрований тексти. Криптосистема складається із $h$ циклів шифрування. Циклові ключі незалежні й не мають спільних бітів. Ключ $K$ системи являє собою поєднання із $h$ - циклових ключів $k_{1}, k_{2} . . . k_{h}$ . Завдання полягає в знаходженні ключа $K$ .

Розв'язок простого випадку

Простим прикладом є подвійне послідовне шифрування блочним алгоритмом двома різними ключами $K_{1}$ і $K_{2}$ . Процес шифрування виглядає так: $s = E N C_{K_{2}} (E N C_{K_{1}} (p))$ де $p$ — це відкритий текст, $s$ — шифротекст, а $E N C_{K_{i}} ()$ — операція одноразового шифрування ключем $K_{i}$ . Відповідно, зворотна операція — розшифровка — виглядає так:

$p = E N C_{K_{1}}^{- 1} (E N C_{K_{2}}^{- 1} (s))$

На перший погляд здається, що застосування подвійного шифрування багаторазово збільшує стійкість всієї схеми, оскільки перебирати тепер потрібно два ключі, а не один. У разі алгоритму DES стійкість збільшується з $2^{56}$ до $2^{112}$ . Однак це не так. Атакуючий може скласти дві таблиці:

Всі значення $m_{1} = E N C_{K_{1}} (p)$ для всіх можливих значень $K_{1}$ ,
Всі значення $m_{2} = E N C_{K_{2}}^{- 1} (s)$ для всіх можливих значень $K_{2}$ .

Потім йому достатньо лише знайти збіги у цих таблицях, тобто такі значення $m_{1}$ і $m_{2}$ , що $E N C_{K_{1}} (p) = E N C_{K_{2}}^{- 1} (s)$ . Кожен збіг відповідає набору ключів $(K_{1}, K_{2})$ , який задовольняє умови, оскільки

\begin{matrix} s & = {𝐸 𝑁 𝐶}_{k_{2}} ({𝐸 𝑁 𝐶}_{k_{1}} (p)) \\ {𝐸 𝑁 𝐶^{- 1}}_{k_{2}} (s) & = {𝐸 𝑁 𝐶^{- 1}}_{k_{2}} ({𝐸 𝑁 𝐶}_{k_{2}} [{𝐸 𝑁 𝐶}_{k_{1}} (p)]) \\ {𝐸 𝑁 𝐶^{- 1}}_{k_{2}} (s) & = {𝐸 𝑁 𝐶}_{k_{1}} (p) \end{matrix}

Для даної атаки потрібно $2^{57}$ операцій шифрування-розшифрування (лише удвічі більше, ніж для перебору одного ключа) і $2^{57}$ пам'яті. Додаткові оптимізації — використання хеш-таблиць, обчислення тільки для половини ключів (для DES повний перебір, насправді, вимагає лише $2^{55}$ операцій) — можуть знизити ці вимоги. Головний результат атаки полягає в тому, що послідовне шифрування двома ключами збільшує час перебору лише удвічі.

Розв'язок у загальному вигляді

Позначимо перетворення алгоритму як $E_{k} (a) = b$ , де $a$ — Відкритий текст, а $b$ — шифротекст. Його можна уявити як композицію $E_{k_{1}} E_{k_{2}} . . . E_{k_{h}} (a) = b$ , де $E_{k_{i}}$ — циклове перетворення на ключі $E_{k_{i}}$ . Кожен ключ $k_{i}$ являє собою двійковий вектор довжини $n$ , а загальний ключ системи — вектор довжини $n \times h$

1. Заповнення пам'яті. Перебираються всі значення $k^{'} = (k_{1}, k_{2} . . . k_{r})$ , тобто, перші $r$ циклові ключі. На кожному такому ключі $k^{'}$ зашифруємо відкритий текст $a$ - $E_{k^{'}} (a) = E_{k_{1}} E_{k_{2}} . . . E_{k_{r}} (a) = S$ (тобто, проходимо $r$ циклів шифрування замість $h$ ). Будемо вважати $S$ якоюсь адресою пам'яті і за цією адресою запишемо значення $k^{'}$ . Необхідно перебрати всі значення $k^{'}$ .

2. Визначення ключа.

Перебираються всі можливі $k^{″} = (k_{r + 1}, k_{r + 2} . . . k_{h})$ . На отриманих ключах розшифровується шифротекст $b$ — $E_{k^{″}}^{- 1} (b) = E_{k_{h}}^{- 1} . . . E_{k_{r + 1}}^{- 1} (b) = S^{'}$ . Якщо за адресою $S^{'}$ не пусто, то дістаємо звідти ключ $k^{'}$ і отримуємо кандидата в ключі $(k^{'}, k^{″}) = k$ .

Однак, потрібно зауважити, що перший же отриманий кандидат $k$ не обов'язково є справжнім ключем. Так, для даних $a$ і $b$ виконується $E_{k} (a) = b$ , але на інших значеннях відкритого тексту $a^{'}$ шифротексту $b^{'}$ , отриманого з $a^{'}$ на істинному ключі, рівність може порушуватися. Все залежить від конкретних характеристик криптосистеми. Але іноді буває достатньо отримати такий "псевдоеквівалентний" ключ. В іншому ж разі після завершення процедур буде отримана деяка множина ключів $k^{'}, k^{″} . . .$ , серед яких знаходиться істинний ключ.

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

Атака з розбиттям ключової послідовності на 3 частини

У деяких випадках буває важко розділити біти послідовності ключів на частини, що належать до різних ключів. В такому разі застосовують алгоритм Шаблон:Iw, запропонований Богдановим і Річбергером в 2011 році на основі звичайного методу зустрічі посередині. Даний алгоритм застосовується в разі відсутності можливості поділу послідовності ключових бітів на дві незалежні частини, як необхідно в звичайному алгоритмі методу зустрічі посередині. Складається з двох фаз: фази виділення і перевірки ключів.^[2]

Фаза виділення ключів

На початку даної фази шифр ділиться на 2 підшифра $f$ і $g$ як і в загальному випадку атаки, однак допускаючи можливе використання деяких бітів одного підшифра в іншому. Так, якщо $b = E_{k} (a)$ , то $E_{k} (*) = f (g (*))$ ; при цьому біти ключа $k$ , що використовуються в $f$ позначимо $k_{f}$ , а в $g$ - $k_{g}$ . Тоді ключову послідовність можна розділити на 3 частини:

$A_{0}$ - перетин множин $k_{f}$ і $k_{g}$ ,
$A_{1}$ - ключові біти, які є тільки в $k_{f}$ ,
$A_{2}$ - ключові біти, які є тільки в $k_{f}$ .

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

Для кожного елемента із $A_{0}$

Вирахувати проміжне значення $i = f (k_{f}, a)$ , де $a$ — відкритий текст, а $k_{f}$ — деякі ключові біти із $A_{0}$ и $A_{1}$ , тобто, $i$ — результат проміжного шифрування відкритого тексту на ключі $k_{f}$ .
Вирахувати проміжне значення
$j = g^{- 1} (k_{g}, b)$ , де $b$ — закритий текст, а $k_{g}$ — деякі ключові біти із $A_{0}$ и $A_{2}$ , тобто,. $j$ — результат проміжного шифрування відкритого тексту на ключ $k_{g}$
Порівняти $i$ і $j$ . У разі збігу отримаємо кандидата в ключі

Фаза перевірки ключів

Для перевірки ключів отримані кандидати перевіряють на декількох парах відомих відкритих-/закритих текстів. Зазвичай для перевірки потрібно не дуже велика кількість таких пар текстів.^[2]

Приклад

Як приклад наведемо атаку на сімейство шифрів KTANTAN^[3], яка дозволила зменшити обчислювальну складність отримання ключа з $2^{80}$ (атака повним перебором) до $2^{75, 170}$ .^[1]

Підготовка атаки

Кожен з 254 раундів шифрування з використанням KTANTAN використовує 2 випадкових біта ключа з 80-бітного набору. Це робить складність алгоритму залежною тільки від кількості раундів. Приступаючи до атаки, автори помітили наступні особливості:

В раундах з 1 по 111 не були використані наступні біти ключа: $k_{32}, k_{39}, k_{44}, k_{61}, k_{66}, k_{75}$ .
В раундах з 131 по 254 не були використані наступні біти ключа: $k_{3}, k_{20}, k_{41}, k_{47}, k_{63}, k_{74}$ .

Це дозволило розділити біти ключа на наступні групи:

$A_{0}$ - загальні біти ключа: ті 68 біт, що не згадані вище.
$A_{1}$ - біти, що використовуються тільки в першому блоці раундів (з 1 по 111),
$A_{2}$ - біти, які використовуються тільки у другому блоці раундів (з 131 по 254).

Перша фаза: виділення ключів

Виникала проблема обчислення описаних вище значень $i$ і $j$ , так як в розгляді відсутні раунди з 112 по 130, однак тоді було проведено Шаблон:Iw: автори атаки помітили збіг 8 біт в $i$ і $j$ , перевіривши їх звичайною атакою методом зустрічі посередині на 127 раунді. У зв'язку з цим у даній фазі порівнювалися значення саме цих 8 біт в підшифрах $i$ і $j$ . Це збільшило кількість кандидатів у ключі, але не складність обчислень.

Друга фаза: перевірка ключів

Для перевірки кандидатів в ключі алгоритму KTANTAN32 було потрібно в середньому ще дві пари відкритого-/закритого текстів для виділення ключа.

Результати

KTANTAN32: обчислювальна складність підбору ключа скоротилася до $2^{75, 170}$ з використанням трьох пар відкритого-/закритого тексту.
KTANTAN48: обчислювальна складність підбору ключа скоротилася до $2^{75, 044}$ з використанням двох пар відкритого-/закритого тексту.
KTANTAN64: обчислювальна складність підбору ключа скоротилася до $2^{75, 584}$ з використанням двох пар відкритого-/закритого тексту.

Тим не менш, це не найкраща атака на сімейство шифрів KTANTAN. У 2011 році була здійснена атака^[4], яка скорочувала обчислювальну складність алгоритму до $2^{72, 9}$ з використанням чотирьох пар відкритого-/закритого тексту.

Багатовимірний алгоритм

Багатовимірний алгоритм методу зустрічі посередині застосовується при використанні великої кількості циклів шифрування різними ключами на блокових шифрах. Замість звичайної «зустріч посередині» в даному алгоритмі використовується поділ криптотексту кількома проміжними точками.^[5]

Припускається, що атакується текст, зашифрований деяку кількість разів блоковим шифром:

$C = E N C_{k_{n}} (E N C_{k_{n - 1}} (. . . (E N C_{k_{1}} (P)) . . .))$ $P = D E C_{k_{1}} (D E C_{k_{2}} (. . . (D E C_{k_{n}} (C)) . . .))$

Алгоритм

Обчислюється:

s C_{1} = E N C_{f_{1}} (k_{f_{1}}, P)

\forall k_{f_{1}} \in K

s C_{1}

зберігається разом з

k_{1}

d

H_{1}

.

s C_{n + 1} = D E C_{b_{n + 1}} (k_{b_{n + 1}}, C)

\forall k_{b_{n + 1}} \in K

s C_{n + 1}

зберігається разом з

k_{b_{n + 1}}

d

H_{b_{n + 1}}

.

Для кожного можливого проміжного стану $s_{1}$ обчислюється:

s C_{1} = D E C_{b_{1}} (k_{b_{1}}, s_{1})

\forall k_{b_{1}} \in K

при кожному збігу

s C_{1}

з елементом з

H_{1}

в

T_{1}

зберігаються

k_{b_{1}}

і

k_{f_{1}}

..

s C_{2} = E N C_{f_{2}} (k_{f_{2}}, s_{1})

\forall k_{f_{2}} \in K

s C_{2}

зберігається разом з

k_{f_{2}}

в

H_{2}

.

Для кожного можливого проміжного стану $s_{2}$ обчислюється:

s C_{2} = D E C_{b_{2}} (k_{b_{2}}, s_{2})

\forall k_{b_{2}} \in K

при кажному совпадінні

s C_{2}

з елементом із

H_{2}

проверяеться совпадіння з

T_{1}

, пвсля чого в

T_{2}

зберігаються

k_{b_{2}}

и

k_{f_{2}}

.

s C_{3} = E N C_{f_{3}} (k_{f_{3}}, s_{2})

\forall k_{f_{3}} \in K

s C_{3}

зберігається разом з

k_{f_{3}}

в

H_{3}

.

Для кожного можливого проміжного стану $s_{1}$ обчислюється:

s C_{n} = D E C_{b_{n}} (k_{b_{n}}, s_{n})

\forall k_{b_{n}} \in K

при кажному совпадінні

s C_{n}

з елементом із

H_{n}

провіряється совпадіння с

T_{n - 1}

, після чого в

T_{n}

зберігаються

k_{b_{n}}

и

k_{f_{n}}

.

s C_{n + 1} = E N C_{f_{n + 1}} (k_{f_{n + 1}}, s_{n})

\forall k_{f_{n + 1}} \in K

и при кажному совпадінні

s C_{n + 1}

с

H_{n + 1}

, проверяється совпадіння с

T_{n}

Далі знайдена послідовність кандидатів тестується на іншій парі відкритого-/закритого тексту для підтвердження істинності ключів. Слід зауважити рекурсивність в алгоритмі: підбір ключів для стану $s_{j}$ відбувається на основі результатів для стану $s_{j - 1}$ . Це вносить елемент експоненційної складності в даний алгоритм.^[5]

Складність

Часова складність даної атаки становить $2^{| k_{f_{1}} |} + 2^{| k_{b_{n + 1}} |} + 2^{| s_{1} |} \cdot (2^{| k_{b_{1}} |} + 2^{| k_{f_{2}} |} + 2^{| s_{2} |} \cdot (2^{| k_{b_{2}} |} + 2^{| k_{f_{3}} |} + . . .))$

Щодо використання пам'яті, легко помітити, що із збільшенням $i$ на кожен $T_{i}$ накладається все більше обмежень, що зменшує кількість записуваних в нього кандидатів. Це означає, що $T_{2}, T_{3}, . . ., T_{n}$ значно менше $T_{1}$ .

Верхня межа обсягу використаної пам'яті:

2^{| k_{f_{1}} |} + 2^{| k_{b_{n + 1}} |} + 2^{| k | - | s + n |} + . . .

де

k

- загальна довжина ключа.

Складність використання даних залежить від ймовірності "проходження" помилкового ключа. Ця ймовірність дорівнює $1 / 2^{l}$ , де $l$ - довжина першого проміжного стану, яка найчастіше дорівнює розміру блоку. Враховуючи кількість кандидатів в ключі після першої фази, складність дорівнює $2^{| k | - | l |}$ .

В результаті отримуємо $2^{| k | - 2 b}$ , де $| b |$ - розмір блоку.

Кожен раз, коли послідовність кандидатів у ключі тестується на новій парі відкритого-/закритого тексту, кількість ключів, які успішно проходять перевірку, множиться на імовірність проходження ключа, яка дорівнює $1 / 2^{| b |}$ .

Частина атаки повним перебором (перевірка ключів на нових парах відкритого-/закритого текстів) має часову складність $2^{| k | - b} + 2^{| k | - 2 b} + 2^{| k | - 3 b} + . . .$ , в котрій, очевидно, наступні доданки дедалі швидше прагнуть до нуля.

У підсумку, складність даних за аналогічними судженнями обмежена приблизно $⌈ | k | / n ⌉$ парами відкритого-/закритого ключа.^[5]

Примітки

Шаблон:Reflist

Література

Шаблон:Cite journal

↑ ^1,0 ^1,1 Шаблон:Cite journal
↑ ^2,0 ^2,1 Andrey Bogdanov and Christian Rechberger. "A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN" Шаблон:Webarchive
↑ Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. «KATAN & KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers» Шаблон:Webarchive
↑ Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang, and San Ling. "Improved Meet-in-the-Middle Cryptanalysis of KTANTAN" Шаблон:Webarchive
↑ ^5,0 ^5,1 ^5,2 Шаблон:Cite journal

[dh-1] 1,0 ^1,1 Шаблон:Cite journal

[3dmitm-2] 2,0 ^2,1 Andrey Bogdanov and Christian Rechberger. "A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN" Шаблон:Webarchive

[3] Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. «KATAN & KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers» Шаблон:Webarchive

[4] Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang, and San Ling. "Improved Meet-in-the-Middle Cryptanalysis of KTANTAN" Шаблон:Webarchive

[ZhuGuang2011-5] 5,0 ^5,1 ^5,2 Шаблон:Cite journal

[1]

[2]

[3]

[4]

[5]

Метод зустрічі посередині

Зміст

Початкові умови

Розв'язок простого випадку

Розв'язок у загальному вигляді

Атака з розбиттям ключової послідовності на 3 частини

Фаза виділення ключів

Фаза перевірки ключів

Приклад

Підготовка атаки

Перша фаза: виділення ключів

Друга фаза: перевірка ключів

Результати

Багатовимірний алгоритм

Алгоритм

Складність

Примітки

Література

Навігаційне меню

Метод зустрічі посередині

Початкові умови

Розв'язок простого випадку

Розв'язок у загальному вигляді

Атака з розбиттям ключової послідовності на 3 частини

Фаза виділення ключів

Фаза перевірки ключів

Приклад

Підготовка атаки

Перша фаза: виділення ключів

Друга фаза: перевірка ключів

Результати

Багатовимірний алгоритм

Алгоритм

Складність

Примітки

Література

Навігаційне меню

Пошук