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

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

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

Тестовый пример из ГОСТ 34.11—2012

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

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

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

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

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

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

WARNING

При чтении ГОСТа учти, что во всех 64-байтовых массивах (в том числе и в массивах значений итерационных констант C1 — C12) нулевой байт находится в конце массива, а шестьдесят третий, соответственно, в начале.

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

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

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

#define BLOCK_SIZE 64 // Размер блока — 64 байта  ...  typedef uint8_t vect[BLOCK_SIZE]; // Определяем тип vect как 64-байтовый массив

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

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

static void GOSTHashX(const uint8_t *a, const uint8_t *b, uint8_t *c)  {    int i;    for (i = 0; i < 64; i++)      c[i] = a[i]^b[i];  }

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

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

static void GOSTHashAdd512(const uint8_t *a, const uint8_t *b, uint8_t *c)  {    int i;    int internal = 0;    for (i = 0; i < 64; i++)    {      internal = a[i] + b[i] + (internal >> 8);      c[i] = internal & 0xff;    }  }

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

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

static const unsigned char Pi[256] = {    252, 238, 221, ... 99, 182  };

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

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

static void GOSTHashS(uint8_t *state)  {    int i;    vect internal;    for (i = 63; i >= 0; i--)      internal[i] = Pi[state[i]];    memcpy(state, internal, BLOCK_SIZE);  }

Преобразование S

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

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

static const unsigned char Tau[64] = {      0,   8,  16,  24,  32, ... 55,  63  };

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

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

static void GOSTHashP(uint8_t *state)  {    int i;    vect internal;    for (i = 63; i >= 0; i--)      internal[i] = state[Tau[i]];    memcpy(state, internal, BLOCK_SIZE);  }

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

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

Извини, но продолжение статьи доступно только подписчикам

Подписка позволит тебе читать ВСЕ платные материалы сайта, включая эту статью, без каких-либо ограничений. Мы принимаем банковские карты, Яндекс.Деньги и оплату со счетов мобильных операторов. Подробнее о проекте

Уже подписан?