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

Общая криптографическая атака с компромиссом пространства и времени

Атака «встреча посередине» ( MITM ), известная атака с открытым текстом, ^[1] является общей криптографической атакой с компромиссом пространства и времени против схем шифрования, которые полагаются на выполнение нескольких операций шифрования последовательно. Атака MITM является основной причиной, по которой Double DES не используется и почему ключ Triple DES (168 бит) может быть взломан ^{[ требуется разъяснение ]} злоумышленником с 2 ⁵⁶ пробелами и 2 ¹¹² операциями. ^[2]

Описание

При попытке улучшить безопасность блочного шифра заманчивой идеей является шифрование данных несколько раз с использованием нескольких ключей. Можно подумать, что это удваивает или даже увеличивает безопасность схемы многократного шифрования в n раз , в зависимости от того, сколько раз данные шифруются, поскольку полный перебор всех возможных комбинаций ключей (простой перебор) займет 2 ^{n · k} попыток, если данные зашифрованы с помощью k -битных ключей n раз.

MITM — это общая атака, которая ослабляет преимущества безопасности использования множественных шифрований, сохраняя промежуточные значения из шифрований или дешифрований и используя их для улучшения времени, необходимого для подбора ^{[ необходимо разъяснение ]} ключей дешифрования. Это делает атаку Meet-in-the-Middle (MITM) общей криптографической атакой с компромиссом пространства и времени ^[3] .

Атака MITM пытается найти ключи, используя как диапазон (шифротекст), так и домен (открытый текст) композиции нескольких функций (или блочных шифров), так что прямое отображение через первые функции совпадает с обратным отображением (обратное изображение) через последние функции, буквально встречаясь в середине составленной функции. Например, хотя Double DES шифрует данные двумя разными 56-битными ключами, Double DES можно взломать с помощью 2 ⁵⁷ операций шифрования и дешифрования.

Многомерный MITM (MD-MITM) использует комбинацию нескольких одновременных атак MITM, подобных описанным выше, где встреча происходит в нескольких позициях в составной функции.

История

Диффи и Хеллман впервые предложили атаку «встреча посередине» на гипотетическое расширение блочного шифра в 1977 году. ^[4] Их атака использовала компромисс между пространством и временем , чтобы взломать схему двойного шифрования всего за два времени, необходимых для взлома схемы одинарного шифрования.

В 2011 году Бо Чжу и Гуан Гун исследовали многомерную атаку «встреча посередине» и представили новые атаки на блочные шифры ГОСТ , KTANTAN и Hummingbird-2. ^[5]

Встреча посередине (1D-MITM)

Предположим, что кто-то хочет атаковать схему шифрования со следующими характеристиками для заданного открытого текста P и шифртекста C :

${\displaystyle {\begin{aligned}C&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(P))\\P&={\mathit {DEC}}_{k_{1}}({\mathit {DEC}}_{k_{2}}(C))\\\end{aligned}}}$

где ENC — функция шифрования, DEC — функция дешифрования, определяемая как ENC ⁻¹ (обратное отображение), а k ₁ и k ₂ — два ключа.

Наивный подход к брутфорсу этой схемы шифрования заключается в расшифровке зашифрованного текста с использованием каждого возможного k ₂ и расшифровке каждого из промежуточных выходных данных с использованием каждого возможного k ₁ , что в общей сложности составляет 2 ^{|k ₁ |} × 2 ^{|k ₂ |} (или 2 ^{|k ₁ |+|k ₂ |} ) операций.

Атака meet-in-the-middle использует более эффективный подход. Расшифровывая C с помощью k ₂ , получаем следующую эквивалентность:

${\displaystyle {\begin{aligned}C&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(P))\\{\mathit {DEC}}_{k_{2}}(C)&={\mathit {DEC}}_{k_{2}}({\mathit {ENC}}_{k_{2}}[{\mathit {ENC}}_{k_{1}}(P)])\\{\mathit {DEC}}_{k_{2}}(C)&={\mathit {ENC}}_{k_{1}}(P)\\\end{aligned}}}$

