ГОСТ Р 34.12–2015: чего ожидать от нового стандарта?

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

Эксперт ТК 26

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

Эксперт ТК 26, эксперт ISO/IEC JTC1/SC 27

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

К.ф-м.н, эксперт ТК 26, эксперт ISO/IEC JTC1/SC 27

Историческая справка

Историю стандартизации в области криптографии принято отсчитывать от 1977 г., когда в качестве национального стандарта США (FIPS 46-3) Data Encryption Standard (DES) был принят разработанный в 1973–1974 гг. компанией IBM криптографический алгоритм Lucifer.

Этот шифр представлял собой так называемую сеть Фейстеля (см. рис. 1) – конструкцию, крайне удобную для реализации на устройствах со слабыми вычислительными ресурсами, поскольку на каждой итерации с помощью итерационного ключа и некоторой функции усложнения преобразуется только половина информационного блока, и, кроме этого, алгоритм расшифрования представляет собой алгоритм зашифрования с итерационными ключами, взятыми в обратном порядке. Длина входного блока данных алгоритма DES составляла 64 бита, а ключа – 56 бит.

Спустя чуть более десяти лет, в 1989 г., в СССР введен в действие национальный стандарт "ГОСТ 28147–89. Система обработки информации. Защита криптографическая. Алгоритм криптографического преобразования" (далее – ГОСТ 28147– 89), определяющий симметричный криптографический алгоритм. Принципы функционирования данного криптографического алгоритма, с одной стороны, чем-то напоминают принципы функционирования DES, поскольку он реализован с помощью все той же сети Фейстеля, преобразующей 64-битные блоки данных. С другой стороны, ГОСТ 28147–89 использует ключи с длиной 256 бит, что в отличие от DES с его 56-битным ключом позволяет обеспечивать безопасность данных, шифрованных не только в настоящее время, но и в обозримом будущем. Действительно, количество возможных вариантов ключа составляет 2256~1,16*1077, что является недостижимо большой величиной даже для современных суперкомпьютеров. Еще одной особенностью отечественного алгоритма является возможность смены структурных элементов-подстановок. Фактически, с помощью этого механизма пользователь в каждом конкретном случае (для каждой системы связи) может строить "новый" шифр, просто меняя этот набор.

Развитие методов криптографического анализа и средств показало, что уже в начале 90-х гг. алгоритм DES не обладал необходимыми криптографическими характеристиками. В результате NIST провел конкурс по выбору криптографического стандарта второго поколения – AES. Победитель конкурса, семейство алгоритмов Rijndael, обладало принципиально иными характеристиками по сравнению с алгоритмом DES. Размер блока – 128 бит, что позволяет обрабатывать большие объемы данных. Длина ключа – уже весьма достойные длины, равные 128, 192 или 256 битам. Общая конструкция – вариант подстановочно-перестановочной сети (SP-сети, рис. 2) – итерационного преобразования, состоящего из слоя подстановок (нелинейных элементов), линейного (перемешивающего) слоя и слоя наложения ключа. Такая конструкция за счет преобразования всего блока данных на каждой итерации обеспечивает гораздо более быстрое перемешивание входного вектора по сравнению с сетью Фейстеля. Данный эффект усиливается за счет использования в линейном слое т.н. MDS-матрицы, обеспечивающей максимально возможную зависимость бит входного вектора от бит входного. Однако за такие хорошие криптографические свойства необходимо расплачиваться эксплуатационными: для SP-сети процедура расшифрования существенно отличается от процедуры зашифрования.

Несмотря на то, что Rijndael представлял собой безусловно новый виток в синтезе криптографических алгоритмов, криптоанализ также не стоял на месте, и уже через некоторое время появились работы, которые показывали неоптимальность выбора элементов схемы (прежде всего ключевой развертки): это методы связанных ключей [1] и метод биклик [2].

А что же ГОСТ?

