Атака «Встреча посерединее»

В криптоанализе методом встречи посередине или атакой "встречи посередине" (англ. meet-in-the-middle attack) называется класс атак на криптографические алгоритмы, асимптотически уменьшающих время полного перебора за счет принципа "разделяй и властвуй", а также увеличения объема требуемой памяти. Впервые данный метод был предложен Уитфилдом Диффи и Мартином Хеллманом в 1977 году. Атака "встреча посередине" была изобретена в 1981 г. известными криптологами Ральфом Мерклем (Ralph C. Merkle) и Мартином Хеллманом (Martin E. Hellman) именно в применении к алгоритму Double DES. Кроме того, эта атака (но в заметно более сложном исполнении) применима и к одному из вариантов "тройного" DES (Triple DES).

Впоследствии атаки данного класса были неоднократно использованы для анализа различных алгоритмов шифрования. Наиболее показательные примеры относятся к следующим алгоритмам шифрования:

1. Атака "встреча посередине" позволяет вычислить 192-битный ключ алгоритма DEAL выполнением порядка 2¹⁶⁶ тестовых операций шифрования; для вычисления 256-битного ключа необходимо порядка 2²²² операций. И то, и другое не является практически осуществимым, но доказывает невысокий запас криптостойкости алгоритма DEAL.

2. Аналогично непрактичная атака возможна против еще одного участника конкурса AES - SAFER +. Для его вскрытия необходимо 2²⁴⁰ операций шифрования (при 256-битном ключе).

Как видно, в отличие от Double DES, атака малоэффективна против более современных алгоритмов шифрования, что не удивительно. Однако, как и атака методом грубой силы, атака "встреча посередине" нередко применима в контексте других атак, а также для оценки запаса криптостойкости против модифицированных версий алгоритмов и алгоритмов с усеченным числом раундов.

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

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

Простейший пример атак класса встреча посередине (meet-in-the-middle) - вскрытие любого алгоритма шифрования, представляющего собой двойное шифрование данных с помощью какого-либо "одинарного" алгоритма. Рассмотрим алгоритм Double DES, представляющий собой двойное шифрование обычным DES'ом (см. рис.5):

Рис. 1 Алгоритм Double DES.

C = DES_k2/2 (DES_k1/2 (M)),

где k_1/2 и k_2/2 - половины двойного ключа алгоритма Double DES, каждая из которых представляет собой обычный 56-битный ключ DES.

Double DES решает основную проблему алгоритма DES (56-битный ключ шифрования слишком короток - как было показано выше) - 112-битный ключ Double DES невозможно вскрыть полным перебором. Однако, вскрытие Double DES легко выполняется атакой на основе известных открытых текстов. Предположим, у криптоаналитика есть открытый текст M1 и результат его зашифрования - С1. Он может выполнить следующую последовательность действий (см. рис.2):

Рис.2 Пример атаки "встреча посередине".

1. Выполняется зашифрование DES_kx (M1) на всем ключевом множестве (kx = 0…2⁵⁶-1) с записью результатов в некоторую таблицу.

2. Производится расшифрование DES^-1_ky (C1) также на всем ключевом множестве; результаты расшифрования сравниваются со всеми записями в таблице, сформированной на шаге 1.

3. Если какой-либо результат, полученный на шаге 2, совпал с одним из результатов шага 1, то можно предположить, что нужный ключ найден, т.е. соответствует совпадающему результату kx = k_1/2, а ky = k_2/2.

Следует учесть, что таких совпадений может быть много - порядка 2⁴⁸. Для "уточнения" правильного ключа из этих примерно 2⁴⁸ вариантов достаточно наличия еще одной пары текстов: M2 и C2. Криптоаналитик может использовать их абсолютно так же, как и первую пару (M1, C1), но перебор вариантов kx и ky осуществляется уже только по совпадениям первого перебора. В результате будет найден единственно верный ключ (вероятность повторного совпадения ничтожно мала - около 2^-16, в этом случае используется третья пара - M3 и C3 - при ее наличии).

В результате воздействия данной атаки сложность вычисления ключа Double DES всего в 2 раза выше, чем полный перебор ключей обычного DES, что несравнимо меньше 2¹¹² возможных вариантов "двойного" ключа. Алгоритм Double DES, собственно, и не используется, а упоминается лишь в подобных иллюстрациях к атаке "встреча посередине".

№2