В криптоанализе методом встречи посередине или атакой «встречи посередине» () называется класс атак на криптографические алгоритмы, асимптотически уменьшающих время полного перебора за счет принципа «разделяй и властвуй», а также увеличения объема требуемой памяти. Впервые данный метод был предложен Уитфилдом Диффи и Мартином Хеллманом в 1977 году.
Начальные условия Даны открытый (незашифрованный) и шифрованный тексты. Криптосистема состоит из циклов шифрования. Цикловые ключи независимы и не имеют общих битов. Ключ системы представляет собой сочетание из -цикловых ключей . Задача состоит в нахождении ключа .
Решение простого случая Простым примером является двойное последовательное шифрование блочным алгоритмом двумя различными ключами и . Процесс шифрования выглядит так:
,
где — это открытый текст, — шифротекст, а — операция однократного шифрования ключом . Соответственно, обратная операция — расшифрование — выглядит так:
На первый взгляд кажется, что применение двойного шифрования многократно увеличивает стойкость всей схемы, поскольку перебирать теперь нужно два ключа, а не один. В случае алгоритма DES стойкость увеличивается с до . Однако это не так. Атакующий может составить две таблицы: Все значения для всех возможных значений , Все значения для всех возможных значений .
Затем ему достаточно лишь найти совпадения в этих таблицах, то есть такие значения и , что . Каждое совпадение соответствует набору ключей , который удовлетворяет условию.
Для данной атаки потребовалось операций шифрования-расшифрования (лишь в два раза больше, чем для перебора одного ключа) и памяти. Дополнительные оптимизации — использование хеш-таблиц, вычисления только для половины ключей (для DES полный перебор, на самом деле, требует лишь операций) — могут снизить эти требования. Главный результат атаки состоит в том, что последовательное шифрование двумя ключами увеличивает время перебора лишь в два раза.
Решение в общем виде Обозначим преобразование алгоритма как , где -открытый текст, а -шифротекст. Его можно представить как композицию , где — цикловое преобразование на ключе . Каждый ключ представляет собой двоичный вектор длины , а общий ключ системы — вектор длины .
Заполнение памяти Перебираются все значения , т.е первые цикловых ключей. На каждом таком ключе зашифровываем открытый текст — (то есть проходим циклов шифрования вместо ). Будем считать неким адресом памяти и по этому адресу запишем значение . Необходимо перебрать все значения .
Определение ключа Перебираются все возможные . На получаемых ключах расшифровывается шифротекст — . Если по адресу не пусто, то достаем оттуда ключ и получаем кандидат в ключи .
Однако нужно заметить, что первый же полученный кандидат не обязательно является истинным ключом. Да, для данных и выполняется , но на других значениях открытого текста шифротекста , полученного из на истинном ключе, равенство может нарушаться. Все зависит от конкретных характеристик криптосистемы. Но иногда бывает достаточно получить такой «псевдоэквивалентный» ключ. В противном же случае после завершения процедур будет получено некое множество ключей , среди которых находится истинный ключ.
Если рассматривать конкретное применение, то шифротекст и открытый текст могут быть большого объема (например, графические файлы) и представлять собой достаточно большое число блоков для блочного шифра. В данном случае для ускорения процесса можно зашифровывать и расшифровывать не весь текст, а только его первый блок (что намного быстрее) и затем, получив множество кандидатов, искать в нем истинный ключ, проверяя его на остальных блоках.
Атака с разбиением ключевой последовательности на 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» , сокращающая вычислительную сложность алгоритма до с использованием четырех пар открытого-закрытого текста.
Атака по полному двудольному графу Атака по полному двудольному графу применяется для увеличения количества попыток атаки посредника с помощью построения полного двудольного графа. Предложена Диффи и Хеллманом в 1977 году.
Многомерный алгоритм Многомерный алгоритм метода встречи посередине применяется при использовании большого количества циклов шифрования разными ключами на блочных шифрах. Вместо обычной «встречи посередине» в данном алгоритме используется разделение криптотекста несколькими промежуточными точками.
Предполагается, что атакуемый текст зашифрован некоторое количество раз блочным шифром:
Алгоритм Вычисляется:
сохраняется вместе с d .
сохраняется вместе с d .
Для каждого возможного промежуточного состояния вычисляется:
при каждом совпадении с элементом из в сохраняются и .
сохраняется вместе с в .
Для каждого возможного промежуточного состояния вычисляется:
при каждом совпадении с элементом из проверяется совпадение с , после чего в сохраняются и .
сохраняется вместе с в . Для каждого возможного промежуточного состояния вычисляется: и при каждом совпадении с элементом из проверяется совпадение с , после чего в сохраняются и . и при каждом совпадении с , проверяется совпадение с
Далее найденная последовательность кандидатов тестируется на иной паре открытого-закрытого текста для подтверждения истинности ключей. Следует заметить рекурсивность в алгоритме: подбор ключей для состояния происходит на основе результатов для состояния . Это вносит элемент экспоненциальной сложности в данный алгоритм.
Сложность
Временная сложность данной атаки составляет
Говоря об использовании памяти, легко заметить что с увеличением на каждый накладывается все больше ограничений, что уменьшает количество записываемых в него кандидатов. Это означает, что значительно меньше .
Верхняя граница объема используемой памяти:
где — общая длина ключа.
Сложность использования данных зависит от вероятности «прохождения» ложного ключа. Эта вероятность равна , где — длина первого промежуточного состояния, которая чаще всего равна размеру блока. Учитывая количество кандидатов в ключи после первой фазы, сложность равна .
В итоге получаем , где — размер блока.
Каждый раз, когда последовательность кандидатов в ключи тестируется на новой паре открытого-закрытого текста, количество успешно проходящих проверку ключей умножается на вероятность прохождения ключа, которая равна .
Часть атаки полным перебором (проверка ключей но новых парах открытого-закрытого текстов) имеет временную сложность , в которой, очевидно, последующие слагаемые все быстрее стремятся к нулю.
В итоге, сложность данных по аналогичным суждениям ограничена приблизительно парами открытого-закрытого ключа.
Примечания
Литература
Категория:Криптографические атаки Категория:Криптография