Стрибог (хеш-функция)
Стрибог | |
---|---|
Разработчики |
ФСБ России, ОАО «ИнфоТеКС» |
Опубликован | 2012 |
Стандарты | ГОСТ 34.11-2018, ГОСТ Р 34.11-2012, ИСО/МЭК 10118-3:2018, RFC 6986 |
Размер хеша | 256 или 512 бит |
Число раундов | 12 |
Тип | хеш-функция |
«Стрибог» (англ. STREEBOG[1]) — криптографический алгоритм вычисления хеш-функции с размером блока входных данных 512 бит и размером хеш-кода 256 или 512 бит.
Описывается в ГОСТ 34.11-2018 «Информационная технология. Криптографическая защита информации. Функция хэширования» — действующем межгосударственном криптографическом с��андарте.
Разработан Центром защиты информации и специальной связи ФСБ России с участием ОАО «ИнфоТеКС» на основе национального стандарта Российской Федерации ГОСТ Р 34.11-2012 и введен в действие с 1 июня 2019 года приказом Росстандарта № 1060-ст от 4 декабря 2018 года.
Стандарт ГОСТ Р 34.11-2012 разработан и введён в качестве замены устаревшему стандарту ГОСТ Р 34.11-94:
Необходимость разработки <…> вызвана потребностью в создании хэш-функции, соответствующей современным требованиям к криптографической стойкости и требованиям стандарта ГОСТ Р 34.10-2012 на электронную цифровую подпись.
— Текст стандарта. Введение.
Название хеш-функции — «Стрибог», по имени славянского божества, — часто используется вместо официального названия стандарта, хотя в его тексте явно не упоминается (см. ниже).
Концепции построения хэш-функции «Стрибог»
[править | править код]В соответствии с требованиями, высказанными на конференции РусКрипто-2010, в работе, посвящённой новой хеш-функции[2]:
- у новой хеш-функции не должно быть свойств, которые позволяли бы применить известные атаки;
- в хеш-функции должны использоваться изученные конструкции и преобразования;
- вычисление хеш-функции должно быть эффективным, занимать мало времени;
- не должно быть лишних преобразований, усложняющих конструкцию хеш-функции. Причем каждое используемое в хеш-функции преобразование должно отвечать за определённые криптографические свойства.
В той же работе вводятся «универсальные» требования, касающиеся трудоемкости атак на хеш-функцию:
Задача | Сложность |
построение прообраза | 2n |
построение коллизии | 2n/2 |
построение второго прообраза | 2n/(длина сообщения) |
удлинение прообраза | 2n |
Сравнение ГОСТ Р 34.11-2012 и ГОСТ Р 34.11-94
[править | править код]- В ГОСТ Р 34.11-2012 размер блоков сообщения и внутреннего состояния хеш-функции составляет 512 бит против 256 бит в ГОСТ Р 34.11-94.
- Новый стандарт определяет две функции хеширования с длинами хеш-кода 256 и 512 бит, в то время как в старом стандарте длина хеш-кода может быть только 256 бит. Возможность вариации выходного хеша может быть полезна в случае встроенных реализаций с ограниченными ресурсами или наличия каких-то дополнительных требований в области криптографии.
- Основное отличие современной хеш-функции от старой — функция сжатия. В ГОСТ Р 34.11-2012 используется функции сжатия, в основе которой лежат три преобразования: нелинейное биективное преобразование (обозначается S), перестановка байт (обозначается P), линейное преобразование (обозначается L). В ГОСТ Р 34.11-94 используется функция сжатия, основанная на симметричном блочном шифре ГОСТ Р 28147-89, также эта функция использует операции перемешивания.
- При вычислении новой хеш-функции, если размер сообщения не кратен размеру обрабатываемого блока (для современного стандарта — 512 бит, для старого стандарта — 256 бит), то такой блок дополняется вектором (00 … 01). При вычислении старой хеш-функции неполный блок дополняется значением (00 … 0). Считается, что дополнение (00 … 01) лучше, чем (00 … 0), с криптографической точки зрения, так как дополнения значением (00 … 0) приводит к атакам Оракула дополнения[3]. В случае ненулевого дополнения была доказана стойкость к подобным атакам[4].
- Ещё одно отличие состоит в том, что стандарт ГОСТ Р 34.11-94 не определял значение инициализационного вектора, в то время как в стандарте ГОСТ Р 34.11-2012 значение инициализационного вектора фиксировано и определено в стандарте: для хеш-функции с размером выходного хеша 512 бит это вектор (00 … 0), для хеш-функции с размером выходного хеш-кода 256 бит — (000000010 … 100000001) (все байты равны 1).
Функция сжатия
[править | править код]В хеш-функции важным элементом является функция сжатия. В ГОСТ Р 34.11-2012 функция сжатия основана на конструкции Миагути — Пренеля. Схема конструкции Миагути — Пренеля: h, m — вектора, поступающие на вход функции сжатия; g(h, m) — результат функции сжатия; E — блочный шифр с длиной блока и ключа 512 бит. В качестве блочного шифра в хеш-функции ГОСТ Р 34.11-2012 взят XSPL-шифр. Этот шифр состоит из следующих преобразований:
- сложение по модулю 2;
- преобразование замены или подстановки. Обозначается S-преобразование;
- преобразование перестановки. Обозначается P-преобразование;
- линейное преобразование. Обозначается L-преобразование.
Преобразования, используемые в новой хеш-функции, должны быть хорошо изучены. Поэтому в блочном шифре E используются преобразования X, S, P, L, которые хорошо изучены.
Важным параметром блочного шифра является то, как выбирается ключ, который будет использовать на каждом раунде. В блочном шифре, используемом в ГОСТ Р 34.11-2012, ключи , , … , для каждого из 13 раундов генерируются с помощью самой функции шифрования.
, , … , — итерационные константы, которые являются 512 битовыми векторам. Их значения указаны в соответствующем разделе стандарта.
Описание
[править | править код]В основу хеш-функции положена итерационная конструкция Меркла — Дамгора с использованием MD-усиления. Под MD-усилением понимается дополнение неполного блока при вычислении хеш-функции до полного путём добавления вектора (0 … 01) такой длины, чтобы получился полный блок. Из дополнительных элементов нужно отметить следующие:
- завершающее преобразование, которое заключается в том, что функция сжатия применяется к контрольной сумме всех блоков сообщения по модулю 2512;
- при вычислении хеш-кода на каждой итерации применяются разные функции сжатия. Можно сказать, что функция сжатия зависит от номера итерации.
Описанные выше решения позволяют противостоять многим известным атакам.
Кратко описание хеш-функции ГОСТ Р 34.11-2012 можно представить следующим образом. На вход хеш-функции подается сообщение произвольного размера. Далее сообщение разбивается на блоки по 512 бит, если размер сообщения не кратен 512, то оно дополняется необходимым количеством бит. Потом итерационно используется функция сжатия, в результате действия которой обновляется внутреннее состояние хеш-функции. Также вычисляется контрольная сумма блоков и число обработанных бит. Когда обработаны все блоки исходного сообщения, производятся ещё два вычисления, которые завершают вычисление хеш-функции:
- обработка функцией сжатия блока с общей длиной сообщения.
- обработка функцией сжатия блока с контрольной суммой.
В работе Александра Казимирова и Валентины Казимировой[5] приведена графическая иллюстрация вычисления хеш-функции.
Анализ
[править | править код]Криптостойкость
[править | править код]Криптоанализ старого стандарта выявил некоторые его слабые стороны с теоретической точки зрения. Так в одной из работ[6], посвящённых криптоанализу ГОСТ Р 34.11-94, было выявлено, что сложность алгоритма построения прообраза оценивается в 2192 вычислений функций сжатия, коллизии 2105, что меньше «универсальных» оценок, которые для ГОСТ Р 34.11-94 равны 2256 и 2128. Хотя по состоянию на 2013 год нет большого числа работ, посвящённых криптостойкости новой хеш-функции, исходя из конструкции новой хеш-функции, можно сделать некоторые выводы о её криптостойкости и предположить[источник не указан 3058 дней], что её криптостойкость будет выше, чем у ГОСТ Р 34.11-94:
- в разделе «Описание» из схемы видно, что все блоки сообщения суммируются по модулю 2512 и уже результат суммирования всех блоков подается на вход завершающего этапа (stage3). Благодаря тому, что здесь суммирование — это не побитовое сложение, получается защита от следующих атак:
- построение мультиколлизий;
- удлинение прообраза;
- дифференциальный криптоанализ;
- в функции сжатия используется конструкция Миагути — Пренели, это обеспечивает защиту от атаки, основанную на фиксированных точках, так как для конструкции Миагути — Пренели не найдено лёгких способов для поиска фиксированных точек;
- на каждой итерации при вычислении хеш-кода используются различные константы. Это затрудняет атаки на основе связанных и разностных связанных ключей, атаки скольжения и отражения.
В 2013 году на сайте «Cryptology ePrint Archive: Listing for 2013» было опубликовано две статьи, посвящённых криптоанализу новой хеш-функции. В статье «Rebound attack on Stribog»[7] исследуется устойчивость хеш-функции по отношению к атаке, называемой «The Rebound attack»; в основе этой атаки лежит «rotation cryptanalysis» и дифференциальный криптоанализ. Криптоаналитики при поиске уязвимостей использовали метод, называемый «free-start». Это означает, что при вычислении хеш-кода фиксируется некоторое состояние хеш-функции и дальше вычисления могут идти как в сторону вычисления хеш-кода, так и в сторону вычисления сообщения. Криптоаналитики сумели добиться коллизии за 5 раундов и была получена так называемая «near collision» (это означает, что были найдены два сообщения, хеш-коды которых отличны в малом количестве бит) при использовании 7,75 раунда. Также было установлено, что схема, по которой выбираются ключи для каждого раунда, добавляет устойчивости функции сжатия. ��днако было показано, что коллизия возможна за 7,75 раунда, а «near collision» — за 8,75 и 9,75, соответственно.
В статье «Integral Distinguishers for Reduced-round Stribog»[8] рассматривается стойкость хеш-функции (с уменьшенным количеством раундов) по отношению к интегральному криптоанализу. Авторами при исследовании функции сжатия удалось найти дифференциал за 4 раунда при вычислении в прямом направлении и за 3,5 раунда при вычислении в обратном направлении. Также было выяснено, что атака нахождения дифференциала на хеш-функцию с числом раундов 6 и 7 требует 264 и 2120 среднераундовых значений, соответственно.
Для изучения криптостойкости новой хеш-функции компания «ИнфоТеКС» в ноябре 2013 года объявила о старте конкурса[9]; он завершился в мае 2015 года[10]. Победителем стала работа «The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function», в которой авторы представили атаку нахождения второго прообраза для хеш-функции «Стрибог-512», требующую 2266 вызовов функции сжатия для сообщений длиннее 2259 блоков[11].
На конференции Crypto-2015 Алекс Бирюков, Лео Перрин и Алексей Удовенко представили доклад, в котором говорится о том, что значения S-блока шифра «Кузнечик» и хеш-функции Стрибог не являются (псевдо)случайными числами, а сгенерированы на основе скрытого алгоритма, который докладчикам удалось восстановить методами обратного проектирования[12][13].
29 января 2019 года была опубликовано исследование «Partitions in the S-Box of Streebog and Kuznyechik»[14], которое опровергает заявление авторов о случайном выборе параметров таблиц замен в алгоритмах Стрибог и Кузнечик[15].
Быстродействие
[править | править код]На сайте, посвящённом VI Международной конференции «Параллельные вычисления и задачи управления» (PACO’2012), представлена статья П. А. Лебедева «Сравнение старого и нового стандартов РФ на криптографическую хеш-функцию на ЦП и графических процессорах NVIDIA», в которой проводится сравнение быстродействия семейства криптографических хеш-функций ГОСТ Р 34.11-94 и ГОСТ Р 34.11-2012 на процессорах архитектуры x86_64 и видеокартах NVIDIA с поддержкой технологии CUDA[16].
Для сравнения быстродействия на процессоре архитектуры x86_64 были взяты 4 разных реализации хеш-функций:
- реализация ГОСТ Р 34.11-1994 из криптографического пакета OpenSSL (версия 1.0.1c) с открытым исходным кодом. В этой реализации нет алгоритмических и программных оптимизаций;
- реализация ГОСТ Р 34.11-1994 в программе RHash (версия 1.2.9). В этой реализации есть алгоритмические и программные оптимизации, в том числе ассемблерные оптимизации;
- реализация ГОСТ Р 34.11-2012, написанная А. Казимировым[17];
- реализации ГОСТ Р 34.11-1994 и ГОСТ Р 34.11-2012, написанные П. А. Лебедевым.
Использовался процессор Intel Core i7-920 CPU на базовой частоте 2,67 ГГц. Результаты производительности:
ГОСТ Р 34.11-1994 | ГОСТ Р 34.11-2012 | |||
---|---|---|---|---|
Реализация № | МБ/с | Тактов/байт | МБ/с | Тактов/байт |
1 | 18 | 143 | - | - |
2 | 49 | 52 | - | - |
3 | - | - | 38 | 67 |
4 | 64 | 40 | 94 | 27 |
Сравнение быстродействия старого и нового стандартов хеш-функций на GPU проводилось между реализациями П. А. Лебедева. Использовалась видеокарта NVIDIA GTX 580. Результаты производительности (8192 потока данных по 16 КБ):
ГОСТ Р 34.11-1994 | ГОСТ Р 34.11-2012 | ||
---|---|---|---|
МБ/с | Тактов/байт | МБ/с | Тактов/байт |
1697 | - | 608 | - |
На основании этих результатов сделан вывод, что хеш-функция ГОСТ Р 34.11-2012 может быть в два раза быстрее хеш-функции ГОСТ Р 34.11-94 на современных процессорах, но медленнее на графических картах и системах с ограниченными ресурсами.
Такие результаты производительности можно объяснить тем, что при вычислении новой хеш-функции используются только сложения по модулю 2 и ин��трукции пересылки данных. Старая хеш-функции содержит много инструкций перемешивания, которые не лучшим образом отображаются на набор команд ЦП. Но увеличенный размер состояний и таблиц подстановки хеш-функции ГОСТ Р 34.11-2012 делает её медленней на высокопараллельных вычислительных средствах, таких как графические процессоры.
Также исследование производительности новой хеш-функции было проведено её разработчиками на 64-битном процессоре Intel Xeon E5335 2 ГГц. Использовалось одно ядро. Производительность хеш-функции ГОСТ Р 34.11-2012 составила 51 такт процессора на 1 байт хешируемых данных (примерно 40 MБ/с). Полученный результат на 20 % лучше, чем у старой хеш-функции ГОСТ Р 34.11-94.
Интересные факты
[править | править код]В конце текста стандарта приведены примеры пошагового вычисления хеша для нескольких исходных значений. Одно из таких значений — шестнадцатеричное число M2 длины 576 бит (72 байта) из примера 2:
fbe2e5f0eee3c820fbeafaebef20fffbf0e1e0f0f520e0ed20e8ece0ebe5f0f2f120fff0
eeec20f120faf2fee5e2202ce8f6f3ede220e8e6eee1e8f0f2d1202ce8f0f2e5e220e5d1
На ЭВМ архитектуры x86 используется порядок байт от младшего к старшему, и подобное число в памяти будет представлено в «перевёрнутом» виде. Если преобразовать этот массив байт в текст в кодировке Windows-1251, то получится немного изменённая строчка из Слова о полку Игореве:
Се ветри, Стрибожи внуци, веютъ с моря стрелами на храбрыя плъкы Игоревы
В ответ на критическую статью «Watch your Constants: Malicious Streebog»[18] комитет ТК26 выпустил заметку «Об алгоритме выработки констант функции хэширования „Стрибог“» [19] [20] в которой пояснено, что константы раундовых ключей строились как преобразование входных строк с помощью «Стрибог»-подобной хэш функции. Если преобразовать эти входные строки в текст в кодировке Windows-1251, то получатся имена авторов стандарта:
Ci = Hinit(M) | M (в шестнадцатеричной записи) | Mcp1251 (строка в Windows-1251) |
C1 | e2e5ede1e5f0c3 | Гребнев |
C2 | f7e8e2eef0e8ece8e4e0ebc220e9e5e3f0e5d1 | Сергей Владимирович |
C3 | f5f3ecc4 | Дмух |
C4 | f7e8e2eef0e4ede0f1eae5ebc020e9e5f0e4edc0 | Андрей Александрович |
C5 | ede8e3fbc4 | Дыгин |
C6 | f7e8e2eeebe9e0f5e8cc20f1e8ede5c4 | Денис Михайлович |
C7 | ede8f5fef2e0cc | Матюхин |
C8 | f7e8e2eef0eef2eae8c220e9e8f0f2e8ecc4 | Дмитрий Викторович |
C9 | e9eeeaf1e4f3d0 | Рудской |
C10 | f7e8e2e5f0eee3c820f0e8ece8e4e0ebc2 | Владимир Игоревич |
C11 | ede8eaf8e8d8 | Шишкин |
C12 | f7e8e2e5e5f1eae5ebc020e9e8ebe8f1e0c2 | Василий Алексеевич |
Применение
[править | править код]Алгоритм используется в реализации ДЭГ на выборах президента России.[21]
Примечания
[править | править код]- ↑ 17. Dedicated Hash-Function 11 (STREEBOG-512) Архивная копия от 22 января 2020 на Wayback Machine // ISO/IEC 10118-3:2018 IT Security techniques — Hash-functions — Part 3: Dedicated hash-functions.
- ↑ Матюхин Д. В., Шишкин В. А., Рудский В. И. Перспективный алгоритм хеширования // Доклад на конференции РусКрипто’2010, 2010.
- ↑ Serge Vaudenay (2002). «Security Flaws Induced by CBC Padding Applications to SSL, IPSEC, WTLS…». Advances in Cryptology — EUROCRYPT 2002, Proc. International Conference on the Theory and Applications of Cryptographic Techniques. Springer Verlag (2332): 534—545.
- ↑ Kenneth G. Paterson; Gaven J. Watson (2008). «Immunising CBC Mode Against Padding Oracle Attacks: A Formal Security Treatment». Security and Cryptography for Networks — SCN 2008, Lecture Notes in Computer Science. Springer Verlag (5229): 340—357.
- ↑ Источник . Дата обращения: 1 декабря 2013. Архивировано 3 декабря 2013 года.
- ↑ «F. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, J. Szmidt» CRYPTO 2008
- ↑ Riham AlTawy, Aleksandar Kircanski and Amr M. Youssef. Rebound attacks on Stribog (англ.) (27 августа 2013). Дата обращения: 1 декабря 2013. Архивировано 3 декабря 2013 года.
- ↑ Riham AlTawy and Amr M. Youssef. Integral Distinguishers for Reduced-round Stribog (англ.) (8 октября 2013). Дата обращения: 3 ноября 2015. Архивировано 4 марта 2016 года.
- ↑ http://www.streebog.info/ Архивная копия от 3 декабря 2013 на Wayback Machine Открытый конкурс по исследованию функции
- ↑ http://www.streebog.info/news/opredeleny-pobediteli-konkursa-po-issledovaniyu-khesh-funktsii-stribog/ Архивная копия от 10 сентября 2015 на Wayback Machine Определены победители конкурса по исследованию хеш-функции «Стрибог»
- ↑ Jian Guo, Jérémy Jean, Gaëtan Leurent, Thomas Peyrin, Lei Wang. The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function (англ.) (29 августа 2014). Дата обращения: 3 ноября 2015. Архивировано 4 марта 2016 года.
- ↑ Alex Biryukov, Léo Perrin, Aleksei Udovenko. The Secret Structure of the S-Box of Streebog, Kuznechik and Stribob (англ.) (14 августа 2015). Дата обращения: 3 ноября 2015. Архивировано 8 сентября 2015 года.
- ↑ Alex Biryukov, Léo Perrin, Aleksei Udovenko. Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (Full Version) (англ.) (26 января 2016). Дата обращения: 22 февраля 2017. Архивировано 16 июля 2017 года.
- ↑ Léo Perrin. Partitions in the S-Box of Streebog and Kuznyechik (29 января 2019). Дата обращения: 25 августа 2020. Архивировано 14 ноября 2020 года.
- ↑ Virgil Security, Inc. Очередные странности в алгоритмах ГОСТ Кузнечик и Стрибог . habr.com. Дата обращения: 25 августа 2020. Архивировано 7 ноября 2020 года.
- ↑ П. А. Лебедев. Сравнение старого и нового стандартов РФ на криптографическую хэш-функцию на ЦП и графических процессорах NVIDIA . Московский институт электроники и математики Национального исследовательского университета «Высшая школа экономики» (2012). Дата обращения: 25 августа 2020. Архивировано 18 апреля 2021 года.
- ↑ GitHub — okazymyrov/stribog . Дата обращения: 3 декабря 2013. Архивировано 11 июня 2018 года.
- ↑ Riham AlTawy and Amr M. Youssef. Watch your Constants: Malicious Streebog (англ.) (8 октября 2013). Дата обращения: 3 ноября 2015. Архивировано 4 марта 2016 года.
- ↑ В.И. Рудской. Об алгоритме выработки констант функции хэширования «Стрибог» . Дата обращения: 26 декабря 2019. Архивировано 26 декабря 2019 года.
- ↑ V. Rudskoy. Note on Streebog constants origin (англ.). Дата обращения: 26 декабря 2019. Архивировано 2 марта 2021 года.
- ↑ Описание протокола тайного голосования ДЭГ . Портал дистанционного электронного голосования ЦИК России. ПАО "Ростелеком" (2023).
Ссылки
[править | править код]- Текст стандарта ГОСТ Р 34.11-2012 «Информационная технология. Криптографическая защита информации. Функция хэширования»
- Текст стандарта ГОСТ 34.11-2018 «Информационная технология. Криптографическая защита информации. Функция хэширования»
- Текст стандарта ГОСТ Р 34.11-2012 в Викитеке
- RFC 6986 GOST R 34.11-2012: Hash Function
- Algebraic Aspects of the Russian Hash Standard GOST R 34.11-2012, 2013
- Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (Full Version), 2016
Для улучшения этой статьи желательно:
|