Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Meet-in-the-middle attack, многомерная MITM

Лекция



Сразу хочу сказать, что здесь никакой воды про meet in the middle attack, и только нужная информация. Для того чтобы лучше понимать что такое meet in the middle attack, ключа , многомерная mitm , настоятельно рекомендую прочитать все из категории Криптоанализ, Виды уязвимости и защита Информации .

Атака посредника, или атака «человек посередине» (MITM) Meet-in-the-Middle attack (MITM) является общим пространственно-временным компромиссом криптографической атаки.

Описание

MITM - это универсальная атака, применимая к нескольким криптографическим системам. Следовательно, внутренняя структура конкретной системы не важна для этой атаки.

Злоумышленнику требуется способность шифровать и дешифровать, а также владение парами открытых текстов и соответствующих зашифрованных текстов.

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

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

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

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

История

Впервые он был разработан как атака на попытку расширения блочного шифра Диффи и Хеллманом в 1977 году.

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

В 2011 году Бо Чжу и Гуан Гун исследовали многомерную атаку Meet-in-the-Middle и представили новые атаки на блочные шифры GOST, KTANTAN и Hummingbird-2.

MITM (1D-MITM)

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

Meet-in-the-middle attack, многомерная MITM

Meet-in-the-middle attack, многомерная MITM

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

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

Эта атака является одной из причин, по которой DES был заменен тройным DES - «двойной DES» не обеспечивает дополнительной защиты от исчерпывающего поиска ключей для злоумышленника с 2 56 пробелами. Однако тройной DES с ключом «тройной длины» (168-бит) уязвим для атаки «встреча посередине» в 2 56 пространствах и 2 112 операциях.

Meet-in-the-middle attack, многомерная MITM
Иллюстрация атаки 1D-MITM

Как только совпадения обнаружены, их можно проверить с помощью второго набора тестов, состоящего из открытого текста и зашифрованного текста.

Алгоритм MITM

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

  • Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM :

и сохраним каждую Meet-in-the-middle attack, многомерная MITM вместе с соответствующими Meet-in-the-middle attack, многомерная MITM в наборе A

  • Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM :

и сравниваем каждую новую Meet-in-the-middle attack, многомерная MITM с множеством A

Когда найдено совпадение, сохранить K F 1 , K б 1 в качестве кандидата ключа пары в таблице Т . Проверьте пары в T на новой паре (P, C), чтобы подтвердить достоверность. Если пара ключей не работает с этой новой парой, выполните MITM еще раз с новой парой (P, C) .

Сложность MITM

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

Многомерный-MITM


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

Meet-in-the-middle attack, многомерная MITM
Meet-in-the-middle attack, многомерная MITM

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

Meet-in-the-middle attack, многомерная MITM
Иллюстрация атаки MD-MITM

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

Алгоритм MD-MITM

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

  • Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM :

и сохраните каждый Meet-in-the-middle attack, многомерная MITM вместе с соответствующим Meet-in-the-middle attack, многомерная MITM в наборе Meet-in-the-middle attack, многомерная MITM.

  • Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM :

и сохраните каждый Meet-in-the-middle attack, многомерная MITM вместе с соответствующим Meet-in-the-middle attack, многомерная MITM в наборе Meet-in-the-middle attack, многомерная MITM.

Для каждого возможного предположения о промежуточном состоянии Meet-in-the-middle attack, многомерная MITM вычислите следующее:

  • Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM :

и для каждого совпадения между этим Meet-in-the-middle attack, многомерная MITM и набором Meet-in-the-middle attack, многомерная MITMсохраняйте Meet-in-the-middle attack, многомерная MITM и Meet-in-the-middle attack, многомерная MITM в новом наборе Meet-in-the-middle attack, многомерная MITM.

  • Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM :

и сохраните каждый Meet-in-the-middle attack, многомерная MITM вместе с соответствующим Meet-in-the-middle attack, многомерная MITM в наборе Meet-in-the-middle attack, многомерная MITM.

Для каждого возможного предположения о промежуточном состоянии Meet-in-the-middle attack, многомерная MITM вычислите следующее:1 Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM

и для каждого совпадения между этим Meet-in-the-middle attack, многомерная MITM и множеством Meet-in-the-middle attack, многомерная MITMпроверьте также,

он совпадает с Meet-in-the-middle attack, многомерная MITM и затем сохраняет комбинацию подключей вместе в новом наборе Meet-in-the-middle attack, многомерная MITM.

2 ...

Для каждого возможного предположения о промежуточном состоянии Meet-in-the-middle attack, многомерная MITM вычислите следующее:а) Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM

и для каждого совпадения между этим Meet-in-the-middle attack, многомерная MITM и множеством Meet-in-the-middle attack, многомерная MITMпроверьте также,

он совпадает с Meet-in-the-middle attack, многомерная MITM, сохранить Meet-in-the-middle attack, многомерная MITM и Meet-in-the-middle attack, многомерная MITM в новом наборе

Meet-in-the-middle attack, многомерная MITM.

б) Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM

и для каждого совпадения между этим Meet-in-the-middle attack, многомерная MITM и набором Meet-in-the-middle attack, многомерная MITMпроверьте также

