Участник:Огнева Мария/Метод встречи посередине

Метод встречи посередине
Последовательный алгоритм
Последовательная сложность	[math]O(\sqrt n\log n)[/math]
Объём входных данных	[math]O(1)[/math]
Объём выходных данных	[math]O(1)[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O()[/math]
Ширина ярусно-параллельной формы	[math]O()[/math]

Основные авторы описания: М.С. Огнева

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

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

1.1.1 История

Алгоритм шифрования DES был принят в качестве стандарта в 1977 году. Длина ключа нового стандарта составляла 56 бит, довольно большое число по тем временам, но оставляла возможность полного перебора ([math]2^{56} [/math]). В 1977 Диффи и Хеллман предложили устройство, стоимостью примерно 20 млн. долларов, которое смогло бы найти ключ DES за один день. Поэтому появилась необходимость увеличить стойкость алгоритма DES, используя технику многократного шифрования. Этот способ позволяет искусственно увеличить длину ключа, применяя несколько раз операцию шифрования с разными ключами. Так для алгоритма 2DES (двойное шифрование) длина ключа равна 112 бит, то есть полный перебор становится бессмысленной затеей. В 1981 году Ральф Меркл и Мартин Хеллман подробно разбирают безопасность двойного шифрования и описывают метод встречи посередине, позволяющий восстановить ключ шифрования не за [math]2^{112}[/math] операций шифрования, а за относительно пустяковые [math]2^{57}[/math] за счет перебора не одного длинного ключа, а двух более коротких. Следующая модернизация DES - Triple DES с 168-битным ключом - требует от метода встречи посередине [math]2^{56} [/math] памяти и [math]2^{112}[/math] операций.

1.1.2 Особенности метода

1. Способ шифрования: симметричный.

   Для шифрования и расшифрования применяется один и тот же криптографический ключ.

2. Условия криптоанализа: атака на основе открытого текста.

   Известны открытый и шифрованный текст, алгоритм шифрования и дешифрования, необходимо найти ключ.

3. Метод криптоанализа: универсальный.

   С определенными вариациями метод применим ко многим шифрам.

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

1.1.3 Описание метода для алгоритма двойного шифрования

На данной странице будет рассмотрен более простой вариант - двойное шифрование (две итерации шифрования). Пусть [math]p, c[/math] – открытый (plaintext) и шифрованный текст (ciphertext) соответственно. Тогда сокращение полного перебора происходит следующим образом:

1. Находим множество всех шифртекстов [math]W[/math], получаемых одинарным шифрованием открытого текста p по всем возможным ключам первой итерации.
2. Находим множество всех шифртекстов [math]Z[/math], получаемых одинарным дешифрованием шифрованного текста c по всем возможным ключам второй итерации.
3. Если множества [math]W[/math] и [math]Z[/math] имеют непустое пересечение, то искомым ключом шифрования будет являться пара ключей, при помощи которых это пересечение было зашифровано из [math]p[/math] и дешифровано из [math]c[/math].

1.2 Математическое описание алгоритма

Пусть алгоритм шифрования описывается как [math]Enc(k, t) [/math], дешифрования [math]Dec(k, t) [/math], где [math]k[/math] – ключ, [math]t[/math] – текст. Тогда получаемый двойным шифрованием по ключам [math]k_1[/math] и [math]k_2[/math] шифрованный текст равен: [math]c = Enc(k_2, Enc(k_1, p))[/math]. Открытый текст получается из шифрованного двойным дешифрованием: [math]p=Dec(k_1, Dec(k_2, c))[/math].

Исходные данные: тексты [math]p, c[/math].

Вычисляемые данные: ключ [math]k=(k_1, k_2)[/math], где [math]k_1 \in K_1[/math], [math]k_2 \in K_2[/math]. Предположим для упрощения, что для известной пары [math](p, c)[/math] существует единственный ключ [math](k_1, k_2)[/math]. Составим таблицы [math]W[/math] и [math]Z[/math]:

• для всех [math]k^i_1 \in K_1[/math]: [math]w(k^i_1) = Enc (k^i_1, p)[/math]
• для всех [math]k^j_2 \in K_2[/math]: [math]z(k^j_2) = Dec (k^j_2, c)[/math]

Таблицы объединяются и сортируются по полученным промежуточным шифртекстам [math]z_i, w_j[/math]. Пара [math]z_i = w_j[/math], которую можно найти одиночным просмотром объединенной таблицы, определяет искомый ключ [math](k^i_1, k^j_2) [/math].

В более общем случае, может получиться не одна пара [math]z_i = w_j[/math]. Тогда необходимы еще пары [math](p, c)[/math] для определения истинного ключа.

1.3 Вычислительное ядро алгоритма

Основную сложность алгоритма составляет перебор ключей [math]k^i_1,k^j_2[/math], а так же сортировка полученных массивов [math]W[/math] и [math]Z[/math].

1.4 Макроструктура алгоритма

Метод использует в качестве составных частей следующие алгоритмы:

1. Алгоритм зашифрования/расшифрования
   • В качестве основных примем алгоритмы Blowfish и DES, сложность которых пропорциональна длине ключа. В связи с тем, что длина ключа не больше 64 бит, то будем считать, что эти алгоритмы выполняются за единицу времени.
2. Алгоритм сортировки
   • Будем считать, что используется быстрая сортировка или сортировка слиянием, которые в среднем работают за [math]O(n \log n)[/math].
3. Алгоритм поиска
   • Совпадающие значения матриц [math]W[/math] и [math]Z[/math] будем искать одиночным просмотром всей таблицы.

1.5 Схема реализации последовательного алгоритма

Последовательность действий метода:

1. Вычислить таблицы [math]W[/math] и [math]Z[/math], записывая значения в порядке вычисления и сохраняя соответствующие ключи для шифрования/дешифрования.
2. Отсортировать массив [math]W \cup Z[/math].
3. Найти совпадения в отсортированной таблице.

1.6 Последовательная сложность алгоритма

1. Сложность вычисления таблиц [math]W[/math] и [math]Z[/math] составит [math]O(|K_1|+|K_2|)[/math] операций.
2. Объединение таблиц и их сортировка будет иметь сложность: [math]O([|K_1|+|K_2|]\log[|K_1|+|K_2|])[/math].
3. Поиск совпадений: [math]O(|K_1|+|K_2|)[/math].

Общая сложность всего метода равна: [math]O(|K_1|+|K_2|) + O([|K_1|+|K_2|]\log[|K_1|+|K_2|]) + O(|K_1|+|K_2|)=O([|K_1|+|K_2|]\log[|K_1|+|K_2|])[/math]

Примем за [math]n[/math] количество всевозможных ключей [math]k= k_1,k_2[/math]. Если предположить, что [math]|K_1|=|K_2|[/math], то [math]|K_1|=|K_2|=\sqrt n[/math]. Тогда сложность метода составляет [math]O(\sqrt n\log n) [/math].

1.9 Входные и выходные данные алгоритма

Входные данные: открытый текст [math]p[/math] и шифрованный текст [math]y[/math],имеющие одинаковую длину.

Так как рассматриваемые шифры являются блочными, то равенство длины текста длине ключа не является обязательным, может быть больше. В данной ситуации тексты являются последовательностью блоков, а для шифрования/дешифрования берётся один блок текстов для максимального ускорения операций.

Примем, что длина ключей [math]k_1[/math] и [math]k_2[/math] равна 64 битам. То есть длина текста равна 64 битам или кратна этому числу.

Выходные данные: множество пар [math](k_1,k_2)[/math], для которых нашлись совпадения.

Лишние пары могли получиться при шифровании/дешифровании одного блока текстов. Тогда для получения истинного ключа необходимо проверить все пары на блоках открытого и шифрованного текста, которые в алгоритме не использовались.

Длина искомого ключа: 128 бит.

2 Программная реализация алгоритма

2.2 Существующие реализации алгоритма

Реализаций метода в виде библиотек не обнаружено. В свободном доступе существуют коды для метода встречи по середине с использованием шифрования Blowfish и хэш-таблиц на C, а также с использованием шифрования 2DES на питоне.