Стрибог

Streebog ( русский : Стрибог ) — криптографическая хэш-функция, определённая в российском национальном стандарте ГОСТ Р 34.11-2012 Информационные технологии — Криптографическая защита информации — Хэш-функция . Она была создана для замены устаревшей хэш-функции ГОСТ, определённой в старом стандарте ГОСТ Р 34.11-94, и как асимметричный ответ на конкуренцию SHA-3 со стороны Национального института стандартов и технологий США . ^[2] Функция также описана в RFC 6986 и является одной из хэш-функций в ISO/IEC 10118-3:2018. ^[3]

Streebog оперирует 512-битными блоками входных данных, используя конструкцию Меркла–Дамгарда для обработки входных данных произвольного размера. ^[4]

Высокоуровневая структура новой хэш-функции напоминает структуру из ГОСТ Р 34.11-94, однако функция сжатия была существенно изменена. ^[5] Функция сжатия работает в режиме Миягучи–Пренеля и использует 12-раундовый шифр типа AES с 512-битным блоком и 512-битным ключом. (Она использует матрицу байтов 8×8 вместо матрицы AES 4×4.)

Streebog-256 использует другое начальное состояние, чем Streebog-512, и обрезает выходной хеш, но в остальном идентичен.

Функция была названа Стрибог в честь Стрибога , бога стремительного ветра в древнеславянской мифологии, ^[2] и часто упоминается под этим именем, хотя оно явно не упоминается в тексте стандарта. ^[6]

Хэш-значения пустой строки.

Стрибог-256("")0x 3f539a213e97c802cc229d474c6aa32a825a360b2a933a949fd925208d9ce1bbСтрибог-512("")0x 8e945da209aa869f0455928529bcae4679e9873ab707b55315f56ceb98bef0a7 \ 362f715528356ee83cda5f2aac4c6ad2ba3a715c1bcd81cb8e9f90bf4c1c1a8a

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

Streebog-256(" Быстрая коричневая лиса перепрыгивает через ленивую собаку ")0x 3e7dea7f2384b6c5a3d0e24aaa29c05e89ddd762145030ec22c71a6db8b2c1f4Streebog-256(" Быстрая коричневая лиса перепрыгивает через ленивую собаку .")0x 36816a824dcbe7d6171aa58500741f2ea2757ae2e1784ab72c5c3c6c198d71daStreebog-512(" Быстрая коричневая лиса перепрыгивает через ленивую собаку ")0x d2b793a0bb6cb5904828b5b6dcfb443bb8f33efc06ad09368878ae4cdc8245b9 \ 7e60802469кровать1e7c21a64ff0b179a6a1e0bb74d92965450a0adab69162c00feStreebog-512(" Быстрая коричневая лиса перепрыгивает через ленивую собаку .")0x fe0c42f267d921f940faa72bd9fcf84f9f1bd7e9d055e9816e4c2ace1ec83be8 \ 2d2957cd59b86e123d8f5adee80b3ca08a017599a9fc1a14d940cf87c77df070

В 2013 году Российский технический комитет по стандартизации «Криптография и защитные механизмы» (ТК 26) при участии Академии криптографии Российской Федерации объявил открытый конкурс на криптоанализ хэш-функции Стрибог ^[7] , что привлекло к функции международное внимание.

Ma и др . описывают атаку на прообраз , которая занимает 2 ⁴⁹⁶ времени и 2 ⁶⁴ памяти или 2 ⁵⁰⁴ времени и 2 ¹¹ памяти для нахождения одного прообраза ГОСТ-512, сокращенного до 6 раундов. ^[8] В той же статье они также описывают атаку на коллизию со сложностью по времени 2 ¹⁸¹ и требуемой памятью 2 ^{64 .}

Го и др . описывают вторую атаку на основе прообраза для полного Streebog-512 с общей временной сложностью, эквивалентной 2 ²⁶⁶ оценкам функции сжатия, если сообщение содержит более 2 ²⁵⁹ блоков. ^[1]

AlTawy и Youssef опубликовали атаку на модифицированную версию Streebog с другими раундовыми константами. ^[9] Хотя эта атака, возможно, не оказывает прямого влияния на безопасность исходной хэш-функции Streebog, она поднимает вопрос о происхождении используемых в функции параметров. Разработчики опубликовали статью, в которой объясняют, что это псевдослучайные константы, сгенерированные с помощью хэш-функции, подобной Streebog, снабженной 12 различными входными сообщениями на естественном языке. ^[10]

AlTawy и др . обнаружили 5-раундовую коллизию свободного старта и 7,75-раундовую близкую коллизию свободного старта для внутреннего шифра со сложностью 2 ⁸ и 2 ⁴⁰ соответственно, а также атаки на функцию сжатия с 7,75-раундовой коллизией полусвободного старта со сложностью по времени 2 ¹⁸⁴ и сложностью по памяти 2 ⁸ , 8,75 и 9,75-раундовой близкой коллизией полусвободного старта со сложностью по времени 2 ¹²⁰ и 2 ¹⁹⁶ соответственно. ^[11]

Ванг и др . описывают атаку коллизий на функцию сжатия, сокращенную до 9,5 раундов со сложностью по времени 2 ¹⁷⁶ и сложностью по памяти 2 ^{128. [12]}

В 2015 году Бирюков, Перрен и Удовенко провели обратную разработку неопубликованной структуры генерации S-box (которая, как ранее утверждалось, генерируется случайным образом) и пришли к выводу, что ее базовые компоненты криптографически слабы. ^[13]

• Резюме безопасности хэш-функции