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

На початку даної фази шифр ділиться на 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}$. У разі збігу отримаємо кандидата в ключі

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

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

Кожен з 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, однак тоді було проведено часткове порівняння: автори атаки помітили збіг 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 році була здійснена атака[4], яка скорочувала обчислювальну складність алгоритму до ${\displaystyle 2^{72,9}}$ з використанням чотирьох пар відкритого-/закритого тексту.

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

${\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}}$. Це вносить елемент експоненційної складності в даний алгоритм.[5]

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

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

${\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 }$ парами відкритого-/закритого ключа.[5]