Уязвимость алгоритма шифрования ГОСТ 28147-89 к дифференциальному анализу

Ищукова Е.А.,

Южный Федеральный Университет,

г. Ростов-на-Дону

Алгоритм ГОСТ используется в качестве государственного стандарта в Российской Федерации. До сих пор в открытой печати имеется сравнительно мало информации о возможных уязвимостях данного шифра. Одной из наиболее значимых работ является статья [3], в которой авторы предложили вариант анализа алгоритма ГОСТ с использованием дифференциального криптоанализа на связанных ключах (Related-Key Attack) при условии использования слабых блоков замены. В настоящей работе рассмотрена возможность осуществления атаки на алгоритм шифрования ГОСТ с помощью классического метода дифференциального криптоанализа и определены условия, при которых осуществление данной атаки возможно.

Метод дифференциального криптоанализа, впервые предложенный Э. Бихамом (E. Biham) и А. Шамиром (A. Shamir) для анализа алгоритма DES [1, 2], базируется на прослеживании изменения разности двух сообщений при их прохождении через раунды шифрования. После появления работ [1, 2] большинство существовавших на тот момент алгоритмов шифрования были подвергнуты анализу с использованием данного метода. Исследования показали, что метод дифференциального криптоанализа является универсальным, то есть может быть применен к анализу большинства известных симметричных криптосистем. Именно поэтому вновь создаваемые алгоритмы шифрования в первую очередь тестируются на устойчивость к данному виду анализа.

Отличительной чертой алгоритма ГОСТ является использование в его структуре нефиксированных блоков замены. Предполагается, что при любом заполнении S-блоков тридцати двух раундов шифрования будет достаточно для того, чтобы противостоять таким мощным методам анализа, как линейный и дифференциальный криптоанализ. В данной работе показано, что существуют слабые блоки замены, использование которых в алгоритме ГОСТ может привести к успешному осуществлению атаки на основе метода дифференциального криптоанализа. Долгое время считалось, что если оставлять S-блоки в секрете, то их можно рассматривать как дополнительный ключевой материал [6]. Однако в работе [5] был предложен метод, применение которого позволяет достаточно просто восстановить значения S-блоков, используемых для шифрования данных.

Метод дифференциального криптоанализа базируется на прослеживании изменения несхожести между двумя сообщениями. Для определения несхожести используется операция сложения по модулю два, которая в результате сложения дает ненулевые биты в тех позициях, в которых два исходных сообщения имели различные значения битов. В работе [4] были выявлены дифференциальные свойства основных криптографических преобразований алгоритма ГОСТ, которые используются для нахождения характеристик с максимальными вероятностями.

В ходе работы была рассмотрена возможность проведения атаки на алгоритм ГОСТ при использовании слабых блоков замены. В качестве слабых были определены блоки, для которых входная разность ΔА, содержащая одну единицу заменяется на выходную разность ΔС, также содержащую одну единицу. Показано, что существует 384 различных S-блоков, обладающих слабыми свойствами.

Для упрощения анализа в алгоритме был использован один и тот же слабый S-блок, однако это не значит, что для успешного анализа алгоритм ГОСТ должен использовать один и тот же S-блок. Возможно достаточно большое число комбинаций из 384 слабых блоков, которые могут привести к подобному результату.

Для успешного проведения анализа необходимо найти несколько характеристик с довольно большими вероятностями, в каждой из которых будет задействован одна или несколько тетрад со значением 1_х, 2_х или 4_х.

В работе [4] была представлена разработка универсального алгоритма, позволяющего осуществлять поиск хороших характеристик для алгоритма ГОСТ. На вход данного алгоритма поступает значение входной разности. После этого рассматриваются все варианты преобразования разности (с учетом свойств таблиц анализа для S-блоков) и отбираются те выходные разности, для которых вероятность будет либо максимальна, либо не ниже заданной (в соответствии с начальными установками алгоритма). Анализ 32 раундов алгоритма ГОСТ, использующего слабые блоки замены, показал, что существует достаточно большой объем пар входная – выходная разность, для которых характеристика обладает достаточно большой вероятностью (в пределах от 2^-25 до 2^-33) и может быть использована для анализа. Такие значения вероятностей позволяют надеяться на сравнительно легкое нахождение правильных пар текстов, пригодных для анализа. Согласно Парадоксу Дней Рождений для нахождения правильной пары текстов, соответствующей характеристике, которая выполняется с вероятностью  необходимо в среднем проанализировать 2^33,5 пар текстов. Подобный отбор с использованием алгоритма, приведенного в работе [4] может занять от нескольких минут до получаса.

При поиске ключа для каждой правильной пары текстов необходимо рассматривать первый и последний раунды шифрования. В соответствии с классической структурой алгоритма ГОСТ в первом и последнем раунде используется один и тот же раундовый подключ К1. Таким образом, анализ первого и последнего раундов позволит сделать предположение о значении первого раундового подключа.

