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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Початкові умови[ред. | ред. код]

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

Розв'язок простого випадку[ред. | ред. код]

Простим прикладом є подвійне послідовне шифрування блочним алгоритмом двома різними ключами і . Процес шифрування виглядає так: де  — це відкритий текст,  — шифротекст, а  — операція одноразового шифрування ключем . Відповідно, зворотна операція — розшифровка — виглядає так:

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

  1. Всі значення для всіх можливих значень ,
  2. Всі значення для всіх можливих значень .

Потім йому достатньо лише знайти збіги у цих таблицях, тобто такі значення і , що . Кожен збіг відповідає набору ключів, який задовольняє умови, оскільки

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

Розв'язок у загальному вигляді[ред. | ред. код]

Позначимо перетворення алгоритму як , де — Відкритий текст, а — шифротекст. Його можна уявити як композицію , де — циклове перетворення на ключі . Кожен ключ являє собою двійковий вектор довжини , а загальний ключ системи — вектор довжини

1. Заповнення пам'яті. Перебираються всі значення , тобто, перші циклові ключі. На кожному такому ключі зашифруємо відкритий текст - (тобто, проходимо циклів шифрування замість ). Будемо вважати якоюсь адресою пам'яті і за цією адресою запишемо значення . Необхідно перебрати всі значення .

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

Перебираються всі можливі . На отриманих ключах розшифровується шифротекст . Якщо за адресою не пусто, то дістаємо звідти ключ і отримуємо кандидата в ключі .

Однак, потрібно зауважити, що перший же отриманий кандидат не обов'язково є справжнім ключем. Так, для даних і виконується , але на інших значеннях відкритого тексту шифротексту , отриманого з на істинному ключі, рівність може порушуватися. Все залежить від конкретних характеристик криптосистеми. Але іноді буває достатньо отримати такий "псевдоеквівалентний" ключ. В іншому ж разі після завершення процедур буде отримана деяка множина ключів , серед яких знаходиться істинний ключ.

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

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

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

Фаза виділення ключів[ред. | ред. код]

На початку даної фази шифр ділиться на 2 підшифра і як і в загальному випадку атаки, однак допускаючи можливе використання деяких бітів одного підшифра в іншому. Так, якщо , то ; при цьому біти ключа , що використовуються в позначимо , а в - . Тоді ключову послідовність можна розділити на 3 частини:

  1. - перетин множин і ,
  2. - ключові біти, які є тільки в ,
  3. - ключові біти, які є тільки в .

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

  • Для кожного елемента із
  1. Вирахувати проміжне значення , де  — відкритий текст, а  — деякі ключові біти із и , тобто,  — результат проміжного шифрування відкритого тексту на ключі .
  2. Вирахувати проміжне значення
  3. , де  — закритий текст, а  — деякі ключові біти із и , тобто,.  — результат проміжного шифрування відкритого тексту на ключ  
  4. Порівняти і . У разі збігу отримаємо кандидата в ключі

Фаза перевірки ключів[ред. | ред. код]

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

Приклад[ред. | ред. код]

В якості прикладу наведемо атаку на сімейство шифрів KTANTAN[3], яка дозволила зменшити обчислювальну складність отримання ключа з (атака повним перебором) до .[1]

Підготовка атаки[ред. | ред. код]

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

  • В раундах з 1 по 111 не були використані наступні біти ключа: .
  • В раундах з 131 по 254 не були використані наступні біти ключа: .

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

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

Перша фаза: виділення ключів[ред. | ред. код]

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

Друга фаза: перевірка ключів[ред. | ред. код]

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

Результати[ред. | ред. код]

  • KTANTAN32: обчислювальна складність підбору ключа скоротилася до з використанням трьох пар відкритого-/закритого тексту.
  • KTANTAN48: обчислювальна складність підбору ключа скоротилася до з використанням двох пар відкритого-/закритого тексту.
  • KTANTAN64: обчислювальна складність підбору ключа скоротилася до з використанням двох пар відкритого-/закритого тексту.

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

Багатовимірний алгоритм[ред. | ред. код]

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

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

Алгоритм[ред. | ред. код]

  • Обчислюється:
 
зберігається разом з d .
 
зберігається разом з d .
  • Для кожного можливого проміжного стану обчислюється:
 
при кожному збігу з елементом з в зберігаються і ..
 
зберігається разом з в .
  • Для кожного можливого проміжного стану обчислюється:
 
при кажному совпадінні з елементом із проверяеться совпадіння з , пвсля чого в зберігаються и .
 
зберігається разом з в .
  • Для кожного можливого проміжного стану обчислюється:
  при кажному совпадінні з елементом із провіряється совпадіння с , після чого в зберігаються и .
  и при кажному совпадінні с , проверяється совпадіння с

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

Складність[ред. | ред. код]

Часова складність даної атаки становить

Щодо використання пам'яті, легко помітити, що із збільшенням на кожен накладається все більше обмежень, що зменшує кількість записуваних в нього кандидатів. Це означає, що значно менше .

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

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

Складність використання даних залежить від ймовірності "проходження" помилкового ключа. Ця ймовірність дорівнює , де - довжина першого проміжного стану, яка найчастіше дорівнює розміру блоку. Враховуючи кількість кандидатів в ключі після першої фази, складність дорівнює .

В результаті отримуємо , де - розмір блоку.

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

Частина атаки повним перебором (перевірка ключів на нових парах відкритого-/закритого текстів) має часову складність , в котрій, очевидно, наступні доданки дедалі швидше прагнуть до нуля.

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

Примітки[ред. | ред. код]

  1. а б Diffie, Whitfield; Hellman, Martin E. (June 1977). Exhaustive Cryptanalysis of the NBS Data Encryption Standard. 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"
  3. Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. «KATAN & KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers»
  4. Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang, and San Ling. "Improved Meet-in-the-Middle Cryptanalysis of KTANTAN"
  5. а б в Zhu, Bo; Guang Gong (2011). MD-MITM Attack and Its Applications to GOST, KTANTAN and Hummingbird-2. eCrypt. 

Література[ред. | ред. код]

  1. Moore, Stephane (November 16, 2010). Meet-in-the-Middle Attacks. с. 2.