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

Эта работа прошла предварительную проверку Дата последней правки страницы: 14.11.2016 Данная работа соответствует формальным критериям. Проверено Sleo.

Метод встречи посередине
Последовательный алгоритм
Последовательная сложность	[math]O(\sqrt n\log n)[/math]
Объём входных данных	[math]O(1)[/math]
Объём выходных данных	[math]O(1)[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]2[/math]
Ширина ярусно-параллельной формы	[math]n[/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], получаемых одинарным шифрованием открытого текста [math]p[/math] по всем возможным ключам первой итерации.
2. Находим множество всех шифртекстов [math]Z[/math], получаемых одинарным дешифрованием шифрованного текста [math]c[/math] по всем возможным ключам второй итерации.
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.7 Информационный граф

Опишем информационный граф алгоритма.

На вход подаётся открытый и шифрованный тексты. После открытый текст шифруется (Enc) по всем ключам [math]k_1[/math], а дешифрованный дешифруется (Dec) по всем ключам [math]k_2[/math]. Далее полученные тексты сравниваются между собой (Cmp) и все ключи, на которых они совпали, являются выходами алгоритма.

Рисунок 1. Граф алгоритма c отображением входных и выходных данных. Plaintext — открытый текст, ciphertext — шифрованный текст, Enc — операция шифрования, Dec — операция дешифрования, Cmp — операция сравнения, Key — полученный ключ

1.8 Ресурс параллелизма алгоритма

Как видно из информационного графа, для реализации метода в параллельном варианте потребуется выполнение следующих двух ярусов ярусно-параллельной формы (ЯПФ):

1. [math]2* \sqrt{n}[/math] шифрований/дешифрований
2. [math]n[/math] сравнений

То есть, высота ЯПФ составляет [math]2[/math], ширина – [math]n[/math] (т.к. [math]n\gt 2* \sqrt n[/math]).

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

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

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

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

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

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

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

1.10 Свойства алгоритма

Соотношение последовательной и параллельной сложности для данного метода равно [math]O(\sqrt n\log n)[/math].

При этом вычислительная мощность алгоритма, равная отношению числа операций к суммарному объему входных и выходных данных, составляет [math]O(\sqrt{n})[/math].

Алгоритм полностью детерминирован при условии корректности данных.

Дуги информационного графа, исходящие из вершин, соответствующих операциям шифрования/дешифрования, образуют пучки мощности [math]\sqrt{n}[/math].

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

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

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

3 Литература

• Метод встречи посередине
• Meet-in-the-middle attack

Сноски: