Метод встречи посередине

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В криптоанализе методом встречи посередине или атакой "встречи посередине" (англ. 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. Сравнить и . В случае совпадения получаем кандидата в ключи.

Фаза проверки ключей[править | править код]

Для проверки ключей полученные кандидаты проверяют на нескольких парах известных открытых-/закрытых текстов. Обычно для проверки требуется не очень большое количество таких пар текстов. [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. 1 2 (June 1977) «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer 10 (6): 74–84. DOI:10.1109/C-M.1977.217750.
  2. 1 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. 1 2 3 Zhu, Bo (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.