У криптоаналізі методом зустрічі посередині або атакою «зустріч посередині» () називається клас атак на криптографічні алгоритми, які асимптотично зменшують час повного перебору за рахунок принципу «розділяй і володарюй», а також збільшення об'єму необхідної пам'яті. Вперше цей метод був запропонований Уітфілдом Діффі і Мартіном Геллманом у 1977 році.
Початкові умови Існують відкритий (незашифрований) і шифрований тексти. Криптосистема складається із циклів шифрування. Циклові ключі незалежні й не мають спільних бітів. Ключ системи являє собою поєднання із - циклових ключів . Завдання полягає в знаходженні ключа .
Розв'язок простого випадку Простим прикладом є подвійне послідовне шифрування блочним алгоритмом двома різними ключами і . Процес шифрування виглядає так:
де — це відкритий текст, — шифротекст, а — операція одноразового шифрування ключем . Відповідно, зворотна операція — розшифровка — виглядає так:
На перший погляд здається, що застосування подвійного шифрування багаторазово збільшує стійкість всієї схеми, оскільки перебирати тепер потрібно два ключі, а не один. У разі алгоритму DES стійкість збільшується з до . Однак це не так. Атакуючий може скласти дві таблиці:
Всі значення для всіх можливих значень , Всі значення для всіх можливих значень .
Потім йому достатньо лише знайти збіги у цих таблицях, тобто такі значення і , що . Кожен збіг відповідає набору ключів, який задовольняє умови, оскільки
Для даної атаки потрібно операцій шифрування-розшифрування (лише удвічі більше, ніж для перебору одного ключа) і пам'яті. Додаткові оптимізації — використання хеш-таблиць, обчислення тільки для половини ключів (для DES повний перебір, насправді, вимагає лише операцій) — можуть знизити ці вимоги. Головний результат атаки полягає в тому, що послідовне шифрування двома ключами збільшує час перебору лише удвічі.
Розв'язок у загальному вигляді
Позначимо перетворення алгоритму як , де — Відкритий текст, а — шифротекст. Його можна уявити як композицію , де — циклове перетворення на ключі . Кожен ключ являє собою двійковий вектор довжини , а загальний ключ системи — вектор довжини
1. Заповнення пам'яті. Перебираються всі значення , тобто, перші циклові ключі. На кожному такому ключі зашифруємо відкритий текст - (тобто, проходимо циклів шифрування замість ). Будемо вважати якоюсь адресою пам'яті і за цією адресою запишемо значення . Необхідно перебрати всі значення .
2. Визначення ключа.
Перебираються всі можливі . На отриманих ключах розшифровується шифротекст — . Якщо за адресою не пусто, то дістаємо звідти ключ і отримуємо кандидата в ключі .
Однак, потрібно зауважити, що перший же отриманий кандидат не обов'язково є справжнім ключем. Так, для даних і виконується , але на інших значеннях відкритого тексту шифротексту , отриманого з на істинному ключі, рівність може порушуватися. Все залежить від конкретних характеристик криптосистеми. Але іноді буває достатньо отримати такий "псевдоеквівалентний" ключ. В іншому ж разі після завершення процедур буде отримана деяка множина ключів , серед яких знаходиться істинний ключ.
Якщо розглядати конкретне застосування, то шифротекст і відкритий текст можуть бути великого обсягу (наприклад, графічні файли) і являти собою досить велике число блоків для блокового шифру. В такому разі для прискорення процесу можна зашифровувати і розшифровувати не весь текст, а лише його перший блок (що набагато швидше), і потім, отримавши безліч кандидатів, шукати в ньому справжній ключ, перевіряючи його на інших блоках.
Атака з розбиттям ключової послідовності на 3 частини У деяких випадках буває важко розділити біти послідовності ключів на частини, що належать до різних ключів. В такому разі застосовують алгоритм , запропонований Богдановим і Річбергером в 2011 році на основі звичайного методу зустрічі посередині. Даний алгоритм застосовується в разі відсутності можливості поділу послідовності ключових бітів на дві незалежні частини, як необхідно в звичайному алгоритмі методу зустрічі посередині. Складається з двох фаз: фази виділення і перевірки ключів.Andrey Bogdanov and Christian Rechberger. "A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN"
Фаза виділення ключів На початку даної фази шифр ділиться на 2 підшифра і як і в загальному випадку атаки, однак допускаючи можливе використання деяких бітів одного підшифра в іншому. Так, якщо , то ; при цьому біти ключа , що використовуються в позначимо , а в - . Тоді ключову послідовність можна розділити на 3 частини:
- перетин множин і , - ключові біти, які є тільки в , - ключові біти, які є тільки в .
Далі проводиться атака методом зустрічі посередині за наступним алгоритмом:
Для кожного елемента із Вирахувати проміжне значення , де — відкритий текст, а — деякі ключові біти із и , тобто, — результат проміжного шифрування відкритого тексту на ключі . Вирахувати проміжне значення , де — закритий текст, а — деякі ключові біти із и , тобто,. — результат проміжного шифрування відкритого тексту на ключ Порівняти і . У разі збігу отримаємо кандидата в ключі
Фаза перевірки ключів Для перевірки ключів отримані кандидати перевіряють на декількох парах відомих відкритих-/закритих текстів. Зазвичай для перевірки потрібно не дуже велика кількість таких пар текстів.
Приклад Як приклад наведемо атаку на сімейство шифрів KTANTANChristophe De Cannière, Orr Dunkelman, Miroslav Knežević. «KATAN & KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers» , яка дозволила зменшити обчислювальну складність отримання ключа з (атака повним перебором) до .
Підготовка атаки Кожен з 254 раундів шифрування з використанням KTANTAN використовує 2 випадкових біта ключа з 80-бітного набору. Це робить складність алгоритму залежною тільки від кількості раундів. Приступаючи до атаки, автори помітили наступні особливості:
В раундах з 1 по 111 не були використані наступні біти ключа: . В раундах з 131 по 254 не були використані наступні біти ключа: .
Це дозволило розділити біти ключа на наступні групи:
- загальні біти ключа: ті 68 біт, що не згадані вище. - біти, що використовуються тільки в першому блоці раундів (з 1 по 111), - біти, які використовуються тільки у другому блоці раундів (з 131 по 254).
Перша фаза: виділення ключів Виникала проблема обчислення описаних вище значень і , так як в розгляді відсутні раунди з 112 по 130, однак тоді було проведено : автори атаки помітили збіг 8 біт в і , перевіривши їх звичайною атакою методом зустрічі посередині на 127 раунді. У зв'язку з цим у даній фазі порівнювалися значення саме цих 8 біт в підшифрах і . Це збільшило кількість кандидатів у ключі, але не складність обчислень.
Друга фаза: перевірка ключів Для перевірки кандидатів в ключі алгоритму KTANTAN32 було потрібно в середньому ще дві пари відкритого-/закритого текстів для виділення ключа.
Результати
KTANTAN32: обчислювальна складність підбору ключа скоротилася до з використанням трьох пар відкритого-/закритого тексту. KTANTAN48: обчислювальна складність підбору ключа скоротилася до з використанням двох пар відкритого-/закритого тексту. KTANTAN64: обчислювальна складність підбору ключа скоротилася до з використанням двох пар відкритого-/закритого тексту.
Тим не менш, це не найкраща атака на сімейство шифрів KTANTAN. У 2011 році була здійснена атакаLei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang, and San Ling. "Improved Meet-in-the-Middle Cryptanalysis of KTANTAN" , яка скорочувала обчислювальну складність алгоритму до з використанням чотирьох пар відкритого-/закритого тексту.
Багатовимірний алгоритм Багатовимірний алгоритм методу зустрічі посередині застосовується при використанні великої кількості циклів шифрування різними ключами на блокових шифрах. Замість звичайної «зустріч посередині» в даному алгоритмі використовується поділ криптотексту кількома проміжними точками.
Припускається, що атакується текст, зашифрований деяку кількість разів блоковим шифром:
Алгоритм
Обчислюється:
зберігається разом з d .
зберігається разом з d .
Для кожного можливого проміжного стану обчислюється:
при кожному збігу з елементом з в зберігаються і ..
зберігається разом з в .
Для кожного можливого проміжного стану обчислюється:
при кожному совпадінні з елементом із перевіряється совпадіння з , після чого в зберігаються и .
зберігається разом з в .
Для кожного можливого проміжного стану обчислюється:
при кожному збігу з елементом із провіряється збіг з , після чого в зберігаються и . и при кожному збігу с , перевіряється збіг з
Далі знайдена послідовність кандидатів тестується на іншій парі відкритого-/закритого тексту для підтвердження істинності ключів. Слід зауважити рекурсивність в алгоритмі: підбір ключів для стану відбувається на основі результатів для стану . Це вносить елемент експоненційної складності в даний алгоритм.
Складність Часова складність даної атаки становить
Щодо використання пам'яті, легко помітити, що із збільшенням на кожен накладається все більше обмежень, що зменшує кількість записуваних в нього кандидатів. Це означає, що значно менше .
Верхня межа обсягу використаної пам'яті:
де - загальна довжина ключа.
Складність використання даних залежить від ймовірності "проходження" помилкового ключа. Ця ймовірність дорівнює , де — довжина першого проміжного стану, яка найчастіше дорівнює розміру блоку. Враховуючи кількість кандидатів в ключі після першої фази, складність дорівнює .
В результаті отримуємо , де — розмір блоку.
Кожен раз, коли послідовність кандидатів у ключі тестується на новій парі відкритого-/закритого тексту, кількість ключів, які успішно проходять перевірку, множиться на імовірність проходження ключа, яка дорівнює .
Частина атаки повним перебором (перевірка ключів на нових парах відкритого-/закритого текстів) має часову складність , в котрій, очевидно, наступні доданки дедалі швидше прагнуть до нуля.
У підсумку, складність даних за аналогічними судженнями обмежена приблизно парами відкритого-/закритого ключа.
Примітки
Література