Атакующий может вычислить ENC _{k 1} ( P ) для всех значений k ₁ и DEC _{k 2} ( C ) для всех возможных значений k ₂ , что в общей сложности составит 2 ^{|k ₁ |} + 2 ^{|k ₂ |} (или 2 ^{|k ₁ |+1} , если k ₁ и k ₂ имеют одинаковый размер) операций. Если результат любой из операций ENC _{k 1} ( P ) совпадает с результатом операций DEC _{k 2} ( C ), пара k ₁ и k ₂ , возможно, является правильным ключом. Этот потенциально правильный ключ называется потенциальным ключом . Атакующий может определить, какой потенциальный ключ является правильным, проверив его с помощью второго тестового набора открытого текста и зашифрованного текста.

Атака MITM является одной из причин, по которой стандарт шифрования данных (DES) был заменен на Triple DES , а не на Double DES. Злоумышленник может использовать атаку MITM для подбора Double DES с 2 ⁵⁷ операциями и 2 ⁵⁶ пространством, что делает его лишь небольшим улучшением по сравнению с DES. ^[5] Triple DES использует ключ «тройной длины» (168 бит) и также уязвим для атаки meet-in-the-middle с 2 ⁵⁶ пространством и 2 ¹¹² операциями, но считается безопасным из-за размера своего ключевого пространства. ^{[2] [6]}

Иллюстрация атаки 1D-MITM

Алгоритм MITM

Вычислите следующее:

• ${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P),\;\forall k_{f_{1}}\in K}$:

  и сохранить каждый вместе с соответствующим в наборе A ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{f_{1}}}$

• ${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},C),\;\forall k_{b_{1}}\in K}$:

  и сравнивать каждый новый с набором A ${\displaystyle {\mathit {SubCipher}}_{1}}$

Когда совпадение найдено, сохраните как пару ключей-кандидатов в таблице T. Протестируйте пары в T на новой паре ⁠ ⁠ для подтверждения действительности. Если пара ключей не работает на этой новой паре, выполните MITM еще раз на новой паре ⁠ ⁠ . ${\displaystyle k_{f_{1}},k_{b_{1}}}$ ${\displaystyle (P,C)}$ ${\displaystyle (P,C)}$

сложность MITM

Если размер ключа равен k , эта атака использует только ^{2k +1} шифрований (и дешифрований) и O (2k ⁾ памяти для хранения результатов прямых вычислений в таблице поиска , в отличие от наивной атаки, для которой требуется 22 ^{· k} шифрований, но O (1) памяти.

Многомерный MITM (MD-MITM)

Хотя 1D-MITM может быть эффективным, была разработана более сложная атака: многомерная атака meet-in-the-middle , также сокращенно MD-MITM . Это предпочтительно, когда данные были зашифрованы с использованием более чем 2 шифрований с разными ключами. Вместо встречи посередине (в одном месте последовательности) атака MD-MITM пытается достичь нескольких определенных промежуточных состояний, используя прямые и обратные вычисления в нескольких позициях в шифре. ^[5]

Предположим, что атака должна быть реализована на блочном шифре, где шифрование и дешифрование определены так же, как и прежде:

${\displaystyle C={\mathit {ENC}}_{k_{n}}({\mathit {ENC}}_{k_{n-1}}(...({\mathit {ENC}}_{k_{1}}(P))...))}$

${\displaystyle P={\mathit {DEC}}_{k_{1}}({\mathit {DEC}}_{k_{2}}(...({\mathit {DEC}}_{k_{n}}(C))...))}$

то есть открытый текст P зашифрован несколько раз с использованием повторения одного и того же блочного шифра

Иллюстрация атаки MD-MITM

MD-MITM использовался для криптоанализа, среди прочего, блочного шифра ГОСТ , где было показано, что 3D-MITM значительно снизил временную сложность атаки на него. ^[5]

Алгоритм MD-MITM

Вычислите следующее:

${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P)\qquad \forall k_{f_{1}}\in K}$

и сохранить каждый вместе с соответствующим в наборе . ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{f_{1}}}$ ${\displaystyle H_{1}}$

${\displaystyle {\mathit {SubCipher}}_{n+1}={\mathit {DEC}}_{b_{n+1}}(k_{b_{n+1}},C)\qquad \forall k_{b_{n+1}}\in K}$

и сохранить каждый вместе с соответствующим в наборе . ${\displaystyle {\mathit {SubCipher}}_{n+1}}$ ${\displaystyle k_{b_{n+1}}}$ ${\displaystyle H_{n+1}}$

Для каждого возможного предположения о промежуточном состоянии вычислите следующее: ${\displaystyle s_{1}}$

${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},s_{1})\qquad \forall k_{b_{1}}\in K}$

