ГОСТ Р 34.11–2012: три года в строю

Александр
Бондаренко

Эксперт технического комитета по стандартизации ТК 26

Григорий
Маршалко

Эксперт технического комитета по стандартизации ТК 26, эксперт ISO/IEC JTC1/SC 27

Василий
Шишкин

К.ф-м.н., эксперт технического комитета по стандартизации ТК 26, эксперт ISO/IEC JTC1/SC 27

С первого января 2013 г. в России действует национальный стандарт ГОСТ Р 34.11– 2012 г. [1], определяющий алгоритм и процедуру вычисления двух функций хеширования (с различными длинами хеш-кодов) семейства "Стрибог", первоначально представленных на конференции Рускрипто в 2010 г. Три года – это уже значительный срок, по прошествии которого можно подвести некоторые промежуточные итоги.

Принципы синтеза

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

Дополнительные условия для криптографических хеш-функций

Должно быть вычислительно сложно:

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

• По значению хеш-кода найти исходное сообщение – т.н. стойкость к нахождению прообраза. Для стойкой функции с длиной хеш-кода, равной n битам, для нахождения прообраза требуется порядка 2n операций вычисления хеш-кода. Эта характеристика важна, например, при использовании хеш-функции в алгоритмах хеширования паролей.
• По сообщению, соответствующему значению хеш-кода, найти какое-либо другое сообщение, дающее такой же хеш-код, – т.н. стойкость к нахождению прообраза. Для стойкой функции с длиной хеш-кода, равной n битам, для нахождения прообраза требуется порядка 2n/m операций вычисления хеш-кода, где m – длина первого сообщения. Эта характеристика также важна при использовании хеш-функции в алгоритмах хеширования паролей.
• По значению хеш-кода, значению длины исходного сообщения дополнить исходное сообщение так, чтобы найти хеш-код нового (дополненного) сообщения, – т.н. стойкость к дополнению сообщения. Для стойкой функции с длиной хеш-кода, равной n битам, для решения задачи дополнения сообщения требуется порядка 2n операций вычисления хеш-кода. Эта характеристика важна при использовании хеш-функции в алгоритмах вычисления кодов аутентификации сообщений (MAC).

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

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

Основой алгоритма является т.н. функция сжатия, представляющая собой блочный шифр, функционирующий в режиме Миягучи-Принеля (рис. 2), для которого обоснованы хорошие криптографические качества [2].

При хешировании исходное сообщение дополняется последовательностью битов специального вида, разбивается на блоки, которые последовательно подаются на вход функции сжатия. После того, как все блоки обработаны, происходит процедура финализации: дополнительно хешируется длина сообщения и его контрольная сумма. С учетом реализованных параметров общая конструкция хеш-функции "Стрибог" является дальнейшим развитием хорошо исследованной конструкции Меркля-Дамгорда [3, 4] с усилением и сходна с наиболее современной на настоящее время конструкцией HAIFA (Hash Iterative FrAmework) [5].

Результаты анализа

За прошедшие 5 лет хеш-функции семейства "Стрибог" стали объектом пристального внимания специалистов в области криптографии. Немалую роль в активизации этих исследований сыграл проведенный Российским техническим комитетом по стандартизации "Криптографическая защита информации" (ТК 26) при участии Академии криптографии Российской Федерации и при организационной и финансовой поддержке ОАО "ИнфоТеКС" открытый конкурс научно-исследовательских работ по анализу разработанных хеш-функций [6].

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

Исследования функции сжатия

К настоящему моменту исследована возможность применения большинства наиболее эффективных методов анализа к функции сжатия хеш-функции "Стрибог": метода встречи посередине [8], метода столкновений [9], метода, использующего супер S-блоки [10, 11], интегрального криптоанализа [12]. Во всех этих работах показана возможность эффективного применения методов только к редуцированным версиям функции сжатия (с уменьшенным числом итераций). Уже начиная с 8 итераций (из полных 12) ни один известный метод эффективно не применим.

Отдельно следует отметить работу [13], в которой была произведена модификация функции сжатия посредством замены структурных элементов – итерационных констант (различных фиксированных векторов, используемых в вычислениях на каждой итерации) таким образом, что авторы смогли в явном виде построить коллизию.

