openPGP в России

16.10 // Интегральный криптоанализ хэш-функции ГОСТ Р 34.11-2012 Стрибог

Хэш-функция «Стрибог» с размером выхода 512/256 бит стала новым официальным российским стандартом, заменившим в 2013 году старый, теоретически взломанный ГОСТ Р 34.11-94 и была заявлена, как асимметричный ответ на SHA-3.

В основу данной функции положен 12-раундовый AES-подобный шифр с размером внутреннего состояния 8x8 байтов, предваряемый одним раундом нелинейного отбеливания в режиме сцепления. Функция сжатия работает в режиме Миагучи-Пренеля и внесена в расширенную область значений путём выполнения инструкции Меркла-Дамгарда на конечном шаге.

В связи с тем, что в основе хэш-функции лежит блочный шифр с известным ключом, то как и при любой другой конструкции хэш-функции противнику известны все её внутренние состояния на каждом раунде. В связи с этим, нахождение любого различителя внутреннего шифра в модели с известным ключом, а в последствии различителя для функции сжатия с этим шифром, может быстро привести к атаке.

Для нахождения различителей в шифрах такого рода логично попытаться применить интегральный криптоанализ. Он является противоположностью по отношению к дифференциальному. Если в дифференциальном криптоанализе изучается прохождение разности пар для получения наиболее вероятного дифференциала, то в интегральном криптоанализе (впервые предложенном Вагнером и Кнудсеном) изучается прохождение сумм множества значений для получения определённых интегралов. Этот криптоанализ был специально разработан против шифров с биективными преобразованиями, которые проще создать устойчивыми к дифференциальному криптоанализу. Интеграл — это набор значений с определёнными суммами на входе и на выходе. Он показывает как при прохождении множества раундов шифра свойства суммирования меняются на каждом раунде.

Интегральный криптоанализ был успешно опробован против AES. В обобщённом виде под именем насыщающего анализа он был ранее опробован против Twofish, а в виде частного случая на атаках с нулевой суммой — против алгоритма SHA3/Keccak.

Исследователи Riham AlTawy и Amr M. Youssef из университета Конкордия (Монреаль, Канада) смогли найти 4-раундовый прямой и 3.5-раундовый обратный интегральный различитель для функции сжатия Stribog. Используя атаки старта посредине и комбинацию двух найденных интегралов, им удалось найти 6.5 и 7.5-раундовый различитель для внутренней перестановки и 6 и 7-раундовый различитель для функции сжатия. Атака нахождения различителя на неполнораундовый Стрибог требует в разных вариантах от 2⁶⁴ до 2¹²⁰ входных или среднераундовых значений.

Этот результат приблизительно сравним с последними известными атаками на Keccak, но даже о его теоретическом значении на будущее говорить пока рано: хотя у Keccak есть запас прочности из-за вдвое большего числа раундов, но сравнивать конструкции этих функций достаточно трудно.

Источник: Cryptology ePrint Archive^[link1]