30.10 // Следите за константами: как в хэш-функции Стрибог можно спрятать бэкдор

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

Опасения такого рода только усилились после раскрытия Эдвардом Сноуденом программы Bullrun, которая указывала на то, что агентство национальной безопасности США умышленно внесло бэкдор в стандарт генератора псевдослучайных чисел на эллиптических кривых Dual_EC_DRBG, позволяющий по фрагментам гаммы раскрывать внутреннее состояние генератора. Предполагается, что за внедрение этого алгоритма в библиотеку RSA BSAFE фирма RSA Security получила от АНБ сумму в 10 миллионов долларов в ходе секретной сделки, немотря на то, что в ходе появления рекомендации от Национального института стандартов и технологий (NIST) возникли опасения, что стандарт подвергался злонамеренным манипуляциям со стороны АНБ в области подбора констант эллиптических кривых.

Ранее были немногочисленные исследования о создании алгоритмов с бэкдорами: были описаны теоретические возможности построения злонамеренных шифров CAST и LOKI, а впоследствии и хэш-функции SHA-1.

В 2010 году была предложена хэш-функция Стрибог, которая стала российским стандартом хэширования, что было отражено в стандарте IETF. В отличие от открыто разрабатываемых хэш-функций, в стандарте ГОСТ на хэширование не были обоснованы ни выбор функций, ни выбор множества случайно выглядящих констант, ни количество раундов. Это позволило исследователям Riham AlTawy и Amr M. Youssef из института разработки систем безопасности Университета Конкордиа (Монреаль, Квебек, Канада) разработать прототип методики секретного внедрения бэкдора в Стрибог.

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

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

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

См. также: Ошибка в структуре российской хэш-функции Stribog привела к её полнораундовому взлому, Интегральный криптоанализ хэш-функции ГОСТ Р 34.11-2012 Стрибог, STRIBOB: шифрование с аутентификацией на основе стандарта российской хэш-функции.