В целом это направление исследований появилось на волне разоблачений Эдварда Сноудена и было связано с вопросом, можно ли выбирать значения структурных элементов криптографического алгоритма так, чтобы в каком-то смысле ослабить его. Первой работой в данном направлении была публикация известного криптографа Жана-Филиппа Омассона и др. [14] которые показали, как указанным выше способом можно строить коллизию для хеш-функции SHA-1. Следует отметить, что подобные результаты носят чисто теоретический интерес, поскольку для построения очередной коллизии злоумышленнику необходимо подбирать каждый раз новый набор констант. В то же время, в работе [15] показано, что константы в хеш-функциях "Стрибог" выбраны доказуемо псевдослучайным способом, поэтому указанный подход даже теоретически не может быть использован.

Исследования конструкции в целом

Несомненным достоинством хеш-функций "Стрибог" является наличие теоретического доказательства стойкости использованной конструкции к атакам поиска коллизии и прообраза [16], выполненного выпускником МГУ им. М.В. Ломоносова Георгием Седовым. Следует отметить, что далеко не для всех используемых в настоящее время функций хеширования такое доказательство было получено.

В работе [17], победившей на упомянутом ранее конкурсе научно-исследовательских работ, получено существенное продвижение в развитии методов построения второго прообраза для конструкций типа Меркля-Дамгорда, но и в этом случае для хеш-функций "Стрибог" авторам публикации не удалось предложить методов эффективнее общих методов анализа, что также является подтверждением правильности выбранных синтезных решений.

Вопросы реализации

Вопросам эффективной реализации хеш-функций "Стрибог" к настоящему моменту посвящено большое количество публикаций конференций Рускрипто и CTCrypt [18–21]. В частности, в работе [20] показано, что на процессорах общего пользования "Стрибог" оказывается быстрее своего предшественника, хеш-функции ГОСТ Р 34.11–94, и сопоставим со скоростью реализации нового американского стандарта SHA-3.

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

Отметим, что в настоящее время в сети Интернет доступны реализации алгоритмов, описанных в ГОСТ Р 34.11–2012, на различных языках программирования (таких, например, как C++, JavaScript, Java, Python, PHP, Verilog).

Потомки

Интересно, что к настоящему моменту на основе конструкций, использованных при синтезе "Стрибога", начинают разрабатывать и другие алгоритмы. Так, в 2014 г. финский специалист Маркку-Юхани Олави Сааринен на основе функции сжатия отечественного стандарта разработал алгоритм аутентифици-рованного шифрования STRI-BOBr1 [23] для участия в организованном американским Национальным институтом стандартов (NIST) конкурсе. К настоящему моменту этот алгоритм успешно вышел во второй этап состязания.

В 2015 г. индийскими специалистами предложена новая функция MGR (Modified Gost R) [24], которая наследует общую структуру хеш-функции "Стрибог", но имеет другую функцию сжатия.

Выводы

За прошедшие 3 года хеш-функции "Стрибог", определяемые стандартом ГОСТ Р 34.11– 2012, зарекомендовали себя как стойкие и эффективно реализуемые синтезные решения, которые отвечают современным требованиям по безопасности, а многочисленные независимые исследования подтвердили правильный выбор подходов к их проектированию.

Литература

