Атака встреча посередине (Meet-in-the-Middle Attack)




При этом методе криптанализа алгоритм шифрования делится на верхнюю и нижнюю части. Затем криптоаналитик посредством частичных (отдельных) рассуждений на базе догадок пытается выполнить частичное шифрование от верха до середины и частичное расшифрование от низа до середины алгоритма. Результаты затем сравниваются и если они согласуются, то ключевой кандидат откладывается (запоминается) для дальнейшего анализа, в противном случае ключевая догадка неправильная. Наиболее примечательные приложения этого метода нашли при анализе каскадных шифров [85, 92, 93]. Далее представляются большие детали.

Атака «встреча посредине» (MITM) требует известного открытого текста и может служить примером метода компромисса между временем и памятью. Рассмотрим операцию двойного DES шифрования с парой (P1,C1) известного плайнтекст/шифртекста: которая использует 112-битный ключ (K1, K2) с независимыми и равномерно распределенными K1 и K2. Это отношение может быть также представлено с помощью операции расшифрования как

Атака сначала создает список из результатов зашифрований известного открытого текста P1 для всех 256 возможных кандидатов ключей K’1 для и сохраняет пару в сортированной таблице, проиндексированной с помощью U. Для всех 256 возможных значений K‘2 ключа K2 вычисляется и выполняется тестирование V для проверки его присутствия в таблице как индекса. Если V не присутствует в таблице, то Таким же образом продолжается испытание остальных кандидатов для K2. Если V является индексом для некоторого (U, K’1), а именно, U = V , то (K’1, K2) является кандидатом для (K1,K2). Для первой пары (P1, C1) ожидаемое число ложных сигналов (решений) равно 256/(264/256) = 248, так как существует вероятность 2-64 совпадения 64-битовых псевдослучайных строк U и V, и 256 значений для K’1 и 256 значений для K2. Вторая пара плайнтекст/ шифртекста уменьшает интенсивность ложных сигналов до 248× 2-64 = 2-16, потому что нужно тестировать только предыдущие 248 кандидатов. Временная сложность атаки равна около 256 + 248 DES шифрований для K1 и 256 + 248 DES расшифрований для K2. Сложность памяти равна 256 пар (текст, ключ) для сортированной таблицы и двух известных пар (P;C). Эти вычисления допускают использование одного процессора.

Так как при выполнении каждого зашифрования используются различные ключи, то MITM атака может быть распараллелена с помощью нескольких процессоров. Ван Оршот и Вайнер в [220] описали MITM атаку на базе метода параллельного поиска коллизий и компромисса между временем и памятью (для экономии памяти). Главным преимуществом ее является более короткая (низкая) временная сложность. Их атака требует двух известных пар плайнтекст/шифртекстов. Оцениваемая стоимость аппаратной реализации атаки составляет 10,000,000$ США.

Теперь, пусть будет тройным DES в EDE режиме[1]) с тремя независимыми ключами или 168 ключевыми битами. Атака «встреча посредине» может быть осуществлена аналогично атаке на двойной DES. Допустим, что атака осуществляет поиск коллизий между и Для первой пары (открытый текст, шифртекст), (P1,C1), каждый из 2112 кандидатов пар ключей (K’1, K2) предлагает в среднем 248 раз каждый из 264 64-битовых текстовых блоков. И значит, существует 256 совпадений между и или кортежей (K’1, K2, K’3). Для второй пары (P2 ,C2) каждый из 2104 кандидатов (K’1, K2, K’3) имеет вероятность 2-64 совпадений с и это приводит к генерированию кандидатов ключа. Для третьей пары (P3 ,C3) каждый из 240 кандидатов (K’1, K’2, K’3) имеет вероятность 2-64 совпадения с и ожидаемое число ложных сигналов равно 240 2-64 = = 2-24. Сложность памяти составляет 256 пар (текст, ключ); требуемыми данными являются три различные пары (P,C), а временная сложность равна 2112 + 248 + 240 шифрований в двойном DES плюс 256 + 256 + 240 расшифрований в одинарном DES.

Ван Оршон и Вайнер в [220] представили распараллеленную версию атаки MITM на трехключевой тройной DES, использующую параллельный метод поиска коллизии и компромисс между временем и памятью.

2.1.7. Метод "Разделяй и побеждай"

Этот метод криптоанализа основан на том, что множество ключей K допускает представление . Это значит, что каждый ключ может быть представлен в виде вектора , где , .

Считается также выполненным обязательное условие в виде существования некоторого критерия h, позволяющего при известных открытом и закрытом текстах проверять правильность первого подключа в .

Метод "Разделяй и побеждай" предлагает сначала опробовать элементы множества , отбраковывая варианты по критерию h. Отсюда определяется - первая компонента вектора . Затем, используя найденное значение и известный шифртекст, опробуются варианты . Трудоемкость определения компоненты равна в среднем операций опробования, соответственно трудоемкость определения равна в среднем операций опробования. Тогда трудоемкость метода есть + против при методе полного перебора [4].

Основная проблема при применении метода "Разделяй и побеждай" состоит в нахождении критерия h, который зависит от конкретного преобразования , где , , или вообще может не существовать. Иногда критерий h может описываться вероятностно-статистической моделью.






Дата добавления: 2016-09-26; просмотров: 2972; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2022 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.021 сек.