Бурное развитие информационно-телекоммуникационной сферы и, как следствие, увеличение объемов обрабатываемой информации привели к тому, что 64-битная длина входного блока оказалась недостаточной для обработки больших объемов информации, поскольку граница для максимально возможного числа входных блоков, обрабатываемых на одном ключе, для любого блочного шифра определяется классической задачей "о днях рождения" и составляет порядка квадратного корня из общего числа входных векторов [3].

Если говорить о криптостойкости, то на протяжении более четверти века криптографический алгоритм, описанный в ГОСТ 28147–89, подвергался анализу со стороны большого числа отечественных и зарубежных специалистов в области криптографии. Одними из наиболее известных результатов криптографического анализа алгоритма ГОСТ 28147–89 являются работы Таканори Исобе [4] и Итая Динура, Орра Данкельмана, Ади Шамира [4]. В этих статьях говорится о том, что стойкость алгоритма ГОСТ 28147–89 может быть снижена по сравнению с полным перебором ключевого множества, но только при наличии большого количества известных злоумышленнику пар открытого и шифрованного текста (232 у Исобе и 264 у Динура, Дунельмана и Шамира). Как мы уже отметили ранее, при таких объемах обрабатываемой информации любой блочный шифр должен рассматриваться как нестойкий, и данные методы криптографического анализа не применимы на практике.

Следует более подробно остановиться на эксплуатационных свойствах криптографического алгоритма ГОСТ 28147–89. Программная реализация процедуры зашифрования информации на процессоре 3.3 HGz алгоритмом ГОСТ 28147–89 без использования специальных конструкций SSE/AVX, реализованных в современных процессорах, составляет порядка 120 Мбайт/с. Программная реализация процедуры шифрования информации на процессоре 3.3 HGz алгоритмом ГОСТ 28147–89 с использованием специальных конструкций AVX составляет порядка 390 Мбайт/с. В данном случае алгоритм ГОСТ 28147–89 незначительно (в пределах 5–10%) проигрывает алгоритму AES при условии его реализации аналогичным способом без использования аппаратной поддержки (Hardware Support). В этой связи интересно отметить недавнюю публикацию на сайте компании Intel, в которой анонсировано встраивание ПЛИС в процессоры серии Xeon, что позволит для ряда задач в 10–20 раз повысить скорость вычислений. В случае внедрения подобных возможностей скорость реализации отечественных стандартов блочного шифрования может вплотную приблизиться к скорости реализации алгоритма AES с использованием аппаратной поддержки. Необходимо отметить интересный факт, что реализация алгоритма ГОСТ 28147–89 на графическом процессоре (Graphics Processing Unit, GPU) AMD Radeon HD 6970 составляет порядка 1300 Мбайт/с и существенно опережает реализацию алгоритма AES, имеющую производительность порядка 1000 Мбайт/с [5].

С другой стороны, в настоящее время ГОСТ 28147–89, разрабатывавшийся в 80-х гг. прошлого века, оказался крайне эффективен при реализации на низкоресурсных (lightweight) устройствах, в частности, в работе сингапурских специалистов [6] было показано, что ГОСТ по числу необходимых для реализации условных вентилей (т.н. гейт-эквивалентов – GE) выигрывает у многих современных низкоресурсных шифров даже с меньшими длинами ключа.

"Магма"

Именно поэтому при разработке нового стандарта было принято решение сохранить в нем под названием "Магма" алгоритм ГОСТ 28147–89, зафиксировав набор подстановок, что позволяет максимально упростить разработку взаимодействующих информационно-телекоммуникационных систем. Используемый при этом набор подстановок был выбран исходя из обеспечения наилучших характеристик, определяющих невозможность применения дифференциального и линейного методов криптографического анализа [7].

"Кузнечик"

Вторым шифром, включенным в стандарт, является опубликованный в 2013 г. российскими специалистами криптографический алгоритм "Кузнечик" с длиной входного блока, равной 128 битам, и 256-битовым ключом.

Так же, как и AES, алгоритм "Кузнечик" основан на использовании SP-сети, однако при его разработке удалось реализовать ряд синтезных решений, которые позволяют исключить выявленные за последние годы недостатки алгоритма AES.

