Открыть главное меню

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

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

СложностьПравить

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

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

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

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

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

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

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

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

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

ПримечанияПравить

  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.
  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; Guang Gong. MD-MITM Attack and Its Applications to GOST, KTANTAN and Hummingbird-2 (англ.) // eCrypt : journal. — 2011.

ЛитератураПравить

  1. Moore, Stephane. Meet-in-the-Middle Attacks (неопр.). — 2010. — 16 November. — С. 2.