Атака на блочный шифр

Атака на блочный шифр — попытка взлома (дешифрования) данных, зашифрованных блочным шифром.

К блочным шифрам применимы все основные типы атак, однако существуют некоторые, специфичные лишь для блочных шифров, атаки.

Типы атак

Общие

1. Атака с использованием только шифрованного текста (ciphertext-only attack) — пользователи A и B зашифровывают свои данные, а криптоаналитик пытается расшифровать сообщение только при наличии шифрованного текста.
2. Атака с известным открытым текстом (known plaintext attack) — известны и открытый и шифрованный текст. Цель атаки — найти ключ.
3. Атака с избранным открытым текстом (chosen plaintext attack) — криптоаналитик может самостоятельно подбирать открытый текст. Имеется возможность отсылать любое количество простых текстов и получать в ответ соответствующие шифрованные тексты. Существуют автономная (offline) и оперативная (online) виды атак. В первом случае выбор открытых текстов подготавливается заранее, до получения шифрованных текстов. Во втором случае каждый последующий открытый текст выбирается исходя из уже полученных шифрованных текстов.
4. Атака с избранным шифрованным текстом (chosen ciphertext attack) — у криптоаналитика есть возможность подбирать как открытый, так и шифрованный текст. Для каждого подобранного открытого текста криптоаналитик получает шифрованный текст, для каждого подобранного шифрованного текста — соответствующий открытый текст.
5. Атаки, в основе которых лежит парадокс задачи о днях рождения (birthday attack) — атаки, получившие своё название в честь парадокса задачи о днях рождения. Суть парадокса в следующем: если в комнате находятся 23 человека, то вероятность того, что два из них родились в один и тот же день, превышает 50 %. Этот тип атак основан на том, что одинаковые значения появляются быстрее, чем можно было ожидать.
6. Двусторонняя атака или атака «встреча на середине» (meet-in-the-middle attack) — криптоаналитик строит таблицу ключей, которые выбрал самостоятельно. Различие между атакой, в основе которой лежит парадокс о днях рождениях, и двусторонней атакой в том, что в первом случае криптоаналитик ждёт, когда одно и то же значение появится дважды во множестве элементов, в двусторонней атаке он ждёт, когда два множества пересекутся.

Специфичные

1. Атака со связанным ключом (related key attack) — впервые её представил Эли Бихам в 1993 году. Данная атака предполагает, что криптоаналитик имеет доступ к нескольким функциям шифрования. Все функции работают с неизвестными ключами, однако ключи связаны определённым отношением, которое известно криптоаналитику. Множество реальных систем используют разные ключи, связанные известным соотношением. Например, для каждого нового сообщения предыдущее значение ключа увеличивается на единицу.
2. Атака с избранным ключом (chosen key attack) — криптоаналитик задаёт часть ключа, а на оставшуюся часть ключа выполняет атаку со связанным ключом.
3. Усечённый дифференциальный криптоанализ (truncated differential cryptanalysis) — атака на блочные шифры, обобщение дифференциального криптоанализа. Ларс Кнудсен разработал эту атаку в 1994 году^[1]. В то время как обычный дифференциальный анализ использует разность между двумя полными текстами, в усечённом криптоанализе рассматривается разность между частями текста. Поэтому с помощью этой атаки можно предсказать значения лишь некоторых бит, а не целого блока.

Некоторые алгоритмы атак

Полный перебор

Полный перебор (или метод «грубой силы», англ. brute force attack) — атака основана на простом понятии: у Оскара, атакующего, есть подслушанный шифрованный текст и у него оказалась небольшая часть открытого текста, например, заголовок файла, который он расшифровывает. Оскар вначале просто расшифровывает небольшую часть шифрованного текста всеми возможными ключами. Ключ для этого шифра — это таблица замещений. Если получившийся текст соответствует небольшой части открытого текста — правильный ключ найден.

