Привет, %username%!
Криптографические алгоритмы в России не проходят через открытые конкурсы, их просто спускают нам свыше. И рано или поздно это сильно нам аукнется. Эта статья об очередном исследовании наших ГОСТов.
В 2016м году исследователи показали, что таблица перестановки в российских алгоритмах хеширования и шифрования Кузнечик и Стрибог имеет структуру, сильно далёкую от случайной. Это уже после того, как в Стрибоге была найдена тривиальная ошибка, уменьшающая его стойкость с 2512 до 2266.
29 января 2019 года была опубликовано новое исследование «Partitions in the S-Box of Streebog and Kuznyechik», которое недвусмысленно намекает на теоретическую возможность бекдора в этих алгоритмах.
Итак, S-Box — или таблица замены, является ключевым элементом безопасности во многих алгоритмах симметричного шифрования и хеширования. Пример такой таблицы приведен на рисунке.
В общем случае эта таблица сопоставляет одной последовательности бит другую. А вот по какому принципу — всегда большой вопрос.
Государственные структуры нередко ограничиваются их публикацией без какого либо рационального объяснения. В случае с DES АНБ предложило изменить S-Box до того как алгоритм стал стандартом. Только через много лет выяснилось, что это изменение на самом деле повышало стойкость DES к дифференциальному криптоанализу.
В случае с новыми ГОСТами не всё так радужно. Авторы декларировали, что таблица замен выбрана случайным образом. Вот слайд из презентации алгоритма, на котором указано, что авторы выбирали таблицу случайным образом. Так, чтобы у неё не было явной структуры, которая помогла бы произвести эффективный криптоанализ.
Вот эта таблица
Но, во-первых, как оказалось, она сгенерирована не случайным образом, а с помощью хитрого алгоритма, который расковыряли еще в 2015м.
Во-вторых, авторы не оставили попыток выяснить причину такого подхода к конструированию S-Box и натолкнулись на очень интересные результаты.
Оказалось, что алгоритмов, которые формируют таблицу замены, больше чем один. Разные группы исследователей описали абсолютно разные алгоритмы, которые не имеют почти ничего общего, но приходят к одной и той же таблице.
Это навело авторов оригинального исследования на мысль покопаться в структуре этих алгоритмов поглубже и найти общие элементы, что им с успехом удалось.
TKlog
TKlog — конструкция перестановки, которую авторы криптоанализа назвали в честь российской конторы ТК-26, где и были созданы Кузнечик со Стрибогом. Её описание сильно выходит за рамки данной статьи, желающие могут обратиться к оригиналу. Если в двух словах, то её ключевым свойством является использование дискретного логарифмирования, прям как в асимметричной криптографии.
Что важно, так это тот факт, что оба варианта функции замены из ГОСТовских алгоритмов являются частным случаем конструкции TKlog. Как и еще одна функция замены из белорусского алгоритма BelT. Функции разные, но сводятся к одной.
Тот факт, что разных вариантов преобразования TKlog крайне мало, говорит о преднамеренном использовании именно этой, нерандомизированной структуры вместо случайной, показанной нам на слайде.
Разбиения на сомножества
Ключевым свойством преобразования TKlog является то, что оно работает с так называемыми сомножествами (cosets). И сопоставляет одни сомножества другим.
Проблема в том, что эти сомножества бывают мультипликативными, как во всех обычных алгоритмах. А бывают аддитивными.
Так вот, единственный известный случай, когда аддитивные сомножества использовались в функции замены блочных шифров — специальное создание бекдора. Информация об этом находится в работе 2016 года.
Такие бекдоры называются NOBUS, сокр. от «NObody But US», это уязвимости, которые могут эксплуатировать только сами авторы алгоритмов.
Вместо заключения
Авторы криптоанализа не представили новых атак на существующие алгоритмы ГОСТ, но задались справедливым вопросом целесообразности всего этого цирка с якобы случайной таблицей перестановки.
АНБ не так давно попыталось протолкнуть в стандарты свои легковесные симметричные алгоритмы Simon и Speck. И самого факта наличия таблиц замены с дизайном, описания которого предоставлено не было, хватило чтобы их отовсюду прогнали ссаными тряпками.
У нас такой возможности нет.
Автор: Scratch
