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

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

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

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

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

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

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

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

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

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

${\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}}$

Для даної атаки потрібно $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 частини

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

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

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

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

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

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

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

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

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

Приклад

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

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

Кожен з 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}$.

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

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

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

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

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

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

Результати

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Складність

Часова складність даної атаки становить $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|-2b}$, де $|b|$ - розмір блоку.

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

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

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

Література

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