Метод встречи посередине в криптоанализе

Привет, Вы узнаете о том , что такое метод встречи посередине в криптоанализе, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое метод встречи посередине в криптоанализе , настоятельно рекомендую прочитать все из категории Криптоанализ, Виды уязвимости и защита Информации .

В криптоанализе методом встречи посередине или атакой "встречи посередине" (англ. meet-in-the-middle attack) называется класс атак на криптографическиеалгоритмы, асимптотически уменьшающих время полного перебора за счет принципа "разделяй и властвуй", а также увеличения объема требуемой памяти. Впервые данный метод был предложен Уитфилдом Диффи и Мартином Хеллманом в 1977 году. 

 

Начальные условия 

Даны открытый (незашифрованный) и шифрованный тексты. Криптосистема состоит из h циклов шифрования. Цикловые ключи независимы и не имеют общих битов. Ключ K системы представляет собой сочетание из h-цикловых ключей k1, k2 ... kh. Задача состоит в нахождении ключа K.

Решение простого случая 

Простым примером является двойное последовательное шифрование блочным алгоритмом двумя различными ключами {\displaystyle K_{1}} и  . Процесс шифрования выглядит так:

 ,

где   — это открытый текст,   — шифртекст, а   — операция однократного шифрования ключом  . Соответственно, обратная операция — расшифрование — выглядит так:

 

На первый взгляд кажется, что применение двойного шифрования многократно увеличивает стойкость всей схемы, поскольку перебирать теперь нужно два ключа, а не один. Об этом говорит сайт https://intellect.icu . В случае алгорима DES стойкость увеличивается с 2⁵⁶ до 2¹¹². Однако это не так. Атакующий может составить две таблицы:

1. Все значения   для всех возможных значений  ,
2. Все значения   для всех возможных значений  .

Затем ему достаточно лишь найти совпадения в этих таблицах, т.е. такие значения   и  , что   . Каждое совпадение соответствует набору ключей  , который удовлетворяет условию.

Для данной атаки потребовалось 2⁵⁷ операций шифрования-расшифрования (лишь в два раза больше, чем для перебора одного ключа) и 2⁵⁷ памяти. Дополнительные оптимизации — использование хэш-таблиц, вычисления только для половины ключей (для DES полный перебор, на самом деле, требует лишь 2⁵⁵ операций) — могут снизить эти требования. Главный результат атаки состоит в том, что последовательное шифрование двумя ключами увеличивает время перебора лишь в два раза.

Решение в общем виде 

Обозначим преобразование алгоритма как Ek(a)=b, где a-открытый текст, а b-шифротекст. Его можно представить как композицию Ek1Ek2..Ekh(a)=b, где Eki — цикловое преобразование на ключе ki. Каждый ключ ki представляет собой двоичный вектор длины n, а общий ключ системы — вектор длины n*h.

1. Заполнение памяти.

Перебираются все значения k'=(k1,k2..kr), т.е первые r цикловых ключей. На каждом таком ключе k' зашифровываем открытый текст a - Ek' (a)=Ek1Ek2..Ekr(a)=S (т.е. проходим r циклов шифрования вместо h). Будем считать S неким адресом памяти и по этому адресу запишем значение k'. Необходимо перебрать все значения k'.

2. Определение ключа.

Перебираются все возможные k"=(kr+1,kr+2...kh). На получаемых ключах расшифровывается шифротекст b - E-1k"(b)=E-1kh..E-1kr+1(b)=S' . Если по адресу S' не пусто, то достаем оттуда ключ k' и получаем кандидат в ключи (k',k")=k.

Однако нужно заметить, что первый же полученный кандидат k не обязательно является истинным ключом. Да, для данных a и b выполняется Ek(a)=b, но на других значениях открытого текста a' шифротекста b', полученного из a' на истинном ключе, равенство может нарушаться. Все зависит от конкретных характеристик криптосистемы. Но иногда бывает достаточно получить такой "псевдоэквивалентный" ключ. В противном же случае после завершения процедур будет получено некое множество ключей {k',k"...}, среди которых находится истинный ключ.

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

 

Примечания.

 

Если множество ключей криптоалгоритма замкнуто относительно композиции, то есть для любых ключей z i и z j найдется ключ zk такой,что результат шифрования любого текста последовательно на z i и z j равен шифрограмме этого же числа на zk , то есть F(z j ,F(z i , x))= F(z k , x), то можно воспользоваться этим свойством. Пусть нам нужно найти ключ zk. Тогда для нахождения ключа zk, необходимо найти эквивалентную ему пару ключей zi , zj. Данный метод криптоанализа основан на "парадоксе дней рождения". Известно, что если считать, что дни рождения распределены равномерно, то в группе из 24 человек с вероятностью 0,5 у двух человек дни рождения совпадут.В общем виде этот парадокс формулируется так: если a Ц n предметов выбираются с возвращением из некоторой совокупности размером n, то вероятность того что два из них совпадут, равна 1-exp(-a2 / 2) 

Пусть известен открытый текст x и его шифрограмма y. Для текста x строим базу данных, содержащую случайное множество ключей z| и соответствующих шифрограмм w=F(z| , x), и упорядочиваем ее по шифрограммам w. Объем базы данных выбираем О( Ц # {z} ). Затем подбираем случайным образом ключи z| | для расшифровки текстов y и результат расшифровани v = F(z| | , y) сравниваем с базой данных. Если текст v окажется равным одной из шифрограмм w, то ключ z| z| | эквивалентен искомому ключу z. Временная сложность метода составляет О( Ц # {z} log#{z}). Множитель log#{z} учитывает сложность сортировки. Требуемая память равна О( Ц # {z} log#{z}) бит или ОЦ # {z}) блоков ( предполагается, что длина блока и длина ключа различаются на ограниченную константу ). 

Этот же метод применим, если множество ключей содержит достаточно большое подмножество, являющееся полугруппой. 

Другое применение этого метода для множества, не являющегося полугруппой, можно продемонстрировать на хэш-функциях. Например, для подделки подписи надо найти два текста, обладающих одним хэш-образом. После этого можно подписанное сообщение заменить на другое, обладающее таким же хэш-образом. Поиск двух таких сообщений можно выполнить с использованием метода "встречи посередине". Сложность поиска равна О(Ц #{h}), где #{h} - число всевозможных хэш-образов 

 

Этот алгоритм является вероятностным. Однако существуют и детерминированный аналог этого алгоритма "giant step - baby step" с такой же сложностью, предложенный американским математиком Д.Шенксом

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

Из статьи мы узнали кратко, но содержательно про метод встречи посередине в криптоанализе