Атака «встреча посередине» из 3 подмножеств
Атака «встреча посередине» с тремя подмножествами (далее сокращенно MITM ) — это вариант общей атаки « встреча посередине» , которая используется в криптологии для криптоанализа хэшей и блочных шифров . Вариант с 3 подмножествами открывает возможность применения MITM-атак на шифры, где непросто разделить ключевые биты на два независимых пространства ключей, как того требует атака MITM.
Вариант с 3 подмножествами ослабляет ограничение на независимость пространств ключей, перемещая пересекающиеся части пространств ключей в подмножество, которое содержит биты ключей, общие для двух пространств ключей.
Первоначальная атака MITM была впервые предложена в статье Диффи и Хеллмана в 1977 году, где они обсуждали криптоаналитические свойства DES. [1] Они утверждали, что размер ключа DES слишком мал, и что многократное повторное применение DES с разными ключами может решить проблему размера ключа; однако они рекомендовали не использовать двойной DES и предложили как минимум тройной DES из-за MITM-атак (Double-DES очень восприимчив к MITM-атаке, поскольку DES можно легко разделить на два подшифра (первое и второе шифрование DES). ) с ключами, независимыми друг от друга, что позволяет провести базовую атаку MITM, которая снижает вычислительную сложность с до .
Появилось множество вариаций, поскольку Диффи и Хеллман предложили MITM-атаки. Эти варианты либо делают MITM-атаки более эффективными, либо позволяют использовать их в ситуациях, когда базовый вариант не может. Вариант с 3 подмножествами был показан Богдановым и Рехбергером в 2011 году [2] и показал его использование в криптоанализе шифров, таких как семейство легковесных блочных шифров KTANTAN.
Как и в случае обычных атак MITM, атака делится на две фазы: фаза сокращения ключа и фаза проверки ключа. На первом этапе домен ключевых кандидатов сокращается путем применения атаки MITM. На втором этапе найденные ключевые кандидаты проверяются на другой паре открытый/зашифрованный текст, чтобы отфильтровать неправильный ключ(и).
На этапе сокращения ключа атакуемый шифр разбивается на два подшифра и , каждый из которых имеет свои независимые ключевые биты, как это обычно бывает при атаках MITM. Вместо того, чтобы соответствовать ограничению, состоящему в том, что ключевые биты двух субшифров должны быть независимыми, атака с 3 подмножествами позволяет разделить шифр на два субшифра, где некоторые биты разрешено использовать в обоих субшифрах.
