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

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

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

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

Простым примером является двойное последовательное шифрование блочным алгоритмом двумя различными ключами ${\displaystyle K_{1}}$ и ${\displaystyle K_{2}}$. Процесс шифрования выглядит так:

${\displaystyle s=ENC_{K_{2}}(ENC_{K_{1}}(p))}$,

где ${\displaystyle p}$ — это открытый текст, ${\displaystyle s}$ — шифртекст, а ${\displaystyle ENC_{K_{i}}()}$ — операция однократного шифрования ключом ${\displaystyle K_{i}}$. Соответственно, обратная операция — расшифрование — выглядит так:

${\displaystyle p=ENC_{K_{1}}^{-1}(ENC_{K_{2}}^{-1}(s))}$

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

1. Все значения ${\displaystyle m_{1}=ENC_{K_{1}}(p)}$ для всех возможных значений ${\displaystyle K_{1}}$,
2. Все значения ${\displaystyle m_{2}=ENC_{K_{2}}^{-1}(s)}$ для всех возможных значений ${\displaystyle K_{2}}$.

Затем ему достаточно лишь найти совпадения в этих таблицах, т.е. такие значения ${\displaystyle m_{1}}$ и ${\displaystyle m_{2}}$, что ${\displaystyle ENC_{K_{1}}(p)=ENC_{K_{2}}^{-1}(s)}$. Каждое совпадение соответствует набору ключей ${\displaystyle (K_{1},K_{2})}$, который удовлетворяет условию.

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

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

Обозначим преобразование алгоритма как Ek(a)=b, где a-открытый текст, а b-шифротекст. Его можно представить как композицию Ek1Ek2..Ekh(a)=b, где Eki — цикловое преобразование на ключе ki. Каждый ключ ki представляет собой двоичный вектор длины n, а общий ключ системы — вектор длины n*h.

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

Перебираются все значения k'=(k1,k2..kr), т.е первые r цикловых ключей. На каждом таком ключе k' зашифровываем открытый текст a - Ek' (a)=Ek1Ek2..Ekr(a)=S (т.е. проходим r циклов шифрования вместо h). Будем считать S неким адресом памяти и по этому адресу запишем значение k'. Необходимо перебрать все значения k'.

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

Перебираются все возможные k"=(kr+1,kr+2...kh). На получаемых ключах расшифровывается шифротекст b - E-1k"(b)=E-1kh..E-1kr+1(b)=S' . Если по адресу S' не пусто, то достаем оттуда ключ k' и получаем кандидат в ключи (k',k")=k.

Однако нужно заметить, что первый же полученный кандидат k не обязательно является истинным ключом. Да, для данных a и b выполняется Ek(a)=b, но на других значениях открытого текста a' шифротекста b', полученного из a' на истинном ключе, равенство может нарушаться. Все зависит от конкретных характеристик криптосистемы. Но иногда бывает достаточно получить такой "псевдоэквивалентный" ключ. В противном же случае после завершения процедур будет получено некое множество ключей {k',k"...}, среди которых находится истинный ключ.

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

Примечания