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

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

Описание [ править ]

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

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

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

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

История [ править ]

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

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

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

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

{\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 ^{|к ₁ |} × 2 ^{|к ₂ |} (или 2 ^{|к ₁ |+|к ₂ |}) операции.

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

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

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

Алгоритм MITM [ править ]

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

${\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P),\;\forall k_{f_{1}}\in K$ :
и сохраните каждый ${\mathit {SubCipher}}_{1}$ вместе с соответствующими $k_{f_{1}}$ в комплекте А
${\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},C),\;\forall k_{b_{1}}\in K$ :
и сравнивать каждое новое ${\mathit {SubCipher}}_{1}$ с набором А

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

Сложность MITM [ править ]

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

Многомерный MITM (MD-MITM) [ править ]

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

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

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

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

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

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

Алгоритм MD-MITM [ править ]

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

${\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P)\qquad \forall k_{f_{1}}\in K$: и сохраните каждый ${\mathit {SubCipher}}_{1}$ вместе с соответствующими $k_{f_{1}}$ в наборе $H_{1}$ .

${\mathit {SubCipher}}_{n+1}={\mathit {DEC}}_{b_{n+1}}(k_{b_{n+1}},C)\qquad \forall k_{b_{n+1}}\in K$: и сохраните каждый ${\mathit {SubCipher}}_{n+1}$ вместе с соответствующими $k_{b_{n+1}}$ в наборе $H_{n+1}$ .

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

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

${\mathit {SubCipher}}_{2}={\mathit {ENC}}_{f_{2}}(k_{f_{2}},s_{1})\qquad \forall k_{f_{2}}\in K$ ^{[ нужна проверка ]}: и сохраните каждый ${\mathit {SubCipher}}_{2}$ вместе с соответствующими $k_{f_{2}}$ в наборе $H_{2}$ .

Для каждого возможного предположения о промежуточном состоянии

s_{2}

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

${\mathit {SubCipher}}_{2}={\mathit {DEC}}_{b_{2}}(k_{b_{2}},s_{2})\qquad \forall k_{b_{2}}\in K$
и для каждого совпадения между этим ${\mathit {SubCipher}}_{2}$ и набор $H_{2}$ , проверьте также, есть ли
это совпадает с $T_{1}$ а затем сохраните комбинацию дополнительных клавиш в новом наборе $T_{2}$ .
Для каждого возможного предположения о промежуточном состоянии $s_{n}$ вычислите следующее:

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

Используйте найденную комбинацию подразделов $(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 [ править ]

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

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

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

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

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

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

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

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

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

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

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

Общий пример 2D-MITM [ править ]

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

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

Алгоритм 2D-MITM [ править ]

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

${\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P)\qquad \forall k_{f_{1}}\in K$: и сохраните каждый ${\mathit {SubCipher}}_{1}$ вместе с соответствующими $k_{f_{1}}$ в комплекте А
${\mathit {SubCipher}}_{2}={\mathit {DEC}}_{b_{2}}(k_{b_{2}},C)\qquad \forall k_{b_{2}}\in K$: и сохраните каждый ${\mathit {SubCipher}}_{2}$ вместе с соответствующими $k_{b_{2}}$ в комплекте Б.

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

${\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},s)\qquad \forall k_{b_{1}}\in K$
и для каждого совпадения между этим ${\mathit {SubCipher}}_{1}$ и набор A, сохраните $k_{b_{1}}$ и $k_{f_{1}}$ в новом наборе Т.
${\mathit {SubCipher}}_{2}={\mathit {ENC}}_{f_{2}}(k_{f_{2}},s)\qquad \forall k_{f_{2}}\in K$
и для каждого совпадения между этим ${\mathit {SubCipher}}_{2}$ и множества B, проверьте также, совпадает ли оно с T для
если это так, то:

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

Сложность 2D-MITM [ править ]

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

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» .

См. также [ править ]

Ссылки [ править ]

^ «Крипто-ИТ» .
↑ Перейти обратно: Перейти обратно: ^а ^б Мур, Стефан (16 ноября 2010 г.). «Атаки «Встреча посередине»» (PDF) : 2. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Виктория, Джейнор. "Виктория15" . Виктория14 . Архивировано из оригинала 14 июля 2021 года . Проверено 14 июля 2021 г.
^ ^ Диффи, Уитфилд; Хеллман, Мартин Э. (июнь 1977 г.). «Исчерпывающий криптоанализ стандарта шифрования данных NBS» (PDF) . Компьютер . 10 (6): 74–84. дои : 10.1109/CM.1977.217750 . S2CID 2412454 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Чжу, Бо; Гуан Гун (2011). «Атака MD-MITM и ее приложения к ГОСТ, КТАНТАН и Колибри-2» . Электронный Крипт .
^ Чжу, Бо; Гуан Гун (2011). «Атака MD-MITM и ее применение к ГОСТ, КТАНТАН и Колибри-2». Электронный Крипт .
^ Блондо, Селин. «Лекция 3: Блочные шифры» (PDF) . CS-E4320 Криптография и безопасность данных . Архивировано из оригинала (PDF) 23 февраля 2018 г. Проверено 22 февраля 2018 г.

[1] «Крипто-ИТ» .

[:0-2] Перейти обратно: Перейти обратно: ^а ^б Мур, Стефан (16 ноября 2010 г.). «Атаки «Встреча посередине»» (PDF) : 2. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[3] Виктория, Джейнор. "Виктория15" . Виктория14 . Архивировано из оригинала 14 июля 2021 года . Проверено 14 июля 2021 г.

[4] Диффи, Уитфилд; Хеллман, Мартин Э. (июнь 1977 г.). «Исчерпывающий криптоанализ стандарта шифрования данных NBS» (PDF) . Компьютер . 10 (6): 74–84. дои : 10.1109/CM.1977.217750 . S2CID 2412454 .

[ZhuGuang2011-5] Перейти обратно: Перейти обратно: ^а ^б ^с Чжу, Бо; Гуан Гун (2011). «Атака MD-MITM и ее приложения к ГОСТ, КТАНТАН и Колибри-2» . Электронный Крипт .

[6] Чжу, Бо; Гуан Гун (2011). «Атака MD-MITM и ее применение к ГОСТ, КТАНТАН и Колибри-2». Электронный Крипт .

[:1-7] Блондо, Селин. «Лекция 3: Блочные шифры» (PDF) . CS-E4320 Криптография и безопасность данных . Архивировано из оригинала (PDF) 23 февраля 2018 г. Проверено 22 февраля 2018 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]