Пусть ${\displaystyle (x,y)}$ означают пару открытого и зашифрованного текста, и пусть ${\displaystyle K=(k_{1},...,k_{k})}$ множество всех возможных ключей ${\displaystyle k_{i}}$. Атака на основе полного перебора проверяет для каждого ${\displaystyle k_{i}\in \ K}$ выполнение: ${\displaystyle d_{k}i(y)=x}$. Если равенство выполняется, правильный ключ найден, если не выполняется проверяется следующий ключ. На практике метод грубой силы может быть сложнее, так как неправильные ключи могут дать неверные положительные результаты.

XSL

XSL-атака (eXtended Sparse Linearization) — метод, основанный на алгебраических свойствах шифра, предполагает решение особой системы уравнений. Впервые был опубликована в 2002 году^[2].

Результат работы S-блоков системы с многораундовым шифрованием записываются в виде уравнения:

${\displaystyle \sum _{i,j}\alpha _{ij}*x_{i}*x_{j}+\sum _{i,j}\beta _{ij}*y_{i}*y_{j}+\sum _{i,j}\gamma _{ij}*x_{i}*y_{j}+\sum _{i}\delta _{i}*x_{i}+\sum _{i}\epsilon _{i}*x_{i}+\eta =0}$

Где ${\displaystyle x_{i}}$ и ${\displaystyle y_{i}}$ — соответственно биты на входе и выходе S-блоков i-го раунда шифрования.

Далее для различных значений входных текстов и соответствующих им шифртекстов составляются таблицы истинности, на основе которых определяется значение ключа системы.

Сдвиговая атака

Рис.1 Сдвиговая атака

Сдвиговая атака (slide attak) — была предложена в 1999 г. Алексом Бирюковым и Дэвидом Вагнером^[3]. В данной атаке количество раундов шифрования не имеет значения. В отличие от отыскания каких-либо аспектов случайных данных блочного шифра, сдвиговая атака анализирует таблицу ключей, находя её слабости, чтобы взломать шифр. Самая распространённая таблица ключей — циклическое повторение ключей. Сдвиговая атака тесно связана с атакой со связанным ключом. Необходимым требованием для сдвиговой атаки является идентичность раундов у алгоритмов, к которым она применяется возможность разбиения зашифрованного текста на несколько раундов из одинаковых ${\displaystyle F}$ функций.

Алгоритм атаки:

1. Выбирается блок текста длиной ${\displaystyle n}$ бит и последовательность ключей: ${\displaystyle K_{1}...K_{m}}$ любых длин.
2. Процесс шифрования разбивается на одинаковые функции ${\displaystyle F}$, которые могут состоять из более одного раунда шифрования, это определяется из последовательности ключей. Например, если при шифровании используются чередующиеся ключи для каждого раунда ${\displaystyle (K_{1}}$ и ${\displaystyle K_{2})}$, то ${\displaystyle F}$ функция будет состоять из двух раундов. Каждый из ключей ${\displaystyle K_{i}}$ появится, по крайней мере, один раз в ${\displaystyle F}$.
3. Следующий шаг, получить ${\displaystyle 2^{n/2}}$ пар: открытый текст — зашифрованный текст. В зависимости от характеристик зашифрованного текста меньшее количество пар будет достаточно, но из парадокса день рождений потребуется не меньше чем ${\displaystyle 2^{n/2}}$ пар. Данные пары ${\displaystyle (P,C)}$ используются в дальнейшем, чтобы найти slide пару ${\displaystyle (P',C')}$. Свойство пары:

