Атака встреча посередине - Meet-in-the-middle attack
Встречаются в-середины атака ( MITM ), известная открытый текст атака, является общим пространственно-временный компромисс криптографической атакой против схем шифрования , которые полагаются на выполнение нескольких операций шифрования в последовательности. Атака MITM является основной причиной того, почему двойной DES не используется и почему ключ тройного DES (168-битный) может быть взломан злоумышленником с 2 56 пробелами и 2 112 операциями.
Описание
При попытке повысить безопасность блочного шифра возникает соблазнительная идея - зашифровать данные несколько раз с использованием нескольких ключей. Можно подумать, что это удваивает или даже n- кратно увеличивает безопасность схемы множественного шифрования, в зависимости от того, сколько раз данные шифруются, потому что исчерпывающий поиск по всем возможным комбинациям ключей (простой перебор) потребует 2 n · K попыток, если данные зашифрованы k- битными ключами n раз.
MITM - это обычная атака, которая ослабляет преимущества безопасности от использования нескольких шифров, сохраняя промежуточные значения из шифров или дешифрования и используя их для сокращения времени, необходимого для перебора ключей дешифрования. Это делает атаку Meet-in-the-Middle (MITM) типичной криптографической атакой на основе пространственно-временного компромисса .
Атака MITM пытается найти ключи, используя как диапазон (зашифрованный текст), так и домен (открытый текст) композиции нескольких функций (или блочных шифров), так что прямое отображение через первые функции такое же, как обратное отображение (обратное image) через последние функции, буквально встречающиеся в середине скомпонованной функции. Например, хотя Double DES шифрует данные двумя разными 56-битными ключами, Double DES можно взломать с помощью 2 57 операций шифрования и дешифрования.
Многомерный MITM (MD-MITM) использует комбинацию нескольких одновременных атак MITM, как описано выше, где встреча происходит в нескольких позициях в составной функции.
История
Диффи и Хеллман впервые предложили атаку "встречу посередине" на гипотетическое расширение блочного шифра в 1977 году. Их атака использовала пространственно-временной компромисс, чтобы взломать схему двойного шифрования всего за вдвое больше времени, необходимого для взлома единственного шифра. -схема шифрования.
В 2011 году Бо Чжу и Гуан Гун исследовали многомерную атаку «встречу посередине» и представили новые атаки на блочные шифры ГОСТ , KTANTAN и Hummingbird-2 .
Встреча посередине (1D-MITM)
Предположим, кто-то хочет атаковать схему шифрования со следующими характеристиками для данного открытого текста P и зашифрованного текста 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 , получаем следующую эквивалентность:
Атакующий может вычислить 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 57 операциями и 2 56 пространством, что делает его лишь небольшим улучшением по сравнению с DES. Тройной DES использует ключ «тройной длины» (168-бит) и также уязвим для атаки «встреча посередине» в 2 56 пространствах и 2 112 операциях, но считается безопасным из-за размера своего пространства ключей.
Алгоритм MITM
Вычислите следующее:
-
:
- и сохраним каждую вместе с соответствующими в наборе A
-
:
- и сравниваем каждую новую с множеством A
Когда обнаруживается совпадение, держать в качестве кандидата ключа пары в таблице T . Проверьте пары в T на новой паре, чтобы подтвердить достоверность. Если пара ключей не работает с этой новой парой, выполните MITM еще раз с новой парой .
Сложность MITM
Если размер ключа равен k , эта атака использует только 2 k +1 шифрования (и дешифрования) и память O (2 k ) для хранения результатов прямых вычислений в таблице поиска , в отличие от простой атаки, для которой требуется 2 2 · K шифров, но O (1) пробел.
Многомерный MITM (MD-MITM)
Хотя 1D-MITM может быть эффективным, была разработана более изощренная атака: многомерная атака встречей посередине , также сокращенно MD-MITM . Это предпочтительнее, если данные были зашифрованы с использованием более чем двух способов шифрования с разными ключами. Вместо того, чтобы встречаться посередине (одно место в последовательности), атака MD-MITM пытается достичь нескольких определенных промежуточных состояний, используя прямые и обратные вычисления в нескольких позициях шифра.
Предположим, что атака должна быть установлена на блочном шифре, где шифрование и дешифрование определены, как и раньше:
то есть открытый текст P зашифрован несколько раз с использованием повторения одного и того же блочного шифра
MD-MITM использовался для криптоанализа, среди многих, блочного шифра ГОСТ , где было показано, что 3D-MITM значительно снизил временную сложность для атаки на него.
Алгоритм MD-MITM
Вычислите следующее:
- и сохраните каждый вместе с соответствующим в наборе .
- и сохраните каждый вместе с соответствующим в наборе .
Для каждого возможного предположения о промежуточном состоянии вычислите следующее:
- и для каждого совпадения между этим и набором сохраняйте и в новом наборе .
- и сохраните каждый вместе с соответствующим в наборе .
- Для каждого возможного предположения о промежуточном состоянии вычислите следующее:
-
- и для каждого совпадения между этим и множеством проверьте также,
- он совпадает с и затем сохраняет комбинацию подключей вместе в новом наборе .
- Для каждого возможного предположения о промежуточном состоянии вычислите следующее:
- и для каждого совпадения между этим и набором также проверяйте, совпадает ли он с новым набором , сохраняется и в нем .
- и для каждого совпадения между этим и набором проверьте также
-
совпадает ли он с . Если это так, то: "
Используйте найденную комбинацию подключей на другой паре открытый текст / зашифрованный текст, чтобы проверить правильность ключа.
Обратите внимание на вложенный элемент в алгоритме. Предположение о каждом возможном значении s j выполняется для каждого предположения о предыдущем s j -1 . Это составляет элемент экспоненциальной сложности по отношению к общей временной сложности этой атаки MD-MITM.
Сложность МД-МИТМ
Временная сложность этой атаки без грубой силы ⋅ ⋅
Что касается сложности памяти, легко увидеть, что они намного меньше, чем первая построенная таблица значений-кандидатов: по мере увеличения i значения-кандидаты, содержащиеся в, должны удовлетворять большему количеству условий, поэтому меньшее количество кандидатов будет передано конечному адресату .
Тогда верхняя граница сложности памяти MD-MITM равна
где k обозначает длину всего ключа (вместе взятого).
Сложность данных зависит от вероятности того, что неверный ключ может пройти (получить ложное срабатывание), то есть , где l - промежуточное состояние в первой фазе MITM. Размер промежуточного состояния и размер блока часто совпадают! Учитывая также, сколько ключей осталось для тестирования после первой фазы MITM, это так .
Следовательно, после первой фазы MITM есть , где - размер блока.
Каждый раз, когда окончательное значение-кандидат ключей проверяется на новой паре открытого текста / зашифрованного текста, количество ключей, которые пройдут, будет умножаться на вероятность того, что ключ может пройти .
Часть тестирования методом перебора (проверка ключа-кандидата на новых парах, имеет временную сложность , очевидно, для увеличения кратности b в экспоненте, число стремится к нулю.
Заключение о сложности данных основано на аналогичных рассуждениях, ограниченных парами.
Ниже приведен конкретный пример того, как монтируется 2D-MITM:
Общий пример 2D-MITM
Это общее описание того, как 2D-MITM устанавливается на шифрование блочного шифра.
В двумерном MITM (2D-MITM) метод заключается в достижении 2 промежуточных состояний внутри множественного шифрования открытого текста. См. Рисунок ниже:
2D-MITM алгоритм
Вычислите следующее:
- и сохраним каждую вместе с соответствующими в наборе A
- и сохраните каждую вместе с соответствующими в наборе B.
Для каждого возможного предположения о промежуточном состоянии s между и вычислить следующее:
-
- и для каждого совпадения между этим и набором A сохраните и в новом наборе T.
-
- и для каждого совпадения между этим и набором B проверьте также, совпадает ли оно с T для
- если это так, то:
Используйте найденную комбинацию подключей на другой паре открытый текст / зашифрованный текст, чтобы проверить правильность ключа.
2D-MITM сложность
Временная сложность этой атаки без грубой силы составляет
где | ⋅ | обозначает длину.
Потребление основной памяти ограничено построением наборов A и B, где T намного меньше других.
Информацию о сложности данных см. В подразделе о сложности MD-MITM .
Смотрите также
- Атака на день рождения
- Беспроводная безопасность
- Криптография
- Атака встречи посередине из трех подмножеств
- Атака встречи посередине с частичным соответствием