и для каждого совпадения между этим и набором , сохраняйте и в новом наборе . ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle H_{1}}$ ${\displaystyle k_{b_{1}}}$ ${\displaystyle k_{f_{1}}}$ ${\displaystyle T_{1}}$

${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {ENC}}_{f_{2}}(k_{f_{2}},s_{1})\qquad \forall k_{f_{2}}\in K}$^{[ требуется проверка ]}

и сохранить каждый вместе с соответствующим в наборе . ${\displaystyle {\mathit {SubCipher}}_{2}}$ ${\displaystyle k_{f_{2}}}$ ${\displaystyle H_{2}}$

Для каждого возможного предположения о промежуточном состоянии вычислите следующее: ${\displaystyle s_{2}}$

• ${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {DEC}}_{b_{2}}(k_{b_{2}},s_{2})\qquad \forall k_{b_{2}}\in K}$

  и для каждого совпадения между этим и набором , также проверьте, ${\displaystyle {\mathit {SubCipher}}_{2}}$ ${\displaystyle H_{2}}$

  он сопоставляется с и затем сохраняет комбинацию подключей вместе в новом наборе . ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

• Для каждого возможного предположения о промежуточном состоянии вычислите следующее: ${\displaystyle s_{n}}$

1. ${\displaystyle {\mathit {SubCipher}}_{n}={\mathit {DEC}}_{b_{n}}(k_{b_{n}},s_{n})\qquad \forall k_{b_{n}}\in K}$и для каждого совпадения между этим и набором , также проверьте, совпадает ли он с , сохраните и в новом наборе . ${\displaystyle {\mathit {SubCipher}}_{n}}$ ${\displaystyle H_{n}}$ ${\displaystyle T_{n-1}}$ ${\displaystyle k_{b_{n}}}$ ${\displaystyle k_{f_{n}}}$ ${\displaystyle T_{n}}$
2. ${\displaystyle {\mathit {SubCipher}}_{n+1}={\mathit {ENC}}_{f_{n}+1}(k_{f_{n}+1},s_{n})\qquad \forall k_{f_{n+1}}\in K}$и для каждого соответствия между этим и множеством , также проверьте, соответствует ли оно . Если это так, то:" ${\displaystyle {\mathit {SubCipher}}_{n+1}}$ ${\displaystyle H_{n+1}}$ ${\displaystyle T_{n}}$

Используйте найденную комбинацию подключей в другой паре открытого текста/зашифрованного текста для проверки правильности ключа. ${\displaystyle (k_{f_{1}},k_{b_{1}},k_{f_{2}},k_{b_{2}},...,k_{f_{n+1}},k_{b_{n+1}})}$

Обратите внимание на вложенный элемент в алгоритме. Догадка о каждом возможном значении s _j делается для каждой догадки о предыдущем s _{j -1} . Это составляет элемент экспоненциальной сложности к общей временной сложности этой атаки MD-MITM.

Сложность MD-MITM

Временная сложность этой атаки без перебора составляет ⋅ ⋅ ${\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|s_{1}|}}$ ${\displaystyle (2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}+2^{|s_{2}|}}$ ${\displaystyle (2^{|k_{b_{2}}|}+2^{|k_{f_{3}}|}+\cdots ))}$

Что касается сложности памяти, легко увидеть, что они намного меньше, чем первая построенная таблица значений-кандидатов: по мере увеличения i содержащиеся в значения-кандидаты должны удовлетворять большему количеству условий, поэтому меньшее количество кандидатов перейдет в конечный пункт назначения . ${\displaystyle T_{2},T_{3},...,T_{n}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{i}}$ ${\displaystyle T_{n}}$

Верхняя граница сложности памяти MD-MITM тогда равна

${\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s_{n}|}\cdots }$

где k обозначает длину всего ключа (в совокупности).

Сложность данных зависит от вероятности того, что может пройти неверный ключ (получить ложный положительный результат), которая равна , где l — промежуточное состояние в первой фазе MITM. Размер промежуточного состояния и размер блока часто совпадают! Учитывая также, сколько ключей осталось для тестирования после первой фазы MITM, это . ${\displaystyle 1/2^{|l|}}$ ${\displaystyle 2^{|k|}/2^{|l|}}$

Таким образом, после первой фазы MITM имеем , где — размер блока. ${\displaystyle 2^{|k|-b}\cdot 2^{-b}=2^{|k|-2b}}$ ${\displaystyle |b|}$

