Исследователи выявили возможный бэкдор в алгоритмах «Кузнечик» и «Стрибог»

Недавние алгоритмы ГОСТ «Кузнечик» и «Стрибог» могут содержать бэкдоры. К такому выводу пришел французский исследователь безопасности Лео Перрен (Léo Perrin) по результатам проведенного им криптоанализа.

Как сообщается в отчете исследователя, «Кузнечик» и «Стрибог» имеют один и тот же S-блок (таблицу подстановок), π, процесс разработки которого не был описан авторами алгоритмов. В предыдущих работах Перрен вместе с Алексом Бирюковым и Алексеем Удовенко восстановили две совершенно разные декомпозиции этого S-блока. Теперь полученные исследователями результаты были пересмотрены, что позволило выявить третью декомпозицию π.

S-блок является ключевой функцией для обеспечения безопасности многих алгоритмов шифрования. В таблице подстановок одна последовательность битов сопоставляется с другой по определенному принципу. По словам авторов «Кузнечика» и «Стрибога», таблица подстановок была выбрана ими случайным образом, то есть, ее структура не позволяет провести криптоанализ.

Тем не менее, как оказалось, таблица была сгенерирована отнюдь не случайным образом. Авторы «Кузнечика» и «Стрибога» использовали алгоритм, раскрытый Перреном, Бирюковым и Удовиченко еще в 2015 году. Более того, для генерирования таблицы они воспользовались сразу двумя алгоритмами.

Исследователи назвали выявленную ими конструкцию перестановки TKlog в честь российского технического комитета по стандартизации, разработавшего алгоритмы «Кузнечик» и «Стрибог». Главной особенностью TKlog является использование дискретного логарифмирования наподобие асимметричного шифрования. Поскольку разных вариантов преобразования TKlog очень мало, исследователи предположили, что подобная неслучайная структура была выбрана авторами алгоритмов осознанно.

Ключевое свойство преобразования TKlog – работа со смежными классами (cosets), сопоставляемыми один с другим. В функции замены блочных шифров добавочные смежные классы использовались пока только в одном случае – для создания бэкдоров. Подобные бэкдоры получили название «NOBUS» («Nobody But Us» – «Никто кроме нас»), поскольку могут использоваться только самими авторами алгоритмов.

Согласно отчету Перрена, никакой информации об эксплуатации возможных бэкдоров на данный момент нет. Тем не менее, непонятно, зачем авторы алгоритмов заявили об использовании якобы случайным образом сгенерированной таблицы, когда все обстоит совсем иначе.