Метод встречи посередине
Автор описания (разделы 1, 2.4, 2.7): А.В.Батарина
| Метод встречи посередине | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(\sqrt n\log(n)) }[/math] |
| Объём входных данных | [math]\displaystyle{ O(\log(n)) }[/math] |
| Объём выходных данных | [math]\displaystyle{ \log(n) }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ O(1) }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ O(n) }[/math] |
Свойства и структура алгоритма
Общее описание алгоритма
Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом [1]. Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.
В качестве примера шифра, поддающегося атаке "встреча посередине" можно привести криптоалгоритм 2DES, являющийся модификацией шифра DES. В 2DES открытый текст шифруется дважды алгоритмом DES на двух разных 56-битных ключах. Однако из-за атаки "встреча посередине" сложность перебора двойного ключа (112 бит) шифра 2DES составляет [math]\displaystyle{ 2^{57} }[/math] вместо ожидаемых [math]\displaystyle{ 2^{112} }[/math].
Математическое описание алгоритма
Исходные данные: открытый текст [math]\displaystyle{ x }[/math], шифртекст [math]\displaystyle{ y }[/math].
Алгоритм зашифрования — композиция двух преобразований: [math]\displaystyle{ T_1(x,k_1) }[/math] и [math]\displaystyle{ T_2(x,k_2) }[/math], т.е. [math]\displaystyle{ y=T_2(T_1(x,k_1),k_2) }[/math].
Алгоритм расшифрования: [math]\displaystyle{ y=T_1^{-1}(T_2^{-1}(x,k_2),k_1) }[/math].
Вычисляемые данные: ключи шифрования [math]\displaystyle{ k_1 \in K_1 }[/math], [math]\displaystyle{ k_2 \in K_2 }[/math], где [math]\displaystyle{ K_1, K_2 }[/math] — множества возможных ключей.
Трудоёмкость полного перебора всех возможных пар [math]\displaystyle{ k_1,k_2 }[/math] составляет в среднем [math]\displaystyle{ |K_1||K_2|/2 }[/math], а в худшем случае [math]\displaystyle{ |K_1||K_2| }[/math]. Однако используя дополнительную память, можно сократить перебор.
Предположим, что открытый текст [math]\displaystyle{ x }[/math] и шифртекст [math]\displaystyle{ y }[/math] однозначно определяют ключи [math]\displaystyle{ k_1,k_2 }[/math]. Составим две таблицы:
[math]\displaystyle{ \begin{align} z_1 & =T_1(x,k_1^1) & z_1^′ &=T_2^{-1}(x,k_2^1)\\ z_2 & =T_1(x,k_1^2) & z_2^′ & =T_2^{-1}(x,k_2^2)\\ & ......... & & ......... \\ z_{|K_1|} & =T_1(x,k_1^{|K_1|}) & z_{|K_1|}^′ & =T_2^{-1}(x,k_2^{|K_1|}) \end{align} }[/math]
Для всех [math]\displaystyle{ k_1^i \in K_1 }[/math], [math]\displaystyle{ k_2^j \in K_2 }[/math]. Далее таблицы объединяются и сортируются по значениям [math]\displaystyle{ z_i,z_j^′ }[/math]. Индексы [math]\displaystyle{ i,j }[/math], при которых [math]\displaystyle{ z_i=z_j^′ }[/math], однозначно определяют искомую пару ключей [math]\displaystyle{ k_1=k_1^i,k_2=k_2^j }[/math]. Для нахождения такой пары достаточно просмотреть отсортированную таблицу один раз.
Если же пара открытый текст/шифртекст определяет ключ не единственном образом, то выходом алгоритма будет некоторое множество пар [math]\displaystyle{ k_1,k_2 }[/math], одна из которых является истинным ключом. Для выбора истинного ключа достаточно проверить ключи из полученного множества на других парах открытый текст/шифртекст.
Оптимизации
1. От генерации второй таблицы со значениями [math]\displaystyle{ z_j^′ }[/math] можно отказаться, перебирая ключи [math]\displaystyle{ k_2^j }[/math] до того момента, когда значение [math]\displaystyle{ z_j^′ }[/math] совпадёт с одним из значений [math]\displaystyle{ z_i }[/math]. В таком случае опробование ключей [math]\displaystyle{ k_2^j }[/math] в среднем сократится вдвое. Также вдвое сократится объём используемой памяти. Для нахождения совпадающего значения в отсортированном массиве можно применить бинарный поиск.
2. Вместо сортировки таблицы со значениями [math]\displaystyle{ z_i }[/math] и последующего бинарного поиска можно использовать хэш-таблицу.
Вычислительное ядро алгоритма
В случае использования хэш-таблицы достаточно большого размера основную сложность алгоритма составляет опробование ключей [math]\displaystyle{ k_1,k_2 }[/math]. Одним из самых трудоёмких шагов также оказывается сортировка таблицы.
Макроструктура алгоритма
Как видно из описания, атака "встреча посередине" использует (или может использовать в качестве оптимизации) следующие алгоритмы:
1. Алгоритм зашифрования/расшифрования
2. Алгоритм сортировки
3. Алгоритмы поиска, вставки в хэш-таблицу
Схема реализации последовательного алгоритма
Далее приводится последовательность действий для варианта алгоритма с генерацией одной таблицы значений [math]\displaystyle{ z_i }[/math].
1. Вычислить таблицу [math]\displaystyle{ z_i }[/math], записывая значения в порядке вычисления или используя хэш-таблицу
2. В случае записи значений в порядке вычисления отсортировать массив
3. Опробовать ключи [math]\displaystyle{ k_2^j }[/math], выполняя поиск совпадения с таблицей значений [math]\displaystyle{ z_j^′ }[/math]. Для нахождения совпадения использовать поиск по хэш-таблице (если она есть) или бинарный поиск
Последовательная сложность алгоритма
Всюду далее считаем, что алгоритм не прекращает работу при нахождении первого совпадения, а ищет все совпадения.
1. Сложность вычисления таблиц значений [math]\displaystyle{ z_i,z_j^′ }[/math] составит [math]\displaystyle{ O(|K_1|+|K_2|) }[/math] операций опробования
2. Объединение таблиц и их сортировка будет иметь сложность [math]\displaystyle{ O((|K_1|+|K_2|)\log(|K_1|+|K_2|)) }[/math] (например, при сортировке слиянием).
3. Сложность бинарного поиска в отсортированном массиве — [math]\displaystyle{ O(\log_2(|K_1|)) }[/math] для каждого поиска
4. Сложность поиска в достаточно большой хэш-таблице составит [math]\displaystyle{ O(1) }[/math] для каждого поиска
Итого: асимптотическая сложность алгоритма:
1. С генерацией двух таблиц — [math]\displaystyle{ 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]
2. C генерацией одной таблицы, сортировкой и бинарным поиском — [math]\displaystyle{ O(|K_1|) + O((|K_1|)\log(|K_1|)) + O(|K_2|\log_2(|K_1|))=O(\max(|K_1|,|K_2|)\log(|K_1|)) }[/math]
3. C генерацией одной (достаточно большой) хэш-таблицы — [math]\displaystyle{ O(|K_1|) + O(|K_2|)=O(|K_1|+|K_2|) }[/math]
Пусть [math]\displaystyle{ n }[/math] - количество всевозможных пар [math]\displaystyle{ k_1,k_2 }[/math] и пусть [math]\displaystyle{ |K_1|=|K_2| }[/math]. В этом случае [math]\displaystyle{ |K_1|=|K_2|=\sqrt n }[/math].
Тогда сложность алгоритма в первых двух пунктах составляет [math]\displaystyle{ O(\sqrt n\log(n)) }[/math], в третьем — [math]\displaystyle{ O(\sqrt n) }[/math].
Информационный граф
Опишем информационный граф алгоритма. На вход подаётся открытый (Open) и закрытый (Close), т.е. зашифрованный, текст. Далее открытый текст шифруется (Enc) на ключах [math]\displaystyle{ k_1^i }[/math], а зашифрованный расшифровывается (Dec) на ключах [math]\displaystyle{ k_2^j }[/math]. Далее полученные криптограммы сравниваются (Cmp) и все ключи, на которых они совпали, являются выходом алгоритма.
Ресурс параллелизма алгоритма
Как видно из информационного графа, для реализации атаки "встреча посередине" в параллельном варианте потребуются выполнение следующих двух ярусов (в предположении, что [math]\displaystyle{ |K_1|=|K_2| }[/math]):
1. [math]\displaystyle{ \sqrt n }[/math] зашифрований и столько же расшифрований
2. [math]\displaystyle{ n }[/math] сравнений
Таким образом, высота ЯПФ составляет 2, ширина - [math]\displaystyle{ n }[/math].
Входные и выходные данные алгоритма
Вход: На вход подаётся открытый текст [math]\displaystyle{ x }[/math] и шифртекст [math]\displaystyle{ y }[/math], а также алгоритм зашифрования/расшифрования. В случае блочного шифра открытым текстом и шифртекстом является последовательность блоков. Для атаки "встреча посередине", как правило, берётся один блок для максимального ускорения операций зашифрования и расшифрования.
Выход: Результатом работы алгоритма является множество пар [math]\displaystyle{ k_1^i,k_2^j }[/math], для которых нашлись совпадения. Только одна из пар является настоящим ключом. Чтобы отсеять лишние, необходимо проверить все пары на блоках открытого и шифрованного текста, которые в алгоритме не использовались.
Свойства алгоритма
Соотношением последовательной и параллельной сложности алгоритма является [math]\displaystyle{ O(\sqrt n\log(n)) }[/math].
Будем считать, что размер входных данных (открытый текст и шифртекст) совпадает с размером ключа (на практике это сравнимые величины), а сортировка слиянием делит массивы пополам. Тогда вычислительная мощность алгоритма — [math]\displaystyle{ O(\sqrt n) }[/math].
Дуги информационного графа, исходящие из вершин зашифрования и расшифрования, образуют пучки мощности [math]\displaystyle{ \sqrt n }[/math], т.е. из каждой такой вершины выходит [math]\displaystyle{ \sqrt n }[/math] дуг. Длинных дуг в алгоритме нет. В случае поиска всех пар ключей с совпадающими криптограммами алгоритм полностью детерминирован.
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Исследование масштабируемости реализации алгоритма проводилось на суперкомпьютере "Ломоносов"[2] Суперкомпьютерного комплекса Московского университета. Изменяемые параметры запуска:
- Размер ключа – от 8 до 20 бит с шагом 1
- Число ядер – от 1 до 8 (значения являются степенью числа 2)
Ниже представлен график зависимости производительности от числа ядер и размера ключа (размер задачи – экспоненциальная функция от размера ключа). Для измерения производительности в качестве базовой операции используется операция опробования ключа и время в секундах. Количество арифметических операций, содержащихся в операции опробования, может быть разным в зависимости от используемого алгоритма шифрования.
Как видно из графика, производительность почти не изменяется в зависимости от размера задачи и возрастает в зависимости от числа ядер. Росту производительности способствует то, что алгоритм содержит большое количество независимых операций опробования ключа, синхронизация между параллельно выполняющимися опробованиями не требуется.
Исследованная параллельная реализация на языке C
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Одна из реализаций атаки "встреча посередине" с использованием хэш-таблицы представлена в свободном доступе по ссылке github
В свободном доступе существуют коды для метода "встречи посередине" с использованием шифрования Blowfish и хэш-таблиц на C, а также с использованием шифрования 2DES на питоне.
Литература
<references \>
- ↑ (June 1977) «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer 10 (6): 74–84. DOI:10.1109/C-M.1977.217750
- ↑ Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.