Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) ( Узнайте, как и когда удалить этот шаблон сообщения )
|
Встречаются в-середины атака ( MITM ), известная открытый текст атака, [1] является универсальным пространственно-временный компромисс криптографической атакой против схем шифрования , которые полагаются на выполнение нескольких операций шифрования в последовательности. Атака MITM является основной причиной того, почему двойной DES не используется и почему ключ тройного DES (168-битный) может быть взломан злоумышленником с использованием 2 56 пробелов и 2 112 операций. [2] [3]
Описание [ править ]
При попытке повысить безопасность блочного шифра возникает соблазнительная идея - зашифровать данные несколько раз с использованием нескольких ключей. Можно подумать, что это удваивает или даже 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 году. [4] Их атака использовала пространственно-временной компромисс, чтобы взломать схему двойного шифрования всего за вдвое больше времени, необходимого для нарушить схему однократного шифрования.
В 2011 году Бо Чжу и Гуан Гун исследовали многомерную атаку "встречу посередине" и представили новые атаки на блочные шифры ГОСТ , KTANTAN и Hummingbird-2 . [5]
Встреча посередине (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. [6] Triple DES использует ключ «тройной длины» (168-бит) и также уязвим для атаки « встречная середина» в 2 56 пространствах и 2 112 операциях, но считается безопасным из-за размера своего пространство клавиш. [2] [3]
Алгоритм MITM [ править ]
Вычислите следующее:
- :
- и сохраним каждую вместе с соответствующими в наборе A
- :
- и сравниваем каждую новую с множеством A
Когда найдено совпадение, сохранить K F 1 , K б 1 в качестве кандидата ключа пары в таблице Т . Проверьте пары в T на новой паре, чтобы подтвердить достоверность. Если пара ключей не работает с этой новой парой, выполните MITM еще раз с новой парой .
Сложность MITM [ править ]
Если размер ключа равен k , эта атака использует только 2 k +1 шифрования (и дешифрования) и O (2 k ) памяти для хранения результатов прямых вычислений в таблице поиска , в отличие от простой атаки, которая требует 2 2 · K шифров, но O (1) пробел.
Многомерный MITM (MD-MITM) [ править ]
Этот раздел, возможно, содержит оригинальные исследования . Май 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( |
Хотя 1D-MITM может быть эффективным, была разработана более изощренная атака: многомерная атака встречей посередине , также сокращенно MD-MITM . Это предпочтительнее, если данные были зашифрованы с использованием более двух способов шифрования с разными ключами. Вместо того, чтобы встречаться посередине (одно место в последовательности), атака MD-MITM пытается достичь нескольких определенных промежуточных состояний, используя прямые и обратные вычисления в нескольких позициях в шифре. [5]
Предположим, что атака должна быть установлена на блочном шифре, где шифрование и дешифрование определены, как и раньше:
то есть открытый текст P зашифрован несколько раз с использованием повторения одного и того же блочного шифра
MD-MITM использовался для криптоанализа, среди многих, блочного шифра ГОСТ , где было показано, что 3D-MITM значительно снизил временную сложность для атаки на него. [5]
Алгоритм MD-MITM [ править ]
В этом разделе не процитировать любые источники . Май 2015 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( |
Вычислите следующее:
- и сохраните каждый вместе с соответствующим в наборе .
- и сохраните каждый вместе с соответствующим в наборе .
Для каждого возможного предположения о промежуточном состоянии вычислите следующее:
- и для каждого совпадения между этим и набором сохраняйте и в новом наборе .
- [ требуется проверка ]
- и сохраните каждый вместе с соответствующим в наборе .
- Для каждого возможного предположения о промежуточном состоянии вычислите следующее:
- и для каждого совпадения между этим и множеством проверьте также,
- он совпадает с и затем сохраняет комбинацию подключей вместе в новом наборе .
- Для каждого возможного предположения о промежуточном состоянии вычислите следующее:
- и для каждого совпадения между этим и набором также проверяйте, совпадает ли он с новым набором , сохраняется и в нем .
- и для каждого совпадения между этим и набором проверьте также
совпадает ли он с . Если это так, то: "
Используйте найденную комбинацию подключей на другой паре открытый текст / зашифрованный текст, чтобы проверить правильность ключа.
Обратите внимание на вложенный элемент в алгоритме. Предположение о каждом возможном значении s j выполняется для каждого предположения о предыдущем s j -1 . Это составляет элемент экспоненциальной сложности по отношению к общей временной сложности этой атаки MD-MITM.
Сложность 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 .
См. Также [ править ]
- Атака на день рождения
- Беспроводная безопасность
- Криптография
- Атака встречи посередине из трех подмножеств
- Атака встречи посередине с частичным соответствием
Ссылки [ править ]
- ^ http://www.crypto-it.net/eng/attacks/meet-in-the-middle.html
- ^ a b Мур, Стефан (16 ноября 2010 г.). «Атаки на встречу посередине» (PDF) : 2. Cite journal requires
|journal=
(help) - ^ a b Блондо, Селин. «Лекция 3: Блочные шифры» (PDF) . CS-E4320 Криптография и безопасность данных .
- ^ ^ Диффи, Уитфилд; Хеллман, Мартин Э. (июнь 1977 г.). «Исчерпывающий криптоанализ стандарта шифрования данных NBS» (PDF) . Компьютер . 10 (6): 74–84. DOI : 10.1109 / CM.1977.217750 . S2CID 2412454 .
- ^ а б в Чжу, Бо; Гуан Гун (2011). «Атака MD-MITM и ее приложения к ГОСТ, КТАНТАН и Колибри-2» . eCrypt .
- ^ Чжу, Бо; Гуан Гун (2011). «Атака MD-MITM и ее приложения к ГОСТ, КТАНТАН и Колибри-2». eCrypt .