Импортозамещенное шифрование глазами программиста. Хешируем по ГОСТ 34.11—2012

Стандарт ГОСТ 34.11—2012 пришел на смену ГОСТ 34.11—94, который к настоящему времени уже считается потенциально уязвимым (хотя до 2018 года ГОСТ 1994 года выпуска все же применять не возбраняется). Отечественные стандарты хеширования обязательны к применению в продуктах, которые будут крутиться в ответственных и критических сферах и для которых обязательно прохождение сертификации в уполномоченных органах (ФСТЭК, ФСБ и подобных). ГОСТ 34.11—2012 был разработан Центром защиты информации и специальной связи ФСБ России с участием открытого акционерного общества «Информационные технологии и коммуникационные системы» (ИнфоТеКС). В основу стандарта 2012 года была положена функция хеширования под названием «Стрибог» (если что, такое имя носил бог ветра в древнеславянской мифологии).

Славянский бог ветра Стрибог (сайт myfhology.info)

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

Немного теории

Основу хеш-функции «Стрибог» составляет функция сжатия (g-функция), построенная на блочном шифре, построенном с помощью конструкции Миягучи — Пренеля, признанной одной из наиболее стойких.

Блочный шифр в режиме Миягучи — Пренеля. Здесь m — очередной блок исходного сообщения, h — значение предыдущей функции сжатия

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

Общая схема вычисления хеш-суммы по ГОСТ 34.11—2012

WARNING

Итак, после краткого и небольшого погружения в теорию начинаем кодить.

Базовые функции стандарта

Поскольку при вычислении хеша мы имеем дело с 64-байтовыми блоками (в стандарте они представлены 512-разрядными двоичными векторами), для начала определим этот самый двоичный вектор:

Сложение двух двоичных векторов по модулю 2

Здесь все предельно просто. Каждый байт первого вектора ксорится с соответствующим байтом второго вектора, и результат пишется в третий (выходной) вектор:

Побитовое исключающее ИЛИ над 512-битными блоками

В тексте ГОСТа название данной операции звучит как сложение в кольце вычетов по модулю 2 в степени n. Такая фраза кого угодно может вогнать в уныние, но на самом деле ничего сложного и страшного в ней нет. Два исходных 64-байтовых вектора представляются как два больших числа, далее они складываются, и переполнение, если оно появляется, отбрасывается:

Нелинейное биективное преобразование (преобразование S)

При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества (более подробно про биекцию можешь почитать в Википедии). То есть это просто банальная подстановка байтов в исходном векторе по определенному правилу. В данном случае правило задается массивом из 256 значений:

Здесь для экономии места показаны не все значения, определенные в стандарте, а только три первых и два последних. Когда будешь писать код, не забудь про остальные.

Итак, если в исходном векторе у нас встречается какой-либо байт со значением, например, 23 (в десятичном выражении), то вместо него мы пишем байт из массива Pi, имеющий порядковый номер 23, и так далее. В общем, код функции преобразования S получается такой:

Перестановка байтов (преобразование P)

Преобразование P — простая перестановка байтов в исходном массиве в соответствии с правилом, определяемым массивом Tau размером в 64 байта:

Здесь, так же как и в предыдущем случае, для экономии места показаны не все значения массива Tau.

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

Линейное преобразование (преобразование L)

Это преобразование носит название «умножение справа на матрицу A над полем Галуа GF(2)» и по сравнению с первыми двумя будет немного посложнее (по крайней мере, вкурить всю суть от и до с первого прочтения стандарта удается далеко не всем). Итак, есть матрица линейного преобразования A, состоящая из 64 восьмибайтовых чисел (здесь приведена не в полном объеме):

Исходный вектор делится на порции размером по 8 байт, каждая из этих порций интерпретируется в виде 64-разрядного двоичного представления. Далее берется очередная порция, каждому биту из этой порции ставится в соответствие строка из матрицы A. Если очередной бит равен нулю, то соответствующая ему строка из матрицы A вычеркивается; если очередной бит равен единице, то соответствующая ему строка из матрицы A остается. После всего этого оставшиеся строки из матрицы линейного преобразования ксорятся, и получившееся число записывается в виде очередной восьмибайтовой порции в результирующий вектор. Код выглядит следующим образом:

Схема линейного преобразования L

Пишем все остальное

Имея в наличии все необходимые базовые преобразования, определенные стандартом, можно приступить непосредственно к реализации алгоритма «Стрибог» в целом.

Для начала определим структуру, в которую будем складывать все исходные, промежуточные и конечные результаты вычислений:

Далее напишем преобразование E, которое является частью функции сжатия. В этом преобразовании задействовано двенадцать так называемых итерационных констант (C1 — C12), на основе которых вычисляются раундовые ключи K. Для вычисления этих раундовых ключей определим функцию GOSTHashGetKey , которая представляет собой сочетание преобразований S, P и L, а также побайтного сложения по модулю 2:

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

Если ты попытаешься сравнить приведенные выше константы с текстом стандарта, то увидишь, что эти самые константы записаны «задом наперед». Дело в том, что все байтовые массивы (в том числе и строки тестовых примеров) в тексте стандарта описаны таким образом, что нулевой их элемент находится в конце массива, а не в начале, как мы привыкли, поэтому строки перед использованием надо «переворачивать».

Далее пишем саму функцию преобразования E:

И, используя эти функции, пишем самую главную функцию алгоритма «Стрибог» — функцию сжатия g:

Схема функции сжатия g

В самом начале мы говорили, что хеширование выполняется блоками по 64 байта, а последний блок, если он меньше 64 байт, дополняется нулями с одной единичкой. Для этой операции вполне подойдет функция GOSTHashPadding :

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

Первый этап (инициализация)

Как ясно из названия, этот этап необходим для первоначального задания значений всех переменных:

Второй этап

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

Третий этап

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

Разобравшись со всеми этапами, сложим все в единое целое. Весь процесс будет описан в трех функциях:

• GOSTHashInit (она у нас уже есть);
• GOSTHashUpdate (туда мы поместим все итерации второго этапа);
• GOSTHashFinal (там мы завершим весь процесс третьим этапом).

Функция GOSTHashUpdate

Объявим эту функцию таким образом:

Как уже неоднократно говорилось, хеширование производится блоками по 64 байта, поэтому в начале функции напишем следующее:

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

Функция GOSTHashFinal

Здесь все просто:

Считаем хеш-сумму файла

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

После завершения в зависимости от нужной нам длины хеш-суммы берем значение CTX->hash полностью (длина хеша 512 бит) либо берем от CTX->hash последние 32 байта.

Весь код: классическую реализацию алгоритма (в полном соответствии с ГОСТом), усовершенствованную реализацию (с предварительным расчетом значений преобразований S и L), а также код предварительного расчета значений преобразований S и L — ты найдешь в приложении к этому номеру.

Заключение

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

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