Каждый раз, когда окончательное значение-кандидат ключей проверяется на новой паре открытого текста/шифротекста, количество прошедших проверку ключей будет умножаться на вероятность того, что ключ может пройти проверку, которая составляет . ${\displaystyle 1/2^{|b|}}$

Часть тестирования методом полного перебора (проверка потенциального ключа на новых ⁠ ⁠ ${\displaystyle (P,C)}$ -парах) имеет временную сложность , очевидно, что для увеличения кратности b в показателе степени число стремится к нулю. ${\displaystyle 2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+2^{|k|-4b}\cdots }$

Вывод о сложности данных по аналогичным соображениям ограничен выводом о сложности ⁠ ⁠ -пар. ${\displaystyle \lceil |k|/n\rceil }$ ${\displaystyle (P,C)}$

Ниже приведен конкретный пример монтажа 2D-MITM:

Общий пример 2D-MITM

Это общее описание того, как 2D-MITM монтируется на блочном шифре.

В двумерном MITM (2D-MITM) метод заключается в достижении двух промежуточных состояний внутри множественного шифрования открытого текста. См. рисунок ниже:

Иллюстрация атаки 2D-MITM

Алгоритм 2D-MITM

Вычислите следующее:

${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P)\qquad \forall k_{f_{1}}\in K}$

и сохранить каждый вместе с соответствующим в наборе A ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{f_{1}}}$

${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {DEC}}_{b_{2}}(k_{b_{2}},C)\qquad \forall k_{b_{2}}\in K}$

и сохраните каждый из них вместе с соответствующим в наборе B. ${\displaystyle {\mathit {SubCipher}}_{2}}$ ${\displaystyle k_{b_{2}}}$

Для каждого возможного предположения о промежуточном состоянии s между и вычислите следующее: ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle {\mathit {SubCipher}}_{2}}$

• ${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},s)\qquad \forall k_{b_{1}}\in K}$

  и для каждого совпадения между этим и набором A сохранить и в новом наборе T. ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{b_{1}}}$ ${\displaystyle k_{f_{1}}}$

• ${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {ENC}}_{f_{2}}(k_{f_{2}},s)\qquad \forall k_{f_{2}}\in K}$

  и для каждого соответствия между этим и множеством B, также проверьте, соответствует ли оно множеству T для ${\displaystyle {\mathit {SubCipher}}_{2}}$

  если это так, то:

Используйте найденную комбинацию подключей в другой паре открытого текста/зашифрованного текста для проверки правильности ключа. ${\displaystyle (k_{f_{1}},k_{b_{1}},k_{f_{2}},k_{b_{2}})}$

2D-MITM сложность

Временная сложность этой атаки без перебора составляет

${\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{2}}|}+2^{|s|}\cdot \left(2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}\right)}$

где |⋅| обозначает длину.

Потребление основной памяти ограничено построением множеств A и B , где T намного меньше остальных.

Информацию о сложности данных см. в подразделе о сложности для MD-MITM.

Смотрите также

• Атака на день рождения
• Безопасность беспроводной связи
• Криптография
• Атака «встреча посередине» с 3 подмножествами
• Атака «встреча посередине» с частичным соответствием

Ссылки

1. «Крипто-ИТ».
2. Мур, Стефан (16 ноября 2010 г.). «Атаки «встречи посередине»» (PDF) : 2. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
3. victoria, jaynor. "victoria15". victoria14 . Архивировано из оригинала 14 июля 2021 г. . Получено 14 июля 2021 г. .
4. ^ Диффи, Уитфилд; Хеллман, Мартин Э. (июнь 1977 г.). «Исчерпывающий криптоанализ стандарта шифрования данных NBS» (PDF) . Компьютер . 10 (6): 74–84. doi :10.1109/CM.1977.217750. S2CID  2412454.
5. Чжу, Бо; Гун, Гуан (2014). «Многомерная атака meet-in-the-middle и ее применение к KATAN32/48/64». Криптография и связь . 6 : 313–333. doi :10.1007/s12095-014-0102-9 – через Springer Link.
6. Блондо, Селин. "Лекция 3: Блочные шифры" (PDF) . CS-E4320 Криптография и безопасность данных . Архивировано из оригинала (PDF) 2018-02-23 . Получено 2018-02-22 .