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

редактировать

Эта статья посвящена процессу оптимизации криптоанализа. Чтобы узнать о форме перехвата связи, см. Атака «Человек посередине».

Встречаются в-середины атака ( MITM), известная открытый текст атака, является общим пространственно-временный компромисс криптографической атакой против схем шифрования, которые полагаются на выполнение нескольких операций шифрования в последовательности. Атака MITM является основной причиной того, почему двойной DES не используется и почему ключ тройного DES (168-битный) может быть взломан злоумышленником с 2 ⁵⁶ пробелами и 2 ¹¹² операциями.

СОДЕРЖАНИЕ

1 Описание
2 История
3 Встреча посередине (1D-MITM)
- 3.1 Алгоритм MITM
- 3.2 Сложность MITM
4 Многомерный MITM (MD-MITM)
- 4.1 Алгоритм MD-MITM
- 4.2 Сложность МД-МИТМ
5 Общий пример 2D-MITM
- 5.1 2D-MITM алгоритм
- 5.2 2D-MITM сложность
6 Смотрите также
7 использованная литература

Описание

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

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

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

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

История

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

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

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

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

{\ displaystyle {\ begin {align} C amp; = {\ mathit {ENC}} _ ​​{k_ {2}} ({\ mathit {ENC}} _ ​​{k_ {1}} (P)) \\ P amp; = {\ mathit {DEC}} _ ​​{k_ {1}} ({\ mathit {DEC}} _ ​​{k_ {2}} (C)) \\\ конец {выровнено}}}

{\ displaystyle {\ begin {align} C amp; = {\ mathit {ENC}} _ ​​{k_ {2}} ({\ mathit {ENC}} _ ​​{k_ {1}} (P)) \\ P amp; = {\ mathit {DEC}} _ ​​{k_ {1}} ({\ mathit {DEC}} _ ​​{k_ {2}} (C)) \\\ конец {выровнено}}}

где ENC - функция шифрования, DEC - функция дешифрования, определенная как ENC ^-1 (обратное отображение), а k 1 и k 2 - два ключа.

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

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

{\ displaystyle {\ begin {align} C amp; = {\ mathit {ENC}} _ ​​{k_ {2}} ({\ mathit {ENC}} _ ​​{k_ {1}} (P)) \\ {\ mathit { DEC}} _ ​​{k_ {2}} (C) amp; = {\ mathit {DEC}} _ ​​{k_ {2}} ({\ mathit {ENC}} _ ​​{k_ {2}} [{\ mathit {ENC }} _ {k_ {1}} (P)]) \\ {\ mathit {DEC}} _ ​​{k_ {2}} (C) amp; = {\ mathit {ENC}} _ ​​{k_ {1}} ( P) \\\ конец {выровнен}}}

{\ displaystyle {\ begin {align} C amp; = {\ mathit {ENC}} _ ​​{k_ {2}} ({\ mathit {ENC}} _ ​​{k_ {1}} (P)) \\ {\ mathit { DEC}} _ ​​{k_ {2}} (C) amp; = {\ mathit {DEC}} _ ​​{k_ {2}} ({\ mathit {ENC}} _ ​​{k_ {2}} [{\ mathit {ENC }} _ {k_ {1}} (P)]) \\ {\ mathit {DEC}} _ ​​{k_ {2}} (C) amp; = {\ mathit {ENC}} _ ​​{k_ {1}} ( P) \\\ конец {выровнен}}}

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

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

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

Алгоритм MITM

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

${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {ENC}} _ {f_ {1}} (k_ {f_ {1}}, P), \; \ forall k_ {f_ {1 }}\чернила}$ ${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {ENC}} _ {f_ {1}} (k_ {f_ {1}}, P), \; \ forall k_ {f_ {1 }}\чернила}$ :
и сохраним каждую вместе с соответствующими в наборе A ${\ displaystyle {\ mathit {SubCipher}} _ {1}}$ ${\ displaystyle {\ mathit {SubCipher}} _ {1}}$ ${\ displaystyle k_ {f_ {1}}}$ $k _ {{f_ {1}}}$
${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {DEC}} _ {b_ {1}} (k_ {b_ {1}}, C), \; \ forall k_ {b_ {1 }}\чернила}$ ${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {DEC}} _ {b_ {1}} (k_ {b_ {1}}, C), \; \ forall k_ {b_ {1 }}\чернила}$ :
и сравниваем каждую новую с множеством A ${\ displaystyle {\ mathit {SubCipher}} _ {1}}$ ${\ displaystyle {\ mathit {SubCipher}} _ {1}}$

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

Сложность MITM

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

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

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

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

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

{\ 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))...))}

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

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

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

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

Алгоритм MD-MITM

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

${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {ENC}} _ {f_ {1}} (k_ {f_ {1}}, P) \ qquad \ forall k_ {f_ {1} }\чернила}$ ${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {ENC}} _ {f_ {1}} (k_ {f_ {1}}, P) \ qquad \ forall k_ {f_ {1} }\чернила}$: и сохраните каждый вместе с соответствующим в наборе. ${\ displaystyle {\ mathit {SubCipher}} _ {1}}$ ${\ displaystyle {\ mathit {SubCipher}} _ {1}}$ ${\ displaystyle k_ {f_ {1}}}$ $k _ {{f_ {1}}}$ ${\ displaystyle H_ {1}}$ $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} = {\ mathit {DEC}} _ {b_ {n + 1}} (k_ {b_ {n + 1}}, C) \ qquad \ forall k_ {b_ {n + 1}} \ in K}$: и сохраните каждый вместе с соответствующим в наборе. ${\ displaystyle {\ mathit {SubCipher}} _ {n + 1}}$ ${\ displaystyle {\ mathit {SubCipher}} _ {n + 1}}$ ${\ displaystyle k_ {b_ {n + 1}}}$ $k _ {{b _ {{n + 1}}}}$ ${\ displaystyle H_ {n + 1}}$ $H _ {{n + 1}}$

