Метод встречи посередине (Bymk; fvmjycn hkvyjy;nuy)

Перейти к навигации Перейти к поиску

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

Начальные условия

[править | править код]

Даны открытый (незашифрованный) и шифрованный тексты. Криптосистема состоит из циклов шифрования. Цикловые ключи независимы и не имеют общих битов. Ключ системы представляет собой сочетание из -цикловых ключей . Задача состоит в нахождении ключа .

Решение простого случая

[править | править код]

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

,

где  — это открытый текст,  — шифротекст, а  — операция однократного шифрования ключом . Соответственно, обратная операция — расшифрование — выглядит так:

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

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

Затем ему достаточно лишь найти совпадения в этих таблицах, то есть такие значения и , что . Каждое совпадение соответствует набору ключей , который удовлетворяет условию.

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

Решение в общем виде

[править | править код]

Обозначим преобразование алгоритма как , где -открытый текст, а -шифротекст. Его можно представить как композицию , где  — цикловое преобразование на ключе . Каждый ключ представляет собой двоичный вектор длины , а общий ключ системы — вектор длины .

Заполнение памяти

[править | править код]

Перебираются все значения , т.е первые цикловых ключей. На каждом таком ключе зашифровываем открытый текст  — (то есть проходим циклов шифрования вместо ). Будем считать неким адресом памяти и по этому адресу запишем значение . Необходимо перебрать все значения .

Определение ключа

[править | править код]

Перебираются все возможные . На получаемых ключах расшифровывается шифротекст  — . Если по адресу не пусто, то достаем оттуда ключ и получаем кандидат в ключи .

Однако нужно заметить, что первый же полученный кандидат не обязательно является истинным ключом. Да, для данных и выполняется , но на других значениях открытого текста шифротекста , полученного из на истинном ключе, равенство может нарушаться. Все зависит от конкретных характеристик криптосистемы. Но иногда бывает достаточно получить такой «псевдоэквивалентный» ключ. В противном же случае после завершения процедур будет получено некое множество ключей , среди которых находится истинный ключ.

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

Атака с разбиением ключевой последовательности на 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], сокращающая вычислительную сложность алгоритма до с использованием четырех пар открытого-закрытого текста.

Атака по полному двудольному графу

[править | править код]

Атака по полному двудольному графу применяется для увеличения количества попыток атаки посредника с помощью построения полного двудольного графа. Предложена Диффи и Хеллманом в 1977 году.

Многомерный алгоритм

[править | править код]

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

Предполагается, что атакуемый текст зашифрован некоторое количество раз блочным шифром:

  • Вычисляется:
 
сохраняется вместе с d .
 
сохраняется вместе с d .
  • Для каждого возможного промежуточного состояния вычисляется:
 
при каждом совпадении с элементом из в сохраняются и .
 
сохраняется вместе с в .
  • Для каждого возможного промежуточного состояния вычисляется:
 
при каждом совпадении с элементом из проверяется совпадение с , после чего в сохраняются и .
 
сохраняется вместе с в .
  • Для каждого возможного промежуточного состояния вычисляется:
  и при каждом совпадении с элементом из проверяется совпадение с , после чего в сохраняются и .
  и при каждом совпадении с , проверяется совпадение с

Далее найденная последовательность кандидатов тестируется на иной паре открытого-закрытого текста для подтверждения истинности ключей. Следует заметить рекурсивность в алгоритме: подбор ключей для состояния происходит на основе результатов для состояния . Это вносит элемент экспоненциальной сложности в данный алгоритм[5].

Временная сложность данной атаки составляет

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

Верхняя граница объема используемой памяти:

где  — общая длина ключа.

Сложность использования данных зависит от вероятности «прохождения» ложного ключа. Эта вероятность равна , где  — длина первого промежуточного состояния, которая чаще всего равна размеру блока. Учитывая количество кандидатов в ключи после первой фазы, сложность равна .

В итоге получаем , где  — размер блока.

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

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

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

Примечания

[править | править код]
  1. 1 2 Diffie, Whitfield; Hellman, Martin E. Exhaustive Cryptanalysis of the NBS Data Encryption Standard (англ.) // Computer : journal. — 1977. — June (vol. 10, no. 6). — P. 74—84. — doi:10.1109/C-M.1977.217750. Архивировано 14 мая 2009 года.
  2. 1 2 Andrey Bogdanov and Christian Rechberger. «A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN» Архивная копия от 7 ноября 2018 на Wayback Machine
  3. Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. «KATAN & KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers» Архивная копия от 20 апреля 2018 на Wayback Machine
  4. Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang, and San Ling. «Improved Meet-in-the-Middle Cryptanalysis of KTANTAN» Архивная копия от 7 ноября 2018 на Wayback Machine
  5. 1 2 3 Zhu, Bo; Guang Gong. MD-MITM Attack and Its Applications to GOST, KTANTAN and Hummingbird-2 (англ.) // eCrypt : journal. — 2011. Архивировано 29 июля 2018 года.

Литература

[править | править код]