Русская Википедия:Метод встречи посередине

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

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

Даны открытый (незашифрованный) и шифрованный тексты. Криптосистема состоит из <math>h</math> циклов шифрования. Цикловые ключи независимы и не имеют общих битов. Ключ <math>K</math> системы представляет собой сочетание из <math>h</math>-цикловых ключей <math>k_1, k_2 ... k_h</math>. Задача состоит в нахождении ключа <math>K</math>.

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

Простым примером является двойное последовательное шифрование блочным алгоритмом двумя различными ключами <math>K_1</math> и <math>K_2</math>. Процесс шифрования выглядит так:

<math>s = ENC_{K_2}(ENC_{K_1}(p))</math>,

где <math>p</math> — это открытый текст, <math>s</math> — шифротекст, а <math>ENC_{K_i}()</math> — операция однократного шифрования ключом <math>K_i</math>. Соответственно, обратная операция — расшифрование — выглядит так:

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

Все значения <math>m_1 = ENC_{K_1}(p)</math> для всех возможных значений <math>K_1</math>,
Все значения <math>m_2 = ENC^{-1}_{K_2}(s)</math> для всех возможных значений <math>K_2</math>.

Затем ему достаточно лишь найти совпадения в этих таблицах, то есть такие значения <math>m_1</math> и <math>m_2</math>, что <math>ENC_{K_1}(p) = ENC^{-1}_{K_2}(s)</math>. Каждое совпадение соответствует набору ключей <math>(K_1,K_2)</math>, который удовлетворяет условию.

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

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

Обозначим преобразование алгоритма как <math>E_k(a)=b</math>, где <math>a</math> -открытый текст, а <math>b</math> -шифротекст. Его можно представить как композицию <math>E_{k_1}E_{k_2}...E_{k_h}(a)=b</math>, где <math>E_{k_i}</math> — цикловое преобразование на ключе <math>k_i</math>. Каждый ключ <math>k_i</math> представляет собой двоичный вектор длины <math>n</math>, а общий ключ системы — вектор длины <math>n \times h</math>.

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

Перебираются все значения <math>k'=(k_1,k_2...k_r)</math>, т.е первые <math>r</math> цикловых ключей. На каждом таком ключе <math>k'</math> зашифровываем открытый текст <math>a</math> — <math>E_{k'}(a)=E_{k_1}E_{k_2}...E_{k_r}(a)=S</math> (то есть проходим <math>r</math> циклов шифрования вместо <math>h</math>). Будем считать <math>S</math> неким адресом памяти и по этому адресу запишем значение <math>k'</math>. Необходимо перебрать все значения <math>k'</math>.

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

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

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

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

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

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

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

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

<math>A_0</math> — пересечение множеств <math>k_f</math> и <math>k_g</math>,
<math>A_1</math> — ключевые биты, которые есть только в <math>k_f</math>,
<math>A_2</math> — ключевые биты, которые есть только в <math>k_g</math>.

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

Для каждого элемента из <math>A_0</math>

Вычислить промежуточное значение <math>i=f(k_f,a)</math>, где <math>a</math> — открытый текст, а <math>k_f</math> — некоторые ключевые биты из <math>A_0</math> и <math>A_1</math>, то есть <math>i</math> — результат промежуточного шифрования открытого текста на ключе <math>k_f</math>.
Вычислить промежуточное значение <math>j=g^{-1}(k_g,b)</math>, где <math>b</math> — закрытый текст, а <math>k_g</math> — некоторые ключевые биты из <math>A_0</math> и <math>A_2</math>, то есть <math>j</math> — результат промежуточного расшифровывания закрытого текста на ключе <math>k_g</math>.
Сравнить <math>i</math> и <math>j</math>. В случае совпадения получаем кандидата в ключи.

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

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

Пример

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

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

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

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

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

<math>A_0</math> — общие биты ключа: те 68 бит, не упомянутые выше.
<math>A_1</math> — биты, используемые только в первом блоке раундов (с 1 по 111),
<math>A_2</math> — биты, используемые только во втором блоке раундов (со 131 по 254).

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

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

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

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

Результаты

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

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

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

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

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

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

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

Алгоритм

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

<math>sC_1 = ENC_{f_1}(k_{f_1},P) </math> <math>\forall k_{f_1} \in K</math>

<math>sC_1</math> сохраняется вместе с <math>k_1</math> d <math>H_1</math>.

<math>sC_{n+1} = DEC_{b_{n+1}}(k_{b_{n+1}},C) </math> <math>\forall k_{b_{n+1}} \in K</math>

<math>sC_{n+1}</math> сохраняется вместе с <math>k_{b_{n+1}}</math> d <math>H_{b_{n+1}}</math>.

Для каждого возможного промежуточного состояния <math>s_1</math> вычисляется:

<math>sC_1 = DEC_{b_1}(k_{b_1},s_1) </math> <math>\forall k_{b_1} \in K</math>

при каждом совпадении <math>sC_1</math> с элементом из <math>H_1</math> в <math>T_1</math> сохраняются <math>k_{b_1}</math> и <math>k_{f_1}</math>.

<math>sC_2 = ENC_{f_2}(k_{f_2},s_1) </math> <math>\forall k_{f_2} \in K</math>

<math>sC_2</math> сохраняется вместе с <math>k_{f_2}</math> в <math>H_2</math>.

Для каждого возможного промежуточного состояния <math>s_2</math> вычисляется:

<math>sC_2 = DEC_{b_2}(k_{b_2},s_2) </math> <math>\forall k_{b_2} \in K</math>

при каждом совпадении <math>sC_2</math> с элементом из <math>H_2</math> проверяется совпадение с <math>T_1</math>, после чего в <math>T_2</math> сохраняются <math>k_{b_2}</math> и <math>k_{f_2}</math>.

<math>sC_3 = ENC_{f_3}(k_{f_3},s_2) </math> <math>\forall k_{f_3} \in K</math>

<math>sC_3</math> сохраняется вместе с <math>k_{f_3}</math> в <math>H_3</math>.

Для каждого возможного промежуточного состояния <math>s_n</math> вычисляется:

<math>sC_n = DEC_{b_n}(k_{b_n},s_n) </math> <math>\forall k_{b_n} \in K</math> и при каждом совпадении <math>sC_n</math> с элементом из <math>H_n</math> проверяется совпадение с <math>T_{n-1}</math>, после чего в <math>T_n</math> сохраняются <math>k_{b_n}</math> и <math>k_{f_n}</math>.

<math>sC_{n+1} = ENC_{f_{n+1}}(k_{f_{n+1}},s_n) </math> <math>\forall k_{f_{n+1}} \in K</math> и при каждом совпадении <math>sC_{n+1}</math> с <math>H_{n+1}</math>, проверяется совпадение с <math>T_n</math>

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

Сложность

Шаблон:Mainref Временная сложность данной атаки составляет <math>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}|}+...))</math>

Говоря об использовании памяти, легко заметить что с увеличением <math>i</math> на каждый <math>T_i</math> накладывается все больше ограничений, что уменьшает количество записываемых в него кандидатов. Это означает, что <math>T_2, T_3, ..., T_n</math> значительно меньше <math>T_1</math>.

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

где <math>k</math> — общая длина ключа.

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

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

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

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

В итоге, сложность данных по аналогичным суждениям ограничена приблизительно <math>\left \lceil |k|/n \right \rceil</math> парами открытого-закрытого ключа.

Примечания

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

Литература

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

↑ ^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]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.