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

В криптоанализе методом встречи посередине или атакой «встречи посередине» (Шаблон:Lang-en) называется класс атак на криптографические алгоритмы, асимптотически уменьшающих время полного перебора за счет принципа «разделяй и властвуй», а также увеличения объема требуемой памяти. Впервые данный метод был предложен Уитфилдом Диффи и Мартином Хеллманом в 1977 году^[1].

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

Даны открытый (незашифрованный) и шифрованный тексты. Криптосистема состоит из $h$ циклов шифрования. Цикловые ключи независимы и не имеют общих битов. Ключ $K$ системы представляет собой сочетание из $h$ -цикловых ключей $k_{1}, k_{2} ... k_{h}$ . Задача состоит в нахождении ключа $K$ .

Решение простого случая

Простым примером является двойное последовательное шифрование блочным алгоритмом двумя различными ключами $K_{1}$ и $K_{2}$ . Процесс шифрования выглядит так:

$s = E N C_{K_{2}} (E N C_{K_{1}} (p))$ ,

где $p$ — это открытый текст, $s$ — шифротекст, а $E N C_{K_{i}} ()$ — операция однократного шифрования ключом $K_{i}$ . Соответственно, обратная операция — расшифрование — выглядит так:

$p = E N C_{K_{1}}^{- 1} (E N C_{K_{2}}^{- 1} (s))$

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

Все значения $m_{1} = E N C_{K_{1}} (p)$ для всех возможных значений $K_{1}$ ,
Все значения $m_{2} = E N C_{K_{2}}^{- 1} (s)$ для всех возможных значений $K_{2}$ .

Затем ему достаточно лишь найти совпадения в этих таблицах, то есть такие значения $m_{1}$ и $m_{2}$ , что $E N C_{K_{1}} (p) = E N C_{K_{2}}^{- 1} (s)$ . Каждое совпадение соответствует набору ключей $(K_{1}, K_{2})$ , который удовлетворяет условию.

Для данной атаки потребовалось $2^{57}$ операций шифрования-расшифрования (лишь в два раза больше, чем для перебора одного ключа) и $2^{57}$ памяти. Дополнительные оптимизации — использование хеш-таблиц, вычисления только для половины ключей (для DES полный перебор, на самом деле, требует лишь $2^{55}$ операций) — могут снизить эти требования. Главный результат атаки состоит в том, что последовательное шифрование двумя ключами увеличивает время перебора лишь в два раза.

Решение в общем виде

Обозначим преобразование алгоритма как $E_{k} (a) = b$ , где $a$ -открытый текст, а $b$ -шифротекст. Его можно представить как композицию $E_{k_{1}} E_{k_{2}} ... E_{k_{h}} (a) = b$ , где $E_{k_{i}}$ — цикловое преобразование на ключе $k_{i}$ . Каждый ключ $k_{i}$ представляет собой двоичный вектор длины $n$ , а общий ключ системы — вектор длины $n \times h$ .

Заполнение памяти