${\displaystyle P'=F(P)}$

${\displaystyle C'=F(C).}$

Как только найдена пара, шифр взломан из-за уязвимости для атаки с известным открытым текстом.

Невозможные дифференциалы

Невозможные дифференциалы (impossible differentials) — принципиально новый вариант дифференциального криптоанализа, предложенный Эли Бихамом, Ади Шамиром и Алексом Бирюковым в 1998 году^[3]. Данный метод использует дифференциалы с нулевой вероятностью, в отличие от дифференциального криптоанализа.

Процесс взлома:

1. Выбираются пары открытых текстов с некоторой разностью; получаются соответствующие им шифртексты.
2. Выполняется анализ полученных данных, все варианты ключа шифрования, приводящие к невозможным дифференциалам, отбрасываются.
3. Результаты приводят к невозможным дифференциалам — или единственный возможный вариант ключа, или подмножество ключевого множества. Для нахождения верного ключа из подмножества, например, производится полный перебор.

Метод бумеранга

Метод бумеранга (boomerang attack) предложен в 1999 году Дэвидом Вагнером^[3]. Данный метод практически является улучшением дифференциального криптоанализа, в нём используется квартет (четыре текста вместо двух) открытых текстов и соответствующих им шифртекстов.

Алгоритм:

1. Разделим ${\displaystyle N}$-раундовый алгоритм на две части по ${\displaystyle N/2}$ раундов.
2. ${\displaystyle E_{0}()}$ — процедура зашифровывания первой части алгоритма. Для квартета выберем два открытых текста ${\displaystyle P}$ и ${\displaystyle P'}$, разность между ними составляет некоторую величину ${\displaystyle \Delta }$. Воздействуя на тексты функцией ${\displaystyle E_{0}()}$, получаем разность ${\displaystyle \Delta *}$(считая, что разность определяется XOR): ${\displaystyle E_{0}(P)\oplus E_{0}(P')=\Delta *}$.
3. Теперь зашифруем тексты ${\displaystyle P}$ и ${\displaystyle P'}$, применяя к ним процедуру зашифровывания второй части ${\displaystyle E_{1}()}$. Получаем шифртексты ${\displaystyle C}$ и ${\displaystyle C'}$: ${\displaystyle C=E_{1}(E_{0}(P))}$; ${\displaystyle C'=E_{1}(E_{0}(P'))}$.
4. Криптоаналитика не интересует разность между ${\displaystyle C}$ и ${\displaystyle C'}$. С помощью них получаем два других шифртекста ${\displaystyle D}$ и ${\displaystyle D'}$, связанных с ними разностью ${\displaystyle \nabla }$: ${\displaystyle C\oplus D=C'\oplus D'=\nabla }$.
5. Теперь формирование квартета происходит в обратную сторону: к ${\displaystyle D}$ и ${\displaystyle D'}$ применяются ${\displaystyle E_{1}^{-1}()}$, причем ${\displaystyle E_{1}^{-1}(C)=E_{0}(P)}$: ${\displaystyle E_{1}^{-1}(D)\oplus E_{0}(P)=E_{1}^{-1}(D')\oplus E_{0}(P')=\nabla *}$.
6. ${\displaystyle Q}$ и ${\displaystyle Q'}$ расшифровывают шифртексты ${\displaystyle D}$ и ${\displaystyle D'}$: ${\displaystyle Q=E_{0}^{-1}(E_{0}^{-1}(D))}$; ${\displaystyle Q'=E_{0}^{-1}(E_{0}^{-1}(D'))}$;

Причём ${\displaystyle Q\oplus Q'=P\oplus P'=\Delta }$.

Примечания

1. Ковтун В. Ю. «Введение в криптоанализ. Криптоанализ симметричных криптосистем: блочные шифры»  (неопр.). Дата обращения: 8 декабря 2011. Архивировано 4 марта 2016 года.
2. N. Courtois, J. Pieprzyk «Cryptology ePrint Archive: Report 2002/044»  (неопр.). Дата обращения: 8 декабря 2011. Архивировано 27 февраля 2012 года.
3. Панасенко, 2009.

Литература

• Нильс Фергюсон, Брюс Шнайер. Практическая криптография.
• Christof Paar, Jan Pelzl, Bart Preneel. Understanding Cryptography.
• Chalermpong Worawannotai, Isabelle Stanton. A Tutorial on Slide Attacks.
• Панасенко С. П. Алгоритмы шифрования. Специальный справочник — СПб.: BHV-СПб, 2009. — 576 с. — ISBN 978-5-9775-0319-8
• Isabelle Stanton. slideattacks (PDF). Архивировано из оригинала (PDF) 5 марта 2016. Дата обращения: 8 декабря 2011. Архивная копия от 5 марта 2016 на Wayback Machine