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

Особенности атаки

Данный метод применяется для атаки на блочные шифры. Обладает значительно меньшей трудоёмкостью по сравнению с методом полного перебора.

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

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

Задача

При известных открытом и шифрованном текстах найти ключ K.

Решение

Обозначим преобразование алгоритма как 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"...}, среди которых находится истинный ключ.

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