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

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

Типы атак

Общие

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

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

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

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

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

XSL

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

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

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

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

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

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

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

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

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

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

$P' = F(P)\,$

$C' = F(C).\,$

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

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

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

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

Метод Бумеранга.

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

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

Причем $Q \oplus Q' = P \oplus P' = \Delta \,$.

Примечания.

1. ↑ Ковтун В.Ю. "Введение в криптоанализ. Криптоанализ симметричных криптосистем: блочные шифры"
2. ↑ N. Courtois, J. Pieprzyk "Cryptology ePrint Archive: Report 2002/044"
3. ↑ ^{1 2 3} Сергей Панасенко Алгоритмы шифрования.

Литература.

1. Нильс Фергюсон, Брюс Шнайер Практическая криптография.
2. Christof Paar, Jan Pelzl, Bart Preneel Understanding Cryptography.
3. Chalermpong Worawannotai, Isabelle Stanton A Tutorial on Slide Attacks.
4. Сергей Панасенко Алгоритмы шифрования.
5. Isabelle Stanton. "slideattacks"..