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

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

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

История

Оригинальная атака MITM была впервые предложена в статье Диффи и Хеллмана в 1977 году, где они обсуждали криптоаналитические свойства DES. ^{[ 1 ]} Они утверждали, что размер ключа 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 году. ^{[ 2 ]} и показал его использование в криптоанализе шифров, таких как облегченное семейство блочных шифров KTANTAN.

Процедура

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

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

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

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

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

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

За каждое предположение $A_{0}$ $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 году. ^{[ 3 ]} Он принимает блок размером 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 на семью КТАНТАН. ^{[ 4 ]} Они пришли к вычислительной сложности $2^{72.9}$ с 4 выбранными парами открытого/зашифрованного текста с использованием методов косвенного частичного сопоставления и сращивания и вырезания MITM.

Примечания

^ Уитфилд Диффи, Мартин Э. Хеллман. «Исчерпывающий криптоанализ стандарта шифрования данных NBS»
^ Андрей Богданов и Кристиан Рехбергер. «Атака по схеме «встреча посередине» с использованием трех подмножеств: криптоанализ легкого блочного шифра КТАНТАН»
^ Кристоф Де Каньер, Орр Дункельман , Мирослав Кнежевич. «КАТАН И КТАНТАН — семейство небольших и эффективных аппаратно-ориентированных блочных шифров»
^ Лэй Вэй, Кристиан Рехбергер, Цзянь Го, Хунцзюнь Ву, Хуасюн Ван и Сан Лин. «Улучшенный криптоанализ KTANTAN по схеме «встреча посередине»»

[1] Уитфилд Диффи, Мартин Э. Хеллман. «Исчерпывающий криптоанализ стандарта шифрования данных NBS»

[2] Андрей Богданов и Кристиан Рехбергер. «Атака по схеме «встреча посередине» с использованием трех подмножеств: криптоанализ легкого блочного шифра КТАНТАН»

[3] Кристоф Де Каньер, Орр Дункельман , Мирослав Кнежевич. «КАТАН И КТАНТАН — семейство небольших и эффективных аппаратно-ориентированных блочных шифров»

[4] Лэй Вэй, Кристиан Рехбергер, Цзянь Го, Хунцзюнь Ву, Хуасюн Ван и Сан Лин. «Улучшенный криптоанализ KTANTAN по схеме «встреча посередине»»

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]