То, что найдена правильная пара текстов, соответствующая заданной характеристике, позволяет предполагать, что разность при прохождении через раунды шифрования преобразовывалась именно так, как было определено при построении характеристики. Для первого раундового подключа К1 необходимо рассматривать восемь тетрад k1, k2, k3, k4, k5, k6, k7, k8 в соответствии с количеством используемых блоков замены. Для каждой тетрады необходимо производить опробование 16 вариантов возможных значений фрагмента ключа (от 0000 до 1111). При этом необходимо учесть тот факт, что при сложении тетрады сообщения  с тетрадой раундового подключа мог возникнуть перенос из младших разрядов. Поэтому для всех тетрад кроме самой младшей необходимо рассмотреть вариант, когда к результату сложения тетрады сообщения и тетрады ключа будет добавляться еще 1 в младший разряд тетрады. Анализируя правильные пары текстов, можно увидеть, что некоторые значения для каждой тетрады раундового подключа будут встречаться чаще других, что позволит сделать предположения о возможных значениях раундового подключа.

Повысить результаты анализа позволяет прием, который использовали Э. Бихам (E. Biham) и А. Шамир (A. Shamir) при анализе алгоритма DES [1]. При поиске правильных пар текстов для полного 16-раундового DES они рассматривали лишь правую часть выходной характеристики. Левая часть выходной характеристики могла быть равна любому значению. В этом случае вероятность прохождения разности через последний раунд шифрования не учитывалась при определении общей вероятности характеристики. Тот факт, что правая часть правильных пар текстов совпадает с  правой частью рассматриваемой характеристики, позволяет предположить, что разность текстов при прохождении через раунды шифрования преобразовывалась именно так, как это было определено при построении характеристики. И лишь в последнем раунде разность преобразовывалась одним из возможных способов.

В результате такого анализа правильных пар текстов будет сформировано некоторое количество возможных значений (возможно их будет несколько тысяч) раундового подключа К1. После этого необходимо провести анализ тех же правильных пар текстов, но уже с использованием не фрагментов подключа, а с выделенными возможными значениями полного 32-битового раундового подключа. В результате такого опробования останется всего несколько ключей (меньше десяти), один из которых и будет являться истинным раундовым подключом.

Для того, чтобы убедиться в действенности метода, была сымитирована атака на алгоритм ГОСТ, сокращенный до 12 раундов. При этом было использовано 8 раундовых подключей так, чтобы в первом и последнем раунде использовался один и тот же раундовый подключ. В качестве блоков замены был использован один и тот же слабый S-блок. Атака на полный ГОСТ будет выглядеть аналогичным образом, за тем исключением, что потребуется опробовать большее число пар текстов, прежде чем правильная пара текстов будет найдена.

Первоначально было определено 10 характеристик для 12 раундов алгоритма ГОСТ. Для каждой характеристики было опробовано 100 000 пар текстов с целью поиска правильных пар текстов. Полученные правильные пары были проанализированы с использованием техники, описанной выше. Так, в результате первичного отбора тетрад секретного ключа было выделено 16384 возможных ключей из общего числа значений 2³². Последующее опробование полного раундового подключа оставляло в среднем 5 возможных значений (в зависимости от числа найденных правильных пар текстов это значение колебалось от 2 до 10). Полный анализ 12 раундов алгоритма ГОСТ с использованием десяти раундовых характеристик, занимал в среднем от 1 до 2 минут (исследования проводились на процессоре Intel Celeron M CPU 530 1.73 GHz, RAM 1007Mb). Было проведено около 1000 экспериментов с использованием различных значений раундовых подключей, и результат всегда был положителен.

Наличие нефиксированных S-блоков в алгоритме ГОСТ приводит к тому, что каждый раз анализ необходимо начинать сначала. В отличие от алгоритмов с фиксированными блоками замены, где можно единожды определить хорошие характеристики и использовать их для анализа шифрованных данных. В данной работе показано, что при применении предложенных подходов к анализу, а также при использовании алгоритма поиска характеристик, предложенного нами ранее в работе [4], первый этап анализа, заключающийся в поиске хороших характеристик, не составляет проблемы. Хорошая характеристика может быть найдена за несколько секунд и даже меньше.

В работе рассмотрено построение характеристик и проведение анализа для алгоритма ГОСТ, использующего один и тот же слабый блок замены. Продолжением данной работы будет исследование влияния на вероятность характеристики сочетания различных слабых блоков замены, и выявление тех из них, которые могут привести к вскрытию шифра.

Работа выполнена при поддержке грантов РФФИ №12-07-000037-а, 12-07-31120-мол_а.

Библиографический список

1. E. Biham, A. Shamir: “Differential Cryptanalysis of the Full 16-round DES”, Crypto'92, Springer-Velgar, 1998, p.487
2. E. Biham, A. Shamir: “Differential Cryptanalysis of DES-like Cryptosystems”, Extended Abstract, Crypto'90, Springer-Velgar, 1998, p.2
3. Kelsey J., Schnier B., Wagner D., Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SARER, and Triple-DES // http://www.schnier.com – 1996.
4. Бабенко Л.К. Ищукова Е.А. Применение рекурсивного алгоритма поиска в Б-деревьях для дифференциального криптоанализа алгоритма шифрования ГОСТ 28147-89 // Материалы IХ Международной научно-практической конференции «Информационная безопасность». Часть 2. – Таганрог; Изд-во: ТТИ ЮФУ 2007 – С. 92-97.
5. Saarien M.-J. A Chosen Key Attack Against the Secret S-boxes of GOST // http://www.m.-js.com – Helsinki University of Technology, Finland.
6. Панасенко С.П. Алгоритмы шифрования. Специальный справочник. – СПб.: БХВ-Петербург, 2009. – 576 с.