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

У криптоаналізі методом зустрічі посередині або атакою «зустріч посередині» (англ. meet-in-the-middle attack) називається клас атак на криптографічні алгоритми, які асимптотично зменшують час повного перебору за рахунок принципу «розділяй і володарюй», а також збільшення об'єму необхідної пам'яті. Вперше цей метод був запропонований Уітфілдом Діффі і Мартіном Геллманом у 1977 році.

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

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

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

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

${\displaystyle p=ENC_{K_{1}}^{-1}(ENC_{K_{2}}^{-1}(s))}$

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

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

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

${\displaystyle {\begin{aligned}s&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(p))\\{\mathit {ENC^{-1}}}_{k_{2}}(s)&={\mathit {ENC^{-1}}}_{k_{2}}({\mathit {ENC}}_{k_{2}}[{\mathit {ENC}}_{k_{1}}(p)])\\{\mathit {ENC^{-1}}}_{k_{2}}(s)&={\mathit {ENC}}_{k_{1}}(p)\\\end{aligned}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приклад

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

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

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

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

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

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

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

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

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

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

Результати

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

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

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

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

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

${\displaystyle C=ENC_{k_{n}}(ENC_{k_{n-1}}(...(ENC_{k_{1}}(P))...))}$ ${\displaystyle P=DEC_{k_{1}}(DEC_{k_{2}}(...(DEC_{k_{n}}(C))...))}$

Алгоритм

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

${\displaystyle sC_{1}=ENC_{f_{1}}(k_{f_{1}},P)}$ ${\displaystyle \forall k_{f_{1}}\in K}$

${\displaystyle sC_{1}}$ зберігається разом з ${\displaystyle k_{1}}$ d ${\displaystyle H_{1}}$.

${\displaystyle sC_{n+1}=DEC_{b_{n+1}}(k_{b_{n+1}},C)}$ ${\displaystyle \forall k_{b_{n+1}}\in K}$

${\displaystyle sC_{n+1}}$ зберігається разом з ${\displaystyle k_{b_{n+1}}}$ d ${\displaystyle H_{b_{n+1}}}$.

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

${\displaystyle sC_{1}=DEC_{b_{1}}(k_{b_{1}},s_{1})}$ ${\displaystyle \forall k_{b_{1}}\in K}$

при кожному збігу ${\displaystyle sC_{1}}$ з елементом з ${\displaystyle H_{1}}$ в ${\displaystyle T_{1}}$ зберігаються ${\displaystyle k_{b_{1}}}$ і ${\displaystyle k_{f_{1}}}$..

${\displaystyle sC_{2}=ENC_{f_{2}}(k_{f_{2}},s_{1})}$ ${\displaystyle \forall k_{f_{2}}\in K}$

${\displaystyle sC_{2}}$ зберігається разом з ${\displaystyle k_{f_{2}}}$ в ${\displaystyle H_{2}}$.

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

${\displaystyle sC_{2}=DEC_{b_{2}}(k_{b_{2}},s_{2})}$ ${\displaystyle \forall k_{b_{2}}\in K}$

при кажному совпадінні ${\displaystyle sC_{2}}$з елементом із ${\displaystyle H_{2}}$ проверяеться совпадіння з ${\displaystyle T_{1}}$, пвсля чого в ${\displaystyle T_{2}}$зберігаються ${\displaystyle k_{b_{2}}}$ и ${\displaystyle k_{f_{2}}}$.

${\displaystyle sC_{3}=ENC_{f_{3}}(k_{f_{3}},s_{2})}$ ${\displaystyle \forall k_{f_{3}}\in K}$

${\displaystyle sC_{3}}$зберігається разом з ${\displaystyle k_{f_{3}}}$ в ${\displaystyle H_{3}}$.

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

${\displaystyle sC_{n}=DEC_{b_{n}}(k_{b_{n}},s_{n})}$ ${\displaystyle \forall k_{b_{n}}\in K}$ при кажному совпадінні ${\displaystyle sC_{n}}$з елементом із ${\displaystyle H_{n}}$ провіряється совпадіння с ${\displaystyle T_{n-1}}$, після чого в ${\displaystyle T_{n}}$зберігаються ${\displaystyle k_{b_{n}}}$ и ${\displaystyle k_{f_{n}}}$.

${\displaystyle sC_{n+1}=ENC_{f_{n+1}}(k_{f_{n+1}},s_{n})}$ ${\displaystyle \forall k_{f_{n+1}}\in K}$ и при кажному совпадінні ${\displaystyle sC_{n+1}}$ с ${\displaystyle H_{n+1}}$, проверяється совпадіння с ${\displaystyle T_{n}}$

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

Складність

Часова складність даної атаки становить ${\displaystyle 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}}|}+...))}$

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

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

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

де ${\displaystyle k}$ - загальна довжина ключа.

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

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

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

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

У підсумку, складність даних за аналогічними судженнями обмежена приблизно ${\displaystyle \left\lceil |k|/n\right\rceil }$ парами відкритого-/закритого ключа.

Примітки

1. Diffie, Whitfield; Hellman, Martin E. (June 1977). . Computer. 10 (6): 74—84. doi:10.1109/C-M.1977.217750. Архів оригіналу за 14 травня 2009. Процитовано 29 липня 2018.
2. Andrey Bogdanov and Christian Rechberger. "A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN" [ 7 листопада 2018 у Wayback Machine.]
3. Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. «KATAN & KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers» [ 20 квітня 2018 у Wayback Machine.]
4. Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang, and San Ling. "Improved Meet-in-the-Middle Cryptanalysis of KTANTAN" [ 7 листопада 2018 у Wayback Machine.]
5. Zhu, Bo; Guang Gong (2011). . eCrypt. Архів оригіналу за 29 липня 2018. Процитовано 29 липня 2018.

Література

1. Moore, Stephane (16 листопада 2010). Meet-in-the-Middle Attacks (PDF): 2.