совпадает ли он с Meet-in-the-middle attack, многомерная MITM. Об этом говорит сайт https://intellect.icu . Об этом говорит сайт https://intellect.icu. Если это так, то: "

Используйте найденную комбинацию подключей Meet-in-the-middle attack, многомерная MITM на другой паре открытый текст / зашифрованный текст, чтобы проверить правильность ключа.

Обратите внимание на вложенный элемент в алгоритме. Предположение о каждом возможном значении s j выполняется для каждого предположения о предыдущем s j-1 . Это составляет элемент экспоненциальной сложности по отношению к общей временной сложности этой атаки MD-MITM.

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

Временная сложность этой атаки без грубой силы Meet-in-the-middle attack, многомерная MITM⋅ Meet-in-the-middle attack, многомерная MITM⋅Meet-in-the-middle attack, многомерная MITM

Что касается сложности памяти, легко увидеть, что Meet-in-the-middle attack, многомерная MITM они намного меньше, чем первая построенная таблица значений-кандидатов: по Meet-in-the-middle attack, многомерная MITM мере увеличения i значения-кандидаты, содержащиеся в, Meet-in-the-middle attack, многомерная MITM должны удовлетворять большему количеству условий, поэтому меньшее количество кандидатов будет передано конечному адресату Meet-in-the-middle attack, многомерная MITM.

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

Meet-in-the-middle attack, многомерная MITM

где Meet-in-the-middle attack, многомерная MITM обозначает длину всего ключа (вместе).

Сложность данных зависит от вероятности того, что неверный ключ может пройти (получить ложное срабатывание), то есть Meet-in-the-middle attack, многомерная MITM, где Meet-in-the-middle attack, многомерная MITM - промежуточное состояние в первой фазе MITM. Размер промежуточного состояния и размер блока часто совпадают! Учитывая также, сколько ключей осталось для тестирования после первой фазы MITM, это так Meet-in-the-middle attack, многомерная MITM.

Следовательно, после первой фазы MITM есть Meet-in-the-middle attack, многомерная MITM⋅ Meet-in-the-middle attack, многомерная MITM , где $ | b | $ - размер блока.

Каждый раз, когда окончательное значение-кандидат ключей проверяется на новой паре открытого текста / зашифрованного текста, количество ключей, которые будут переданы, будет умножаться на вероятность того, что ключ может пройти, что есть Meet-in-the-middle attack, многомерная MITM.

Часть тестирования методом перебора (проверка ключа кандидата на новых (P, C) парах, имеет временную сложность Meet-in-the-middle attack, многомерная MITM...

очевидно, что при увеличении степени, кратной b, число стремится к нулю.

Заключение о сложности данных Meet-in-the-middle attack, многомерная MITMосновано на аналогичных рассуждениях, ограниченных рассуждениями о ⌈ ⌉ (P, C) -парах.

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

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

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

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

Meet-in-the-middle attack, многомерная MITM
Иллюстрация атаки 2D-MITM

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

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

  • Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM

и сохраним каждую Meet-in-the-middle attack, многомерная MITM вместе с соответствующими Meet-in-the-middle attack, многомерная MITM в наборе A

  • Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM

и сохраните каждую Meet-in-the-middle attack, многомерная MITM вместе с соответствующими Meet-in-the-middle attack, многомерная MITM в наборе B.

Для каждого возможного предположения о промежуточном состоянии s между Meet-in-the-middle attack, многомерная MITM и Meet-in-the-middle attack, многомерная MITMвычислить следующее:

1 Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM

и для каждого совпадения между этим Meet-in-the-middle attack, многомерная MITM и набором A сохраните Meet-in-the-middle attack, многомерная MITM и Meet-in-the-middle attack, многомерная MITM в новом наборе T.

2 Meet-in-the-middle attack, многомерная MITM ∀ Meet-in-the-middle attack, многомерная MITM ∈ Meet-in-the-middle attack, многомерная MITM

и для каждого совпадения между этим Meet-in-the-middle attack, многомерная MITM и набором B проверьте также, совпадает ли оно с T для

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

Используйте найденную комбинацию подключей Meet-in-the-middle attack, многомерная MITM на другой паре открытый текст / зашифрованный текст, чтобы проверить правильность ключа.

2D-MITM сложность

Временная сложность этой атаки без грубой силы равна Meet-in-the-middle attack, многомерная MITM⋅, Meet-in-the-middle attack, многомерная MITM где | ⋅ | обозначает длину.

Потребление основной памяти ограничено построением наборов A и B, где T намного меньше остальных.

Информацию о сложности данных см. В подразделе о сложности MD-MITM.

Вау!! 😲 Ты еще не читал? Это зря!


А как ты думаешь, при улучшении meet in the middle attack, будет лучше нам? Надеюсь, что теперь ты понял что такое meet in the middle attack, ключа , многомерная mitm и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Криптоанализ, Виды уязвимости и защита Информации

создано: 2014-08-31
обновлено: 2021-04-20
132526

Рейтиг 9 of 10. count vote: 2
Вы довольны ?:

Поделиться:

Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Создать заявку
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Добавить решение
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей
Разместить резюме

Комментарии

Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Криптоанализ, Виды уязвимости и защита Информации

Термины: Криптоанализ, Виды уязвимости и защита Информации