Атака «встреча посередине» из 3 подмножеств

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

Вариант с тремя подмножествами ослабляет ограничение на независимость пространств ключей за счет перемещения пересекающихся частей пространств ключей в подмножество, которое содержит биты ключей, общие для двух пространств ключей.

История

Оригинальная атака MITM была впервые предложена в статье Диффи и Хеллмана в 1977 году, где они обсуждали криптоаналитические свойства DES. Они утверждали, что размер ключа DES слишком мал и что многократное применение DES с разными ключами может решить проблему размера ключа; однако они посоветовали не использовать двойной DES и предложили тройной DES как минимум из-за атак MITM (Double-DES очень восприимчив к атаке MITM, поскольку DES можно легко разделить на два субшифра (первый и второй шифрование DES). ) с ключами, независимыми друг от друга, что позволяет провести базовую MITM-атаку, которая снижает сложность вычислений с $2^{112}(=2^{2\times 56})$ к $2^{57}(=2\times 2^{56})$.

Появилось множество вариаций с тех пор, как Диффи и Хеллман предложили атаки MITM. Эти варианты либо делают MITM-атаки более эффективными, либо позволяют использовать их в ситуациях, в которых базовый вариант невозможен. Вариант с тремя подмножествами был показан Богдановым и Рехбергером в 2011 году. и показал его использование в криптоанализе шифров, таких как облегченное семейство блочных шифров KTANTAN.

Процедура

Как и в случае обычных атак MITM, атака разделена на две фазы: фазу уменьшения ключа и фазу проверки ключа. На первом этапе домен ключевых кандидатов сокращается за счет применения атаки MITM. На втором этапе найденные ключи-кандидаты проверяются на другой паре простой/зашифрованный текст, чтобы отфильтровать неправильные ключи.

Фаза сокращения ключей

На этапе уменьшения ключа атакуемый шифр разбивается на два субшифра: $f$ и $g$, с каждым из них независимыми битами ключей, как это обычно бывает при атаках MITM. Вместо того, чтобы соответствовать ограничению, заключающемуся в том, что ключевые биты двух субшифров должны быть независимыми, атака с использованием трех подмножеств позволяет разделить шифр на два субшифра, при этом некоторые биты могут использоваться в обоих субшифрах.

Вместо этого это делается путем разделения ключа на три подмножества, а именно:

• $A_{0}$ = ключевые биты, которые являются общими для двух субшифров.
• $A_{1}$ = ключевые биты, отличные от первого субшифра, $f.$
• $A_{2}$ = биты ключей, отличные от второго субшифра, $g$

Теперь, чтобы провести MITM-атаку, три подмножества подвергаются брутфорсу по отдельности в соответствии с процедурой, приведенной ниже:

1. За каждое предположение $A_{0}$:
   1. Рассчитать промежуточное значение $i$ из открытого текста для всех комбинаций битов ключа в $A_{1}$
   2. Рассчитать промежуточное значение $j$, для всех комбинаций ключей и битов в $A_{2}$
   3. Сравнивать $i$ и $j$. Когда будет матч. Храните это ключ-кандидат.

ключевого

Каждый ключ-кандидат, обнаруженный на этапе сокращения ключа, теперь проверяется с другой парой открытого/зашифрованного текста. Это делается просто путем проверки того, дает ли шифрование открытого текста P известный зашифрованный текст C. Обычно здесь требуется только несколько других пар, что делает MITM-атаку с тремя подмножествами очень малой сложностью данных.

Пример

Следующий пример основан на атаке Рехбергера и Богданова на семейство шифров KTANTAN. В этом примере также используются соглашения об именах, использованные в их статье. Атака снижает вычислительную сложность KTANTAN32 до $2^{75.170}$, вниз от $2^{80}$ по сравнению с атакой грубой силы. Вычислительная сложность $2^{75.170}$ 2014 года, по-прежнему невозможно взломать, и поэтому атака на данный момент вычислительно невозможна. То же самое касается КТАНТАН48 и КТАНТАН64, сложности которых можно увидеть в конце примера.

Атака возможна из-за слабостей, используемых в побитовом расписании ключей KTANTAN. Он применим как к KTANTAN32, KTANTAN48, так и к KTANTAN64, поскольку все варианты используют одно и то же расписание ключей. Он неприменим к родственному семейству блочных шифров KANTAN из-за различий в расписании ключей между KTANTAN и KANTAN.