Перебираются все значения $k^{'} = (k_{1}, k_{2} ... k_{r})$ , т.е первые $r$ цикловых ключей. На каждом таком ключе $k^{'}$ зашифровываем открытый текст $a$ — $E_{k^{'}} (a) = E_{k_{1}} E_{k_{2}} ... E_{k_{r}} (a) = S$ (то есть проходим $r$ циклов шифрования вместо $h$ ). Будем считать $S$ неким адресом памяти и по этому адресу запишем значение $k^{'}$ . Необходимо перебрать все значения $k^{'}$ .

Определение ключа

Перебираются все возможные $k^{″} = (k_{r + 1}, k_{r + 2} ... k_{h})$ . На получаемых ключах расшифровывается шифротекст $b$ — $E_{k^{″}}^{- 1} (b) = E_{k_{h}}^{- 1} ... E_{k_{r + 1}}^{- 1} (b) = S^{'}$ . Если по адресу $S^{'}$ не пусто, то достаем оттуда ключ $k^{'}$ и получаем кандидат в ключи $(k^{'}, k^{″}) = k$ .

Однако нужно заметить, что первый же полученный кандидат $k$ не обязательно является истинным ключом. Да, для данных $a$ и $b$ выполняется $E_{k} (a) = b$ , но на других значениях открытого текста $a^{'}$ шифротекста $b^{'}$ , полученного из $a^{'}$ на истинном ключе, равенство может нарушаться. Все зависит от конкретных характеристик криптосистемы. Но иногда бывает достаточно получить такой «псевдоэквивалентный» ключ. В противном же случае после завершения процедур будет получено некое множество ключей $k^{'}, k^{″} ...$ , среди которых находится истинный ключ.

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

Атака с разбиением ключевой последовательности на 3 части

В некоторых случаях бывает сложно разделить биты последовательности ключей на части, относящиеся к разным ключам. В таком случае применяют алгоритм Шаблон:Нп5, предложенный Богдановым и Ричбергером в 2011 году на основе обычного метода встречи посередине. Данный алгоритм применим, когда нет возможности разделить последовательности ключевых битов на две независимые части. Состоит из двух фаз: выделения и проверки ключей^[2].

Фаза выделения ключей

Вначале данной фазы шифр делится на 2 подшифра $f$ и $g$ , как и в общем случае атаки, однако допуская возможное использование некоторых битов одного подшифра в другом. Так, если $b = E_{k} (a)$ , то $E_{k} (*) = f (g (*))$ ; при этом биты ключа $k$ , использующиеся в $f$ обозначим $k_{f}$ , а в $g$ — $k_{g}$ . Тогда ключевую последовательность можно разделить на 3 части:

$A_{0}$ — пересечение множеств $k_{f}$ и $k_{g}$ ,
$A_{1}$ — ключевые биты, которые есть только в $k_{f}$ ,
$A_{2}$ — ключевые биты, которые есть только в $k_{g}$ .

Далее проводится атака методом встречи посередине по следующему алгоритму:

Для каждого элемента из $A_{0}$

Вычислить промежуточное значение $i = f (k_{f}, a)$ , где $a$ — открытый текст, а $k_{f}$ — некоторые ключевые биты из $A_{0}$ и $A_{1}$ , то есть $i$ — результат промежуточного шифрования открытого текста на ключе $k_{f}$ .
Вычислить промежуточное значение $j = g^{- 1} (k_{g}, b)$ , где $b$ — закрытый текст, а $k_{g}$ — некоторые ключевые биты из $A_{0}$ и $A_{2}$ , то есть $j$ — результат промежуточного расшифровывания закрытого текста на ключе $k_{g}$ .
Сравнить $i$ и $j$ . В случае совпадения получаем кандидата в ключи.

Фаза проверки ключей

Для проверки ключей полученные кандидаты проверяют на нескольких парах известных открытых-закрытых текстов. Обычно для проверки требуется не очень большое количество таких пар текстов^[2].

Пример

В качестве примера приведем атаку на семейство шифров KTANTAN^[3], которая позволила сократить вычислительную сложность получения ключа с $2^{80}$ (атака полным перебором) до $2^{75, 170}$ ^[1].

Подготовка атаки

Каждый из 254 раундов шифрования с использованием KTANTAN использует 2 случайных бита ключа из 80-битного набора. Это делает сложность алгоритма зависимой только от количества раундов. Приступая к атаке, авторы заметили следующие особенности:

В раундах с 1 по 111 не были использованы следующие биты ключа: $k_{32}, k_{39}, k_{44}, k_{61}, k_{66}, k_{75}$ .
В раундах со 131 по 254 не были использованы следующие биты ключа: $k_{3}, k_{20}, k_{41}, k_{47}, k_{63}, k_{74}$ .

Это позволило разделить биты ключа на следующие группы:

$A_{0}$ — общие биты ключа: те 68 бит, не упомянутые выше.
$A_{1}$ — биты, используемые только в первом блоке раундов (с 1 по 111),
$A_{2}$ — биты, используемые только во втором блоке раундов (со 131 по 254).

Первая фаза: выделение ключей

Возникала проблема вычисления описанных выше значений $i$ и $j$ , так как в рассмотрении отсутствуют раунды со 112 по 130, однако тогда было проведено Шаблон:Нп5: авторы атаки заметили совпадение 8 бит в $i$ и $j$ , проверив их обычной атакой методом встречи посередине на 127 раунде. В связи с этим в данной фазе сравнивались значения именно этих 8 бит в подшифрах $i$ и $j$ . Это увеличило количество кандидатов в ключи, но не сложность вычислений.

Вторая фаза: проверка ключей

Для проверки кандидатов в ключи алгоритма KTANTAN32 потребовалось в среднем еще две пары открытого-закрытого текстов для выделения ключа.

Результаты

KTANTAN32: вычислительная сложность подбора ключа сократилась до $2^{75, 170}$ с использованием трех пар открытого-закрытого текста.
KTANTAN48: вычислительная сложность подбора ключа сократилась до $2^{75, 044}$ с использованием двух пар открытого-закрытого текста.
KTANTAN64: вычислительная сложность подбора ключа сократилась до $2^{75, 584}$ с использованием двух пар открытого-закрытого текста.

Тем не менее, это не лучшая атака на семейство шифров KTANTAN. В 2011 году была совершена атака^[4], сокращающая вычислительную сложность алгоритма до $2^{72, 9}$ с использованием четырех пар открытого-закрытого текста.

Атака по полному двудольному графу

Атака по полному двудольному графу применяется для увеличения количества попыток атаки посредника с помощью построения полного двудольного графа. Предложена Диффи и Хеллманом в 1977 году.

Многомерный алгоритм

Многомерный алгоритм метода встречи посередине применяется при использовании большого количества циклов шифрования разными ключами на блочных шифрах. Вместо обычной «встречи посередине» в данном алгоритме используется разделение криптотекста несколькими промежуточными точками^[5].

Предполагается, что атакуемый текст зашифрован некоторое количество раз блочным шифром:

$C = E N C_{k_{n}} (E N C_{k_{n - 1}} (... (E N C_{k_{1}} (P)) ...))$ $P = D E C_{k_{1}} (D E C_{k_{2}} (... (D E C_{k_{n}} (C)) ...))$

Алгоритм

Вычисляется:

s C_{1} = E N C_{f_{1}} (k_{f_{1}}, P)

\forall k_{f_{1}} \in K

s C_{1}

сохраняется вместе с

k_{1}

d

H_{1}

.

s C_{n + 1} = D E C_{b_{n + 1}} (k_{b_{n + 1}}, C)

\forall k_{b_{n + 1}} \in K

s C_{n + 1}

сохраняется вместе с

k_{b_{n + 1}}

d

H_{b_{n + 1}}

.

Для каждого возможного промежуточного состояния $s_{1}$ вычисляется:

s C_{1} = D E C_{b_{1}} (k_{b_{1}}, s_{1})

\forall k_{b_{1}} \in K

при каждом совпадении

s C_{1}

с элементом из

H_{1}

в

T_{1}

сохраняются

k_{b_{1}}

и

k_{f_{1}}

.

s C_{2} = E N C_{f_{2}} (k_{f_{2}}, s_{1})

\forall k_{f_{2}} \in K

s C_{2}

сохраняется вместе с

k_{f_{2}}

в

H_{2}

.

Для каждого возможного промежуточного состояния $s_{2}$ вычисляется:

s C_{2} = D E C_{b_{2}} (k_{b_{2}}, s_{2})

\forall k_{b_{2}} \in K

при каждом совпадении

s C_{2}

с элементом из

H_{2}

проверяется совпадение с

T_{1}

, после чего в

T_{2}

сохраняются

k_{b_{2}}

и

k_{f_{2}}

.

s C_{3} = E N C_{f_{3}} (k_{f_{3}}, s_{2})

\forall k_{f_{3}} \in K

s C_{3}

сохраняется вместе с

k_{f_{3}}

в

H_{3}

.

Для каждого возможного промежуточного состояния $s_{n}$ вычисляется:

s C_{n} = D E C_{b_{n}} (k_{b_{n}}, s_{n})

\forall k_{b_{n}} \in K

и при каждом совпадении

s C_{n}

с элементом из

H_{n}

проверяется совпадение с

T_{n - 1}

, после чего в

T_{n}

сохраняются

k_{b_{n}}

и

k_{f_{n}}

.

s C_{n + 1} = E N C_{f_{n + 1}} (k_{f_{n + 1}}, s_{n})

\forall k_{f_{n + 1}} \in K

и при каждом совпадении

s C_{n + 1}

с

H_{n + 1}

, проверяется совпадение с

T_{n}

Далее найденная последовательность кандидатов тестируется на иной паре открытого-закрытого текста для подтверждения истинности ключей. Следует заметить рекурсивность в алгоритме: подбор ключей для состояния $s_{j}$ происходит на основе результатов для состояния $s_{j - 1}$ . Это вносит элемент экспоненциальной сложности в данный алгоритм^[5].

Сложность

Шаблон:Mainref Временная сложность данной атаки составляет $2^{| k_{f_{1}} |} + 2^{| k_{b_{n + 1}} |} + 2^{| s_{1} |} \cdot (2^{| k_{b_{1}} |} + 2^{| k_{f_{2}} |} + 2^{| s_{2} |} \cdot (2^{| k_{b_{2}} |} + 2^{| k_{f_{3}} |} + ...))$

Говоря об использовании памяти, легко заметить что с увеличением $i$ на каждый $T_{i}$ накладывается все больше ограничений, что уменьшает количество записываемых в него кандидатов. Это означает, что $T_{2}, T_{3}, ..., T_{n}$ значительно меньше $T_{1}$ .

Верхняя граница объема используемой памяти:

2^{| k_{f_{1}} |} + 2^{| k_{b_{n + 1}} |} + 2^{| k | - | s + n |} + ...

где

k

— общая длина ключа.

Сложность использования данных зависит от вероятности «прохождения» ложного ключа. Эта вероятность равна $1 / 2^{l}$ , где $l$ — длина первого промежуточного состояния, которая чаще всего равна размеру блока. Учитывая количество кандидатов в ключи после первой фазы, сложность равна $2^{| k | - | l |}$ .

В итоге получаем $2^{| k | - 2 b}$ , где $| b |$ — размер блока.

Каждый раз, когда последовательность кандидатов в ключи тестируется на новой паре открытого-закрытого текста, количество успешно проходящих проверку ключей умножается на вероятность прохождения ключа, которая равна $1 / 2^{| b |}$ .

Часть атаки полным перебором (проверка ключей но новых парах открытого-закрытого текстов) имеет временную сложность $2^{| k | - b} + 2^{| k | - 2 b} + 2^{| k | - 3 b} + ...$ , в которой, очевидно, последующие слагаемые все быстрее стремятся к нулю.

В итоге, сложность данных по аналогичным суждениям ограничена приблизительно $⌈ | k | / n ⌉$ парами открытого-закрытого ключа.

Примечания

Шаблон:Примечания

Литература

Шаблон:Статья

↑ ^1,0 ^1,1 Шаблон:Статья
↑ ^2,0 ^2,1 Andrey Bogdanov and Christian Rechberger. «A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN» Шаблон:Wayback
↑ Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. «KATAN & KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers» Шаблон:Wayback
↑ Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang, and San Ling. «Improved Meet-in-the-Middle Cryptanalysis of KTANTAN» Шаблон:Wayback
↑ ^5,0 ^5,1 Шаблон:Статья

[dh-1] 1,0 ^1,1 Шаблон:Статья

[3dmitm-2] 2,0 ^2,1 Andrey Bogdanov and Christian Rechberger. «A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN» Шаблон:Wayback

[3] Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. «KATAN & KTANTAN — A Family of Small and Efficient Hardware-Oriented Block Ciphers» Шаблон:Wayback

[4] Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang, and San Ling. «Improved Meet-in-the-Middle Cryptanalysis of KTANTAN» Шаблон:Wayback

[ZhuGuang2011-5] 5,0 ^5,1 Шаблон:Статья

[1]

[2]

[3]

[4]

[5]

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

Содержание

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

Решение простого случая

Решение в общем виде

Заполнение памяти

Определение ключа

Атака с разбиением ключевой последовательности на 3 части

Фаза выделения ключей

Фаза проверки ключей

Пример

Подготовка атаки

Первая фаза: выделение ключей

Вторая фаза: проверка ключей

Результаты

Атака по полному двудольному графу

Многомерный алгоритм

Алгоритм

Сложность

Примечания

Литература

Навигация

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

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

Решение простого случая

Решение в общем виде

Заполнение памяти

Определение ключа

Атака с разбиением ключевой последовательности на 3 части

Фаза выделения ключей

Фаза проверки ключей

Пример

Подготовка атаки

Первая фаза: выделение ключей

Вторая фаза: проверка ключей

Результаты

Атака по полному двудольному графу

Многомерный алгоритм

Алгоритм

Сложность

Примечания

Литература

Навигация

Поиск