Атаки класса «встреча посередине»
Как было сказано выше, алгоритм шифрования считается стойким, если атака методом «грубой силы» против него неэффективна, а более быстрых возможностей вскрыть алгоритм не существует.
Любые методы, способные вскрыть алгоритм шифрования быстрее, чем полный перебор ключей, эксплуатируют те или иные конструктивные недостатки алгоритма или его реализации. Начнем обзор таких методов с атак класса встреча посередине (meet-in-the-middle).
Простейший пример подобной атаки — вскрытие любого алгоритма шифрования, представляющего собой двойное шифрование данных с помощью какого-либо «одинарного» алгоритма. Рассмотрим вкратце алгоритм Double DES, представляющий собой двойное шифрование обычным алгоритмом DES.
Double DES решает основную проблему алгоритма DES (56-битный ключ шифрования слишком короток, как было показано выше)— 112-битный ключ Double DES невозможно вскрыть полным перебором. Однако вскрытие Double DES легко выполняется атакой на основе известных открытых текстов. Предположим, у криптоаналитика есть открытый текст и результат его зашифровывания. Он может выполнить следующую последовательность действий.
Выполняется зашифровывание DES на всем ключевом множестве с записью результатов в некоторую таблицу.
Производится расшифровывание также на всем ключевом множестве; результаты расшифровывания сравниваются со всеми записями в таблице, сформированной на шаге 1.
Если какой-либо результат, полученный на шаге 2, совпал с одним из результатов шага 1, то можно предположить, что нужный ключ найден, т. е. найдены соответствующие совпадающему результату.
Следует учесть, что таких совпадений может быть много — порядка 2. Для «уточнения» правильного ключа из этих примерно 248 вариантов достаточно наличия еще одной пары текстов. Криптоаналитик может использовать их абсолютно так же, как и первую пару, но перебор вариантов осуществляется уже только по совпадениям первого перебора. В результате будет найден единственно верный ключ (вероятность повторного совпадения ничтожно мала.
В результате воздействия данной атаки сложность вычисления ключа Double DES всего в 2 раза выше, чем полный перебор ключей обычного DES, что несравнимо меньше 2112 возможных вариантов «двойного» ключа. Алгоритм Double DES, собственно, и не используется, а упоминается лишь в иллюстрациях к атаке «встреча посередине».
Атака «встреча посередине» была изобретена в 1981 г. известными криптоло-гами Ральфом Мерклем (Ralph С. Merkle) и Мартином Хеллманом (Martin Е. Hellman) именно в применении к алгоритму Double DES. Кроме того, эта атака (но в заметно более сложном исполнении) применима и к одному из вариантов «тройного» DES (Triple DES).
Как видно, в отличие от Double DES, атака малоэффективна против более современных алгоритмов шифрования, что не удивительно. Однако, как и атака методом «грубой силы», атака «встреча посередине» нередко применима в комбинации с другими атаками, а также для оценки запаса криптостойкости модифицированных версий алгоритмов и алгоритмов с усеченным количеством раундов.
Алгоритмы шифрования
