Метод встречи посередине

Автор описания (разделы 1, 2.4, 2.7): А.В.Батарина

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

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

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

Криптоанализом назвают науку восстановления (дешифрования) открытого (нешифрованного) текста без доступа к ключу. Попытка криптоанализа называется "атакой".

Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом . Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.

В качестве примера шифра, поддающегося атаке "встреча посередине" можно привести криптоалгоритм 2DES, являющийся модификацией шифра DES. В 2DES открытый текст шифруется дважды алгоритмом DES на двух разных 56-битных ключах. Однако из-за атаки "встреча посередине" сложность перебора двойного ключа (112 бит) шифра 2DES составляет $2^{57}$ вместо ожидаемых $2^{112}$.

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

Исходные данные: открытый текст $x$, шифртекст $y$.

Алгоритм зашифрования — композиция двух преобразований: $T_1(x,k_1)$ и $T_2(x,k_2)$, т.е. $y=T_2(T_1(x,k_1),k_2)$.

Алгоритм расшифрования: $y=T_1^{-1}(T_2^{-1}(x,k_2),k_1)$.

Вычисляемые данные: ключи шифрования $k_1 \in K_1$, $k_2 \in K_2$, где $K_1, K_2$ — множества возможных ключей.

Трудоёмкость полного перебора всех возможных пар $k_1,k_2$ составляет в среднем $|K_1||K_2|/2$, а в худшем случае $|K_1||K_2|$. Однако используя дополнительную память, можно сократить перебор.

Предположим, что открытый текст $x$ и шифртекст $y$ однозначно определяют ключи $k_1,k_2$. Составим две таблицы:

$\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}$

Для всех $k_1^i \in K_1$, $k_2^j \in K_2$. Далее таблицы объединяются и сортируются по значениям $z_i,z_j^′$. Индексы $i,j$, при которых $z_i=z_j^′$, однозначно определяют искомую пару ключей $k_1=k_1^i,k_2=k_2^j$. Для нахождения такой пары достаточно просмотреть отсортированную таблицу один раз.

Если же пара открытый текст/шифртекст определяет ключ не единственном образом, то выходом алгоритма будет некоторое множество пар $k_1,k_2$, одна из которых является истинным ключом. Для выбора истинного ключа достаточно проверить ключи из полученного множества на других парах открытый текст/шифртекст.

1.2.1 Оптимизации

1. От генерации второй таблицы со значениями $z_j^′$ можно отказаться, перебирая ключи $k_2^j$ до того момента, когда значение $z_j^′$ совпадёт с одним из значений $z_i$. В таком случае опробование ключей $k_2^j$ в среднем сократится вдвое. Также вдвое сократится объём используемой памяти. Для нахождения совпадающего значения в отсортированном массиве можно применить бинарный поиск.

2. Вместо сортировки таблицы со значениями $z_i$ и последующего бинарного поиска можно использовать хэш-таблицу.

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

В случае использования хэш-таблицы достаточно большого размера основную сложность алгоритма составляет опробование ключей $k_1,k_2$. Одним из самых трудоёмких шагов также оказывается сортировка таблицы.

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

Как видно из описания, атака "встреча посередине" использует (или может использовать в качестве оптимизации) следующие алгоритмы:

1. Алгоритм зашифрования/расшифрования

2. Алгоритм сортировки

3. Алгоритмы поиска, вставки в хэш-таблицу

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

Далее приводится последовательность действий для варианта алгоритма с генерацией одной таблицы значений $z_i$.

1. Вычислить таблицу $z_i$, записывая значения в порядке вычисления или используя хэш-таблицу

2. В случае записи значений в порядке вычисления отсортировать массив

3. Опробовать ключи $k_2^j$, выполняя поиск совпадения с таблицей значений $z_j^′$. Для нахождения совпадения использовать поиск по хэш-таблице (если она есть) или бинарный поиск

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

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

1. Сложность вычисления таблиц значений $z_i,z_j^′$ составит $O(|K_1|+|K_2|)$ операций опробования

2. Объединение таблиц и их сортировка будет иметь сложность $O((|K_1|+|K_2|)\log(|K_1|+|K_2|))$ (например, при сортировке слиянием).

3. Сложность бинарного поиска в отсортированном массиве — $O(\log_2(|K_1|))$ для каждого поиска

4. Сложность поиска в достаточно большой хэш-таблице составит $O(1)$ для каждого поиска

Итого: асимптотическая сложность алгоритма:

1. С генерацией двух таблиц — $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|))$

2. C генерацией одной таблицы, сортировкой и бинарным поиском — $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|))$

3. C генерацией одной (достаточно большой) хэш-таблицы — $O(|K_1|) + O(|K_2|)=O(|K_1|+|K_2|)$

Пусть $n$ - количество всевозможных пар $k_1,k_2$ и пусть $|K_1|=|K_2|$. В этом случае $|K_1|=|K_2|=\sqrt n$.

Тогда сложность алгоритма в первых двух пунктах составляет $O(\sqrt n\log(n))$, в третьем — $O(\sqrt n)$.

1.7 Информационный граф

Опишем информационный граф алгоритма. На вход подаётся открытый (Open) и закрытый (Close), т.е. зашифрованный, текст. Далее открытый текст шифруется (Enc) на ключах $k_1^i$, а зашифрованный расшифровывается (Dec) на ключах $k_2^j$. Далее полученные криптограммы сравниваются (Cmp) и все ключи, на которых они совпали, являются выходом алгоритма.

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

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

Как видно из информационного графа, для реализации атаки "встреча посередине" в параллельном варианте потребуются выполнение следующих двух ярусов (в предположении, что $|K_1|=|K_2|$):

1. $\sqrt n$ зашифрований и столько же расшифрований

2. $n$ сравнений

Таким образом, высота ЯПФ составляет 2, ширина - $n$.

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

Вход: На вход подаётся открытый текст $x$ и шифртекст $y$, а также алгоритм зашифрования/расшифрования. В случае блочного шифра открытым текстом и шифртекстом является последовательность блоков. Для атаки "встреча посередине", как правило, берётся один блок для максимального ускорения операций зашифрования и расшифрования.

Выход: Результатом работы алгоритма является множество пар $k_1^i,k_2^j$, для которых нашлись совпадения. Только одна из пар является настоящим ключом. Чтобы отсеять лишние, необходимо проверить все пары на блоках открытого и шифрованного текста, которые в алгоритме не использовались.

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

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

Будем считать, что размер входных данных (открытый текст и шифртекст) совпадает с размером ключа (на практике это сравнимые величины), а сортировка слиянием делит массивы пополам. Тогда вычислительная мощность алгоритма — $O(\sqrt n)$.

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