Обзор КТАНТАНА

KTANTAN — это легкий блочный шифр, предназначенный для ограниченных платформ, таких как RFID -метки, где криптографический примитив, такой как AES , был бы либо невозможен (с учетом аппаратного обеспечения), либо слишком дорог в реализации. Его изобрели Каньер, Дункельман и Кнежевич в 2009 году. Он принимает блок размером 32, 48 или 64 бита и шифрует его с использованием 80-битного ключа в течение 254 раундов. В каждом раунде в качестве ключа раунда используются два бита ключа (выбранные согласно расписанию ключей ).

Атака

Подготовка

При подготовке к атаке были выявлены слабые места в ключевом расписании KTANTAN, позволяющем провести атаку MITM с тремя подмножествами. Поскольку в каждом раунде используются только два бита ключа, распространение ключа за раунд невелико - безопасность зависит от количества раундов. Благодаря такой структуре расписания ключей можно было найти большое количество последовательных раундов, в которых никогда не использовались определенные биты ключей.

Точнее, авторы атаки установили, что:

• В раундах с 1 по 111 биты ключа никогда не используются: $k_{32},k_{39},k_{44},k_{61},k_{66},k_{75}$
• В раундах с 131 по 254 биты ключа никогда не используются: $k_{3},k_{20},k_{41},k_{47},k_{63},k_{74}$

Эта характеристика расписания ключей используется для организации атаки MITM с тремя подмножествами, поскольку теперь мы можем разделить шифр на два блока с независимыми ключевыми битами. Параметры атаки таковы:

• $A_{0}$ = биты ключей, используемые обоими блоками (что означает остальные 68 бит, не упомянутые выше)
• $A_{1}$ = биты ключей, используемые только первым блоком (определяется раундами 1-111)
• $A_{2}$ = биты ключей, используемые только вторым блоком (определено раундами 131-254)

Фаза сокращения ключей

Можно заметить проблему на этапе 1.3 на этапе сокращения ключей. Невозможно напрямую сравнить значения $i$ и $j$, как $i$ рассчитывается в конце 111 раунда, и $j$ рассчитывается в начале раунда 131. Это смягчается другим методом MITM, называемым частичным сопоставлением . Авторы нашли путем расчета вперед от промежуточного значения $i$и обратно от промежуточного значения $j$ что в раунде 127 8 бит все еще не изменились в обоих случаях. $i$ и $j$ с вероятностью единица. Таким образом, они сравнивали только часть состояния, сравнивая эти 8 бит (это было 8 бит в раунде 127 для KTANTAN32. Это было 10 бит в раунде 123 и 47 бит в раунде 131 для KTANTAN48 и KTANTAN64 соответственно). Это приводит к большему количеству ложных срабатываний, но не увеличивает заметно сложность атаки.

ключевого

KTANTAN32 теперь требует в среднем 2 пары для поиска ключа-кандидата из-за ложных срабатываний из-за совпадения только части состояния промежуточных значений. KTANTAN48 и KTANTAN64 в среднем по-прежнему требуют только одной пары открытого/зашифрованного текста для проверки и поиска правильных ключей-кандидатов.

Результаты

Для:

• КТАНТАН32, вычислительная сложность описанной выше атаки составляет $2^{75.170}$, по сравнению с $2^{80}$ с исчерпывающим поиском ключей. Сложность данных составляет 3 пары открытого/зашифрованного текста.
• КТАНТАН48, вычислительная сложность составляет $2^{75.044}$ и необходимы 2 пары открытого/зашифрованного текста.
• КТАНТАН64 это $2^{75.584}$ и необходимы 2 пары открытого/зашифрованного текста.

Результаты взяты из статьи Рехбергера и Богданова.

Это уже не лучшая атака на КТАНТАНА. Лучшая атака по состоянию на 2011 год принадлежит Вэй, Рехбергеру, Го, Ву, Вану и Лину, которые улучшили атаку MITM на семью КТАНТАН. Они пришли к вычислительной сложности $2^{72.9}$ с 4 выбранными парами открытого/зашифрованного текста с использованием методов косвенного частичного сопоставления и сращивания и вырезания MITM.