Главная » Хабрахабр » Очередные странности в алгоритмах ГОСТ Кузнечик и Стрибог

Очередные странности в алгоритмах ГОСТ Кузнечик и Стрибог

Привет, %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, где и были созданы Кузнечик со Стрибогом. Её описание сильно выходит за рамки данной статьи, желающие могут обратиться к оригиналу. Если в двух словах, то её ключевым свойством является использование дискретного логарифмирования, прям как в асимметричной криптографии.

Как и еще одна функция замены из белорусского алгоритма BelT. Что важно, так это тот факт, что оба варианта функции замены из ГОСТовских алгоритмов являются частным случаем конструкции TKlog. Функции разные, но сводятся к одной.

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

Разбиения на сомножества

Ключевым свойством преобразования TKlog является то, что оно работает с так называемыми сомножествами (cosets). И сопоставляет одни сомножества другим.

А бывают аддитивными. Проблема в том, что эти сомножества бывают мультипликативными, как во всех обычных алгоритмах.

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

от «NObody But US», это уязвимости, которые могут эксплуатировать только сами авторы алгоритмов. Такие бекдоры называются NOBUS, сокр.

Вместо заключения

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

И самого факта наличия таблиц замены с дизайном, описания которого предоставлено не было, хватило чтобы их отовсюду прогнали ссаными тряпками. АНБ не так давно попыталось протолкнуть в стандарты свои легковесные симметричные алгоритмы Simon и Speck.

У нас такой возможности нет.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Язык Bosque — новый язык программирования от Microsoft

Языку дали название Bosque. Буквально несколько дней назад компания Microsoft представила публике новый язык программирования. Главная миссия дизайна языка — лучше быть богатым и здоровым, чем бедным и больным чтобы он был прост и понятен как для человека, так и ...

Как не слить 10 миллионов бюджета вашего заказчика, играясь с Agile

В этом посте я расскажу о тех проблемах с которыми в течении года сталкивалась наша Scrum Front End команда при работе над приличным проектом. Мы начинали разрабатывать проект с нуля используя стек технологий React + Typescript. Оглядываясь назад я вижу ...