1. ГОСТ Р 34.11–2012. Информационная технология. Криптографическая защита информации. Функция хеширования.
2. Preneel B., Govaerts R. and Vandewalle J. Hash functions based on block ciphers: A synthetic approach. In: CRYPTO 1993, LNCS. – Vol. 773. – P. 368–378, Springer, London, 1994.
3. Damgård I. A Design Principle for Hash Functions. In: Brassard, G. (ed.) CRYPTO 1989, LNCS. – Vol. 435. – P. 416–427, Springer, Heidelberg, 1989.
4. Merkle R.C. Secrecy, authentication, and public key systems. Stanford Ph.D. thesis 1979.
5. Biham E., Dunkelman O. A framework for iterative hash functions – HAIFA [online]. Доступ через https://eprint.iacr.org/2007/278.pdf .
6. Открытый конкурс научно-исследовательских работ, посвященных анализу криптографических качеств хеш-функции ГОСТ Р 34.11–2012 [online]. Доступ через http://www.stree-bog.info.
7. Лавриков И.В. Обзор результатов анализа хеш-функций ГОСТ Р 34.11–2012. Проблемы информационной безопасности / И.В. Лавриков, Г.Б. Маршалко, В.И. Рудской, С.В. Смышляев, В.А. Шишкин // Компьютерные системы. – 2015. – № 4. (презентация: http://www.ruscrypto.ru/resource/summary/rc2015/02_rudskoy.pdf) .
8. AlTawy R., Youssef A.M. Preimage Attacks on reduced-round Stribog, Preimage Attacks on Reduced-Round Stribog. In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT 2014. LNCS. – Vol. 8469. – P. 109– 125. – Springer International Publishing, 2014.
9. AlTawy R., Kircanski A., Youssef A.M. Rebound attacks on Stribog, In: Lee, H.S., Han, D.G. (eds.) ICISC 2013. LNCS. – Vol. 8565. – P. 175–188. – Springer International Publishing, 2014.
10. Ma B., Li B., Hao R., Li X. Improved cryptanalysis of reduced-round GOST and Whirlpool hash function, n: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) ACNS 2014. LNCS. – Vol. 8479. – P. 289–307. – Springer International Publishing, 2014.
11. Zou J., Wu W., Wu S. Cryptanalysis of the round-reduced GOST hash function, In: Lin, D., Xu, S., Yung, M. (eds.) Inscrypt 2013. LNCS. – Vol. 8567. – P. 309–322. Springer International Publishing, 2014.
12. AlTawy R., Youssef A.M. Integral distinguishers for reduced-round Stribog. Information Processing Letters 114, 8 (2014), P. 426–431.
13. AlTawy R., Youssef A.M. Watch your Constants: Malicious Streebog [online]. Доступ через http://eprint.iacr.org/2014/879.pdf.
14. Albertini A. Malicious Hashing: Eve's Variant of SHA-1 / A. Albertini, J.-P. Aumasson, M. Eichlseder, F. Mendel, M. Schlaffer / In SAC (2014), A. Joux and A. Youssef, Eds. – Vol. 8781 of Lecture Notes in Computer Science, Springer.
15. Рудской В.И. Об алгоритме выработки констант хеш-функции "Стрибог" [online]. Доступ через https://www.tc26.ru/ISO_IEC/Streebog/streebog_constants_rus.pdf .
16. Седов Г. Стойкость ГОСТ Р 34.11–2012 к атаке на прообраз и атаке поиска коллизий // Матем. вопр. криптогр. – 2015. –№ 6:2. – С. 79–98.
17. Guo J., The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function / J. Guo, J. Jean, G. Leuren, T. Peyrin, L. Wang / In: Joux, A., Youssef, A. (eds.) SAC 2014, LNCS. – Vol. 8781. – P. 195–211. Springer International Publishing, 2014.
18. Borodin M., Rybkin A., Urivskiy A. High-Speed Software Implementation of the Prospective 128-bit Block Cipher and Streebog Hash-Function. – CTCrypt, 2014.
19. Lebedev P. A. Comparison of old and new cryptographic hash function standards of the Russian Federation on CPUs and NVIDIA GPUs // Математические вопросы криптографии. – 2013. – № 4:2. – С. 73–80.
20. Казимиров А., Смышляев С. О создании эффективных программных реализаций отечественных криптографических стандартов. – Рускрипто, 2013 [online]. Доступ через http://www.ruscrypto.ru/resource/summary/rc2013/ruscrypto_2013_0 28.zip .
21. Бородин М., Рыбкин А. Эффективная реализация базовых криптографических конструкций: перспективного алгоритма блочного шифрования с длиной блока 128 бит, функции хеширования ГОСТ Р 34.11– 2012 и ЭЦП ГОСТ Р 34.10– 2012. – Рускрипто, 2014 [online]. Доступ через http://www.ruscryp-to.ru/resource/summary/rc2014/03_borodin_rybkin.pdf .
22. Biryukov A., Perrin L., Udovenko A. Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 [online]. Доступ через http://eprint.iacr.org/2015/812 .
23. Saarinen M.-J. O. StriBob: authenticated encryption from GOST R 34.11–2012 LPS permutation // Математические вопросы криптографии. – 2015. – № 6:2. – С. 67–78.
24. Bussi K., MGR hash function / K. Bussi, D. Dey, P.R. Mishra, B.K. Bass / [online]. Доступ через http://eprint.iacr.org/2015/856.