22.11 // Полная публикация множественных атак на ГОСТ 28147-89 от Николя Куртуа

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

Автор приводит интересные факты: лишь несколькими днями ранее, до того как он отправил работу на конференцию CRYPTO 2011, Ватанаи Изобе уже успел опубликовать свою работу по первой одноключевой атаке на ГОСТ за 2²²⁵ операций. Куртуа утверждает, что свои работы он начал раньше этой публикации, ещё в сентябре 2010 — феврале 2011 года. Также им была направлена улучшенная версия атаки на конференцию Asiacrypt 2011. Также все его атаки превосходят атаки Изобе. Последний шаг атаки Куртуа состоит в использовании программно-алгебраических методов извлечения ключа из последних раундов. На конференцию CRYPTO 2011 работа Куртуа принята не была. Короткий анонс на Rump Session сделала группа исследователей во главе с Ади Шамиром. Работа группы Шамира была опубликована в октябре 2011 года. В ней были использованы другие методы на последнем шаге, что по мнению Куртуа свидетельствует о независимом подтверждении не единственной, а множественной дефектности структуры шифра ГОСТ, которая может быть подвержена ряду атак различного типа.

Автор непосредственно сам в своей работе характеризует её как "важную как в научном, так и в историческом смысле". За двадцать лет существования международного комитета по стандартизации ISO в качестве кандидатов рассматривались лишь менее десяти блочных шифров с достаточным уровнем безопасности, при этом ГОСТ был внесён кандидатом в 2010 году и до 2011 ни у кого не было ни малейших сомнений в его безопасности.

Также практически никто в криптографическом сообществе не рассматривал всерьёз идею о широком распространении программно-алгебраических атак (одним из первооткрывателей которых был Николя Куртуа), которые могли бы взломать (быстрее атак грубой силой) реально применяемый шифр, сертифицированный для правительственного и военного использования или для безопасности интернета. ГОСТ является именно таким шифром (в отличие от DES и ближе к стандарту AES).

Алгебраический криптоанализ основан на построении и нахождении программного решения системы булевых алгебраических уравнений, описывающих геометрию и структуру шифра. И хотя автору не удалось применить его в полной мере, возможность раздельных атак на разные раунды шифра позволила эффективно использовать его на последних шагах.

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

Все эти атаки не позволяют расшифровывать данные перехваченных коммуникаций, но Куртуа пытается привести аргументы в пользу того, что они имеют не только чисто научный интерес. Он ссылается на широко распространённое мнение (без указания конкретных источников) о том, что во многих приложениях реально используемый ГОСТ является ослабленным. В качестве примера такой возможности он приводит атаки на класс 128-битных ключей "семейства B", на которые ему удалось представить взлом за 2³⁵ подобранных открытых текстов за время 2⁸¹. Также среди множества случайно сгенерированных ключей вероятность получения слабого ключа оценивается им выше, чем это считалось ранее, включая возможность нахождения такого ключа в реальном использовании.

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

Источник: Cryptology ePrint Archive

См. также:
Улучшенная атака на полнораундовый ГОСТ 28147-89, Показан первый концептуальный взлом ГОСТ 28147-89 путём дифференциального криптоанализа, Сообщения о взломе блочного шифра ГОСТ 28147-89 в разгар усилий по его международной стандартизации, Первая атака на функцию хэширования ГOСТ-Р 34.11-94, Рефлективные атаки понижают стойкость шифра ГОСТ.