Атака «встреча посередине» и компромиссы времени и памяти

Атаки MITM разделяют шифр на две половины и атакуют их независимо. Атакующий строит таблицу с одного конца, затем ищет с другого конца совпадение. Сложность атаки снижается с O(2^{2n}) до O(2^n) ценой использования O(2^n) памяти.

Двойной DES применяет DES дважды: C = DES_{K2}(DES_{K1}(P)). Пространство ключей: 2^{112}. Атака MITM: для всех 2^{56} значений K1 вычислите DES_{K1}(P) и сохраните результат. Для всех 2^{56} значений K2 вычислите DES_{K2}^{-1}(C) и выполните поиск в таблице. Совпадение → кандидат (K1, K2). Всего требуется только 2^{57} операций.

Шаг 1: зашифруйте открытый текст P со всеми возможными K1 → таблица T[DES_{K1}(P)] = K1. Шаг 2: для каждого K2 расшифруйте шифротекст C: v = DES^{-1}_{K2}(C). Проверьте, принадлежит ли v множеству T. Если существует T[v] = K1, проверьте пару (K1, K2) на второй паре «открытый текст—шифротекст». Ожидается 1–2 ложных совпадения; отбросьте их.

Тройной DES (3DES) использует три ключа K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM по-прежнему применима, но менее эффективно: двухключевой 3DES (K3=K1) сводится к 2^{112} операциям. Для трёхключевого 3DES существует атака MITM с 2^{112} операциями, поэтому 3DES обеспечивает лишь около 112 бит эффективной безопасности, несмотря на 168-битный ключ.

Hellman (1980): заранее вычислите таблицу цепочек (start_point, end_point), чтобы ускорить автономный поиск ключа. Получив целевой хеш или шифротекст, найдите в таблице Хеллмана цепочку, содержащую его. Компромисс: P = N (время × память = постоянная величина пространства). Это основа радужных таблиц.

Радужные таблицы (Oechslin, 2003) улучшают таблицы Хеллмана, используя разные функции сокращения на каждой позиции цепочки и устраняя ложные срабатывания (объединённые цепочки). Они эффективны для взлома несолёных хешей паролей. Поиск занимает O(table_size/chain_length) времени.

Соль — это случайное значение, добавляемое перед паролем до хеширования: H(salt||password). Разные соли дают разные хеши для одного и того же пароля — радужная таблица для "password" бесполезна, если использовалась другая соль. Соли необходимо хранить вместе с хешем.

Атаки MITM на AES-128 (10 раундов): известные атаки разделяют шифрование на раунде 5 — выполняют 5 раундов шифрования вперёд и 5 раундов расшифрования назад, встречаясь посередине. Лучшая известная атака — атака на основе биклик снижает сложность с 2^{128} до 2^{126.1}; это непрактично, но показывает, что у AES нет запаса безопасности против подходов типа MITM.

Для хешей Меркла—Дамгарда MITM в некоторых конструкциях может находить прообразы быстрее полного перебора. Атака: постройте таблицу из блоков сообщения, начиная с IV; выполняйте поиск в обратном направлении от целевого хеша. Против SHA-256 с полным числом раундов сложность всё ещё составляет около 2^{255}, то есть улучшения по сравнению с полным перебором нет.

Атака рассечения обобщает MITM на разбиение на r частей. При разбиении шифра на 3 части зашифруйте вперёд 1/3 раундов, встретьтесь посередине цепочки, затем расшифруйте назад 1/3 раундов. Требуются O(2^{n*2/3}) времени и O(2^{n/3}) памяти — это более сбалансированный компромисс.

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

Какова эффективная безопасность двойного DES (2x DES, объединённый ключ длиной 112 бит) против атаки MITM?

Атаки MITM разделяют шифры на половины, снижая время с 2^{2n} до 2^n при использовании 2^n памяти. Они взламывают двойной DES; 3DES смягчает эту проблему, но имеет 112 бит эффективной безопасности. Радужные таблицы используют логику MITM для взлома паролей — защита достигается добавлением соли. Далее: атаки по времени и атаки по побочным каналам.