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

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

С момента публикации Диффи и Хеллмана появилось множество вариантов атак «встречей посередине». Некоторые из них делают атаку более эффективной или расширяют области применения, где базовый вариант был невозможен. Вариант с 3-подмножествами предложен Богдановым и Рехбергером в 2011 году^[2] и показал свою эффективность для криптоанализа таких шифров, как семейство облегчённых блочных шифров KTANTAN.

Как и в случае с классической атакой «встречей посередине», процесс делится на две фазы: фазу сокращения пространства ключей и фазу проверки ключа. На первом этапе пространство возможных ключей сужается за счёт применения самой атаки. На втором этапе полученные кандидаты на роль ключа проверяются на другой паре открытый/зашифрованный текст (plaintext/ciphertext) для отбраковки неверных кандидатов.

В этой фазе исходный шифр разбивается на два субшифра, ${\displaystyle f}$ и ${\displaystyle g}$, каждый со своими независимыми битами ключа, как это и принято в атаках данного класса. Вместо строгого требования независимости битов, атака 3-подмножеств позволяет некоторым битам участвовать в обоих субшифрах.

Ключ делится на три подмножества:

• ${\displaystyle A_{0}}$ — биты ключа, которые используются обоими субшифрами.
• ${\displaystyle A_{1}}$ — биты, уникальные для первого субшифра ${\displaystyle f}$.
• ${\displaystyle A_{2}}$ — биты, уникальные для второго субшифра ${\displaystyle g}$.

Дальнейшая процедура перебора для атаки по этим трём подмножествам:

1. Для каждой догадки ${\displaystyle A_{0}}$:
   1. Вычислить промежуточное значение ${\displaystyle i}$ из открытого текста для всех комбинаций ключ-битов ${\displaystyle A_{1}}$.
   2. Вычислить промежуточное значение ${\displaystyle j}$ для всех комбинаций ${\displaystyle A_{2}}$.
   3. Сравнить ${\displaystyle i}$ и ${\displaystyle j}$. При совпадении сохранить соответствующую комбинацию как кандидата на ключ.

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

Здесь рассмотрен пример атаки на семейство шифров KTANTAN, изложенный в работе Рехбергера и Богданова. Соглашения по обозначениям соответствуют их оригинальной статье. Эта атака снижает вычислительную сложность для KTANTAN32 до ${\displaystyle 2^{75.170}}$ против ${\displaystyle 2^{80}}$ для полного перебора. Однако на 2014 год сложность ${\displaystyle 2^{75.170}}$ всё ещё не реализуема на практике и не делает атаку эффективной для реального взлома. Аналогичная оценка справедлива для KTANTAN48 и KTANTAN64 (см. ниже).

Возможность атаки обусловлена особенностями битовой схемы расширения ключа (key-schedule) KTANTAN. Метод применим ко всем вариантам (KTANTAN32, KTANTAN48, KTANTAN64), так как у них одинаковое распределение ключевых битов. Он не применим к родственным блочным шифрам из семейства KANTAN из-за другой схемы расширения ключа.

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

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

Точнее:

• Раунды 1-111 вовсе не используют ключевые биты ${\displaystyle k_{32},k_{39},k_{44},k_{61},k_{66},k_{75}}$
• Раунды 131—254 не используют ${\displaystyle k_{3},k_{20},k_{41},k_{47},k_{63},k_{74}}$

Эту особенность и используют для постановки атаки — появляется возможность разделить алгоритм на два блока с независимыми ключевыми битами. Исключёнными битами определяются параметры атаки:

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

В этом этапе возникает проблема: в шаге 1.3 нельзя напрямую сравнить значения ${\displaystyle i}$ и ${\displaystyle j}$, ведь ${\displaystyle i}$ вычисляется на выходе раунда 111, а ${\displaystyle j}$ — на входе раунда 131. Для обхода этого препятствия применяется разновидность MITM, называемая частичное совпадение. Авторы атаки установили, что если вычислять вперёд из ${\displaystyle i}$ и назад из ${\displaystyle j}$, то на раунде 127 8 бит состояния остаются неизменными с вероятностью единица — их и сравнивают (для KTANTAN32 это 8 бит на 127-м раунде, для KTANTAN48 — 10 бит на 123-м, для KTANTAN64 — 47 бит на 131-м раунде). Это увеличивает число ложных совпадений, но существенного роста вычислительной сложности не даёт.

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

Для:

• KTANTAN32 вычислительная сложность описанной атаки составляет ${\displaystyle 2^{75.170}}$ при количестве данных 3 пары открытый/зашифрованный текст (против ${\displaystyle 2^{80}}$ для полного перебора);
• KTANTAN48 — сложность ${\displaystyle 2^{75.044}}$, необходимы 2 пары;
• KTANTAN64 — ${\displaystyle 2^{75.584}}$ и 2 пары.

Данные взяты из работы Рехбергера и Богданова.

С 2011 года атака 3-подмножеств уступила наилучшей на тот момент атаке на KTANTAN, предложенной Вэй, Рехбергером, Го, Ву, Ваном и Лином, которая позволила снизить сложность до ${\displaystyle 2^{72.9}}$ с 4 выбранными парами открытый/зашифрованный текст благодаря техникам частичного совпадения и splice & cut MITM^[4].