Для каждого возможного предположения о промежуточном состоянии вычислите следующее: ${\ displaystyle s_ {1}}$ $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} = {\ mathit {DEC}} _ {b_ {1}} (k_ {b_ {1}}, s_ {1}) \ qquad \ forall k_ {b_ {1}} \ in K}$: и для каждого совпадения между этим и набором сохраняйте и в новом наборе. ${\ displaystyle {\ mathit {SubCipher}} _ {1}}$ ${\ displaystyle {\ mathit {SubCipher}} _ {1}}$ ${\ displaystyle H_ {1}}$ $H_ {1}$ ${\ displaystyle k_ {b_ {1}}}$ $k _ {{b_ {1}}}$ ${\ displaystyle k_ {f_ {1}}}$ $k _ {{f_ {1}}}$ ${\ displaystyle T_ {1}}$ $Т_ {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} = {\ mathit {ENC}} _ {f_ {2}} (k_ {f_ {2}}, s_ {1}) \ qquad \ forall k_ {f_ {2}} \ in K}$: и сохраните каждый вместе с соответствующим в наборе. ${\ displaystyle {\ mathit {SubCipher}} _ {2}}$ ${\ displaystyle {\ mathit {SubCipher}} _ {2}}$ ${\ displaystyle k_ {f_ {2}}}$ $k _ {{f_ {2}}}$ ${\ displaystyle H_ {2}}$ $H_ {2}$

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

{\ displaystyle s_ {2}}

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} = {\ mathit {DEC}} _ {b_ {2}} (k_ {b_ {2}}, s_ {2}) \ qquad \ forall k_ {b_ {2}} \ in K}$

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

он совпадает с и затем сохраняет комбинацию подключей вместе в новом наборе. ${\ displaystyle T_ {1}}$ $Т_ {1}$ ${\ displaystyle T_ {2}}$ $Т_ {2}$
Для каждого возможного предположения о промежуточном состоянии вычислите следующее: ${\ displaystyle s_ {n}}$ $s_n$

${\ displaystyle {\ mathit {SubCipher}} _ {n} = {\ mathit {DEC}} _ {b_ {n}} (k_ {b_ {n}}, s_ {n}) \ qquad \ forall k_ {b_ {n}} \ in K}$ ${\ 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 {\ mathit {SubCipher}} _ {n}}$ ${\ displaystyle H_ {n}}$ $H_ {n}$ ${\ displaystyle T_ {n-1}}$ $Т _ {{n-1}}$ ${\ displaystyle k_ {b_ {n}}}$ $k _ {{b_ {n}}}$ ${\ displaystyle k_ {f_ {n}}}$ $k _ {{f_ {n}}}$ ${\ displaystyle T_ {n}}$ $T_ {n}$
${\ 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} = {\ 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 {\ mathit {SubCipher}} _ {n + 1}}$ ${\ displaystyle H_ {n + 1}}$ $H _ {{n + 1}}$

совпадает ли он с. Если это так, то: " ${\ displaystyle T_ {n}}$ $T_ {n}$

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

Сложность МД-МИТМ

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

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

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

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

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

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

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

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

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

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

Заключение о сложности данных основано на аналогичных рассуждениях, ограниченных парами. ${\ Displaystyle \ lceil | к | / п \ rceil}$ ${\ Displaystyle \ lceil | к | / п \ rceil}$ ${\ displaystyle (P, C)}$ ${\ displaystyle (P, C)}$

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

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

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

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

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

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

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

${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {ENC}} _ {f_ {1}} (k_ {f_ {1}}, P) \ qquad \ forall k_ {f_ {1} }\чернила}$ ${\ displaystyle {\ mathit {SubCipher}} _ {1} = {\ mathit {ENC}} _ {f_ {1}} (k_ {f_ {1}}, P) \ qquad \ forall k_ {f_ {1} }\чернила}$: и сохраним каждую вместе с соответствующими в наборе A ${\ displaystyle {\ mathit {SubCipher}} _ {1}}$ ${\ displaystyle {\ mathit {SubCipher}} _ {1}}$ ${\ displaystyle k_ {f_ {1}}}$ $k _ {{f_ {1}}}$
${\ displaystyle {\ mathit {SubCipher}} _ {2} = {\ mathit {DEC}} _ {b_ {2}} (k_ {b_ {2}}, C) \ qquad \ forall k_ {b_ {2} }\чернила}$ ${\ displaystyle {\ mathit {SubCipher}} _ {2} = {\ mathit {DEC}} _ {b_ {2}} (k_ {b_ {2}}, C) \ qquad \ forall k_ {b_ {2} }\чернила}$: и сохраните каждую вместе с соответствующими в наборе B. ${\ displaystyle {\ mathit {SubCipher}} _ {2}}$ ${\ displaystyle {\ mathit {SubCipher}} _ {2}}$ ${\ displaystyle k_ {b_ {2}}}$ $k _ {{b_ {2}}}$

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

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

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

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

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

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.

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

использованная литература