Атака по центру - Meet-in-the-middle attack

Эта статья посвящена процессу оптимизации криптоанализа. О форме перехвата связи см. Атака посредника.

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

Описание

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

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

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

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

История

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

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

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

Предположим, кто-то хочет атаковать схему шифрования со следующими характеристиками для данного открытого текста п и зашифрованный текст 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₂) операции.

Атака встречи посередине использует более эффективный подход. Расшифровывая 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_k1(п) для всех значений k₁ и DEC_k2(C) для всех возможных значений k₂, всего 2^k₁ + 2^k₂ (или 2^k₁+1, если k₁ и k₂ одного размера) операции. Если результат любого из ENC_k1(п) соответствует результату DEC_k2(C) операций пара k₁ и k₂ возможно правильный ключ. Этот потенциально правильный ключ называется кандидат ключ. Злоумышленник может определить, какой ключ-кандидат правильный, проверив его с помощью второго тестового набора открытого текста и зашифрованного текста.

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

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

Алгоритм MITM

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

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

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

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

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

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

MITM сложность

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

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

Хотя 1D-MITM может быть эффективным, была разработана более сложная атака: многомерная атака на встречу посередине, также сокращенно МД-МИТМ. Это предпочтительнее, если данные были зашифрованы с использованием более чем двух способов шифрования с разными ключами. Вместо того, чтобы встречаться посередине (одно место в последовательности), атака 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.

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

Временная сложность этой атаки без грубой силы составляет ${\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 ))}$

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

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

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

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

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

Заключение о сложности данных основано на аналогичных рассуждениях, ограниченных тем, что вокруг ${\displaystyle \lceil |k|/n\rceil }$ ${\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}}\in K}$

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

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

и сохранить каждый ${\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}$

  и для каждого матча между этим ${\displaystyle {\mathit {SubCipher}}_{1}}$ и множество A, за исключением ${\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}$

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

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

Используйте найденную комбинацию подключей ${\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)}$

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

Потребление оперативной памяти ограничено конструкцией наборов А и B куда Т намного меньше других.

Для сложности данных см. подраздел по сложности для МД-МИТМ.

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

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

Рекомендации

1. http://www.crypto-it.net/eng/attacks/meet-in-the-middle.html
2. Мур, Стефан (16 ноября 2010 г.). "Атаки по центру" (PDF): 2.
3. Блондо, Селин. «Лекция 3: Блочные шифры» (PDF). CS-E4320 Криптография и безопасность данных.
4. ^ Диффи, Уитфилд; Хеллман, Мартин Э. (июнь 1977 г.). «Исчерпывающий криптоанализ стандарта шифрования данных NBS» (PDF). Компьютер. 10 (6): 74–84. Дои:10.1109 / C-M.1977.217750. S2CID  2412454.
5. Чжу, Бо; Гуан Гун (2011). "Атака MD-MITM и ее приложения к ГОСТ, КТАНТАН и Колибри-2". eCrypt.
6. Чжу, Бо; Гуан Гун (2011). «Атака MD-MITM и ее применение к ГОСТ, КТАНТАН и Колибри-2». eCrypt.