Как мы уже отмечали ранее, использование MDS-матриц необходимо для обеспечения "быстрого" перемешивания входного вектора. С криптографической точки зрения было бы хорошо использовать большую MDS-матрицу для всего блока входных данных, однако хранить в памяти матрицу большого размера невыгодно с точки зрения эксплуатационных характеристик. В "Кузнечике" при синтезе MDS-преобразования использовался подход, предложенный отечественным ученым-алгебраистом Александром Нечаевым и заключающийся в генерации матрицы с помощью линейного регистра сдвига [8]. Такой подход позволяет в некоторых случаях существенно экономить объем требуемой для реализации алгоритма памяти и получить матрицу для всего 128-битного блока, обрабатываемого алгоритмом, в отличие от алгоритма AES, для которого такие матрицы действуют только на 32-битных подблоках. Подход, используемый в "Кузнечике", предпочтительнее, поскольку позволил в 1,5 раза сократить число итераций по сравнению с AES и обеспечить большую защиту от атак по побочным каналам. Например, как показано в статье Дениса Фомина [9], за счет блочности линейного преобразования AES при его реализации на платформе CUDA возможно практическое восстановление ключа с использованием Timing-атаки. Для алгоритма "Кузнечик" такая атака не применима.

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

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

Стоит сказать, что алгоритм "Кузнечик" хотя и не имеет такой богатой истории, как алгоритм ГОСТ 28147–89, но его криптографические свойства уже подтверждены рядом научно-исследовательских работ зарубежных специалистов в области криптографии.

Если говорить о быстродействии программной реализации алгоритма "Кузнечик", то результаты работ [11, 12] позволили получить скорость порядка 135 Мбайт/c на одном ядре процессора 3.3 HGz и порядка 558 Мбайт/c на графическом процессоре.

Более подробную информацию об алгоритмах "Магма" и "Кузнечик", в том числе их эталонные реализации, можно найти на сайте Технического комитета по стандартизации ТК 26 (www.tc26.ru).

Литература

1. A. Biryukov, D. Khovratovich, Related-key Cryptanalysis of the Full AES-192 and AES-256, eprint.iacr.org.
2. A. Bogdanov, D. Khovratovich, C. Rechberger, Biclique cryptanalysis of the full AES, eprint.iacr.org.
3. ISO/IEC JTC 1/SC 27 Standing Document 12 (SD12) on the Assessment of cryptographic algorithms and key lengths.
4. T. Isobe. A Single-Key Attack on the Full GOST Block Cipher, LNCS v. 6733, p. 290–305. Springer, 2011.
5. С. Смышляев. Вопросы применимости российских криптоалгоритмов, events.yandex.ru/events/meetings/24-july-2015/
6. A. Poschmann, S. Ling, H. Wang, 256 bit standardized crypto for 650 GE – GOST revisited, CHES 2010, LNCS 6225, pp. 219-233, 2010.
7. G. Leander, A. Poschmann. On the Classification of 4 bit S-boxes, LNCS, vol. 4547, pp. 159– 176. Springer, Heidelberg (2007).
8. С. Гонсалес, Е. Коусело, В.Марков, А. Нечаев. Параметры рекурсивных МДР-кодов. Дискретная математика, т. 12, вып. 4. 2000.
9. D. Fomin, A timing attack on CUDA implementations of an AES-type block cipher, CTCrypr 2015 Preproceedings, Kazan, 2015.
10. A. Biryukov, L. Perrin, A. Udovenko, The secret structure of the S-Box of Streebog, Kuznechik and Stribob, eprint.iacr.org.
11. M. Borodin, A. Rybkin, A. Urivskiy, High-Speed Software Implementation of the Prospective 128-bit Block Cipher and Streebog Hash-Function, CTCrypr 2014 Preproceedings, Moscow, 2014.
12. E. Alekseev, V. Popov, A. Prokhorov, S. Smyshlyaev, L. Sonina, On the performance of one perspective LSX-based block cipher. Математические вопросы криптографии, т. 6, вып. 2. 2015.
13. I. Dinur, O. Dunkelman, A. Shamir. Improved Attacks on Full GOST, eprint.iacr.org.