Алгебраический метод

ГОСТ 28147-89: «Не спеши его хоронить». Часть 1. Стойкость алгоритма.

В последние годы появляется большое количество статей, посвященных анализу российского алгоритма блокового («блочного») шифрования ГОСТ 28147-89. Одновременно с этим в российских СМИ и блогах российских пользователей растет число заметок о данном алгоритме: как освещающих различной степени достоверности результаты атак на российский стандарт, так и содержащих мнения о его эксплуатационных характеристиках.

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

Николя Куртуа — «великий и ужасный»

Начнем с рассказа о деятельности Николя Куртуа, который является автором целого цикла работ, посвященных российскому стандарту блокового шифрования ([Cour1-Cour5]).

В октябре 2010 года был начат процесс рассмотрения вопроса о включении алгоритма ГОСТ 28147-89 в международный стандарт ISO/IEC 18033-3. Уже в мае 2011 года на электронном архиве ePrint появилась статья известного криптографа Николя Куртуа [Cour1], отмеченного весьма неоднозначным отношением к нему мирового криптографического сообщества. Публикации Куртуа представляют собой печальный пример манипулирования понятиями, которое не открывает никаких новых свойств рассматриваемого объекта, но с претензией на сенсацию провоцирует распространение в некомпетентной среде ошибочных мнений о его действительных свойствах.

Эта, а также последующие ([Cour2-Cour6]) посвященные ГОСТ 28147-89 статьи Куртуа имеют крайне сходную структуру. В аннотации и введении содержится насыщенный эпитетами текст о том, насколько ужасающе слабым оказался российский стандарт блокового шифрования, как легко было построить на него атаку и как катастрофично было положение наивного комитета ISO, который, практически находясь на краю пропасти, чуть было не принял столь уязвимый российский стандарт в качестве международного. Далее присутствуют несколько оценок трудоемкости атак Куртуа, существенно меньших априорной (трудоемкости полного перебора ключей) 2²⁵⁶, несколько слов о недальновидности международного криптографического сообщества, в очередной раз отвергнувшего очередную его работу, а дальше… дальше идет основное содержание работы, в котором дошедший до него читатель (а не журналист, радостно закрывший статью, чтобы мгновенно поделиться с миром новостью о тотальных уязвимостях в российском стандарте), к своему удивлению, не находит ничего похожего на строгий научный текст с обоснованиями атак: вместо повествования, построенного по принципу «утверждение-доказательство», в работах присутствуют «факты» и комментарии к этим фактам. В качестве обоснования этих фактов приводятся, в лучшем случае, правдоподобные рассуждения, но никак не строгие доказательства. В заключениях работ содержится еще один яркий фрагмент текста о совершенной неожиданности обнаружения столь существенных слабостей в блоковом шифре, разработанном в недрах лабораторий могучего КГБ СССР.

«It appears that also that it is for the first time in history that a major standardized block cipher intended to provide a military-grade level of security and intended to protect also classified and secret documents, for the government, large banks and other organisations, is broken by a mathematical attack.»

Алгебраический метод

Рассуждения Куртуа строятся вокруг двух классов методов криптоанализа: алгебраических методов и дифференциальных. Рассмотрим первый класс методов.

Упрощенно метод алгебраического криптоанализа можно описать как составление и решение большой системы уравнений, каждое из решений которой соответствует цели криптоаналитика (например, если система составляется по одной паре открытого и шифрованного текстов, то все решения этой системы соответствуют ключам, при которых данный открытый текст преобразуется в данный шифрованный). То есть, в случае задачи криптоанализа блокового шифра, суть алгебраического метода криптоанализа состоит в том, что ключ находится в результате решения системы полиномиальных уравнений. Основная сложность состоит в том, чтобы с учетом особенностей конкретного шифра суметь составить как можно более простую систему, чтобы процесс ее решения занял как можно меньше времени. Здесь ключевую роль играют особенности каждого конкретного анализируемого шифра.

Алгебраический метод, эксплуатируемый Куртуа, коротко можно описать так. На первом этапе используются такие свойства ГОСТ 28147-89, как существование неподвижной точки для части шифрующего преобразования, а также так называемой точки отражения (reflection point). Благодаря этим свойствам из достаточно большого количества пар открытых — шифрованных текстов выбирается несколько пар, которые позволяют рассматривать преобразования не на 32, а лишь на 8 раундах. Второй этап состоит в том, что по полученным на первом этапе результатам 8-ми раундовых преобразований строится система нелинейных уравнений, неизвестными в которой являются биты ключа. Далее эта система решается (это звучит просто, но в действительности является самой трудоемкой частью метода, т.к. система состоит из нелинейных уравнений).

Как уже отмечалось выше, нигде в работе нет детального описания и анализа трудоемкости второго и главного этапа определения ключа. Именно трудоемкость второго этапа определяет трудоемкость всего метода в целом. Вместо этого автор приводит пресловутые «факты», на основе которых делает оценки трудоемкости. Утверждается, что эти «факты» основаны на результатах экспериментов. Анализ «фактов» из работы Куртуа в целом приведен в работе [Rud2] отечественных авторов. Авторами этой работы отмечается, что многие из представленных без каких-либо доказательств «фактов» Куртуа при экспериментальной проверке оказались ложными. Авторы статьи пошли дальше и за Куртуа провели анализ трудоемкости второго этапа с помощью хорошо обоснованных алгоритмов и оценок. Получившиеся в результате оценки трудоемкости показывают полную неприменимость представленной атаки. Помимо отечественных авторов, большие проблемы, которые возникают у Куртуа с оценками и обоснованием своих методов, отмечались также, например, в работе [Cid].