Часто встречается заблуждение, что стойкость криптографии можно увеличить, если зашифровать сообщение одним ключем, а затем опять зашифровать другим алгоритмом с другим ключем. Хуже, если для двух ключей используется один и тот же алгоритм. Такие действия делают возможной атаку втречи посередине (meet-in-the-middle, не путать с человеком посередине), которая ускоряет подбор ключа в несколько раз.
Что делать, если очень нужно увеличить безопасность системы шифрования и как сделать это грамотно - об этом читайте в конце поста, но сначала разберемся в сути проблемы.
Стиль изложения выбран так, чтобы объяснить проблему с общечеловеческих позиций. Хотите больше формул? Тогда вам в Википедию:
en.wikipedia.org/wiki/Meet-in-the-middle_attack
Итак, у нас есть сообщение, зашифрованное двумя ключами подряд. Надо подобрать эти ключи. Берем первый шифрованный блок и начинаем расшифровывать всеми ключами подряд (т. е. обычный брутфорс). Получаем результаты с промежуточным шифром. Складываем в таблицу. Не обязательно хранить промежуточный блок целиком, достаточно нескольких бит.
Для чего мы их храним? Для того, чтобы сравнивать их с результатами второй ступени, о которой ниже:
Берем множество открытых текстов, шифруем их вторым алгоритмом всеми ключами подряд, получаем промежуточные результаты, сравниваем их с таблицoй. То есть с одной стороны мы расшифровываем подопытное сообщение всеми ключами подряд, а с другой стороны генерируем много пар клиртекст+ключ и зашифровываем все это. Сравнивать блоки целиком не нужно, достаточно сравнить те несколько бит. Если совпало, то можно быстренько сгенерировать эти блоки еще раз и проверить, вдруг совпадут. Если совпали, значит это и есть те два ключа, которые мы искали.
Главное, что можно распараллелить нагрузку и использовать микросхемы ПЛИС для быстрого перебора и сравнивания (если АСИК, то еще быстрее). Понятно?
Атака была впервые предложена в 1977 математиками Диффи и Хеллманом для алгоритма DES. Алгоритм DES не рекомендуется к применению из-за маленькой длины ключа. Эту проблему пытались решить, используя DES дважды. Так появился Double DES, для которого характерна атака meet-in-the-middle. Позже появился Triple DES, в котором средняя ступень как раз и служит для затруднения атаки встречи посередине. Triple DES теперь тоже считается устаревшим (атака Sweet32).
Может ли meet-in-the-middle снижать безопасность других симметричных шифров? Я думаю, что да.
Теперь решение. Метод предложен одним знаменитым криптографом (брюсом шнайером) в одной из своих книг (инфа на русском была где-то в верхнем интернете, сейчас не помню).
- Берем сообщение. Берем криптостойкий шум по объему равный сообщению.
- Ксорим.
- Результат шифруем первым ключем.
- Берем тот шум, который участвовал в ксоре, шифруем его вторым ключем.
- Отправляем и то, и другое получателю, пусть расшифровывает
Схема не идеальная конечно, но считается, что она увеличивает время перебора, что нам и надо.
Вам нравится такое решение? Кто что думает?
