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

Славянский бог ветра Стрибог (сайт myfhology.info)
Славянский бог ветра Стрибог (сайт myfhology.info)
Тестовый пример из ГОСТ 34.11—2012
Тестовый пример из ГОСТ 34.11—2012

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

 

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

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

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

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

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

WARNING


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

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

 

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

Поскольку при вычислении хеша мы имеем дело с 64-байтовыми блоками (в стандарте они представлены 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
Преобразование 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 восьмибайтовых чисел (здесь приведена не в полном объеме):

Продолжение доступно только подписчикам

Вариант 1. Оформи подписку на «Хакер», чтобы читать все материалы на сайте

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

Вариант 2. Купи один материал

Заинтересовала информация, но нет возможности оплатить подписку? Тогда этот вариант для тебя! Обрати внимание: этот способ покупки доступен только для материалов, опубликованных более двух месяцев назад.


8 комментариев

  1. assp1r1n3

    20.07.2016 at 21:22

    >internal = a[i] + b[i] + (internal >> 8);
    internal типа int, а это значит, что сдвиг вправо будет зависеть от конкретной реализации (implementation-defined behaviour). Вряд ли это именно то, что подразумевается в стандарте ибо это невозможно контролировать.

    • Евгений Дроботун

      20.07.2016 at 22:06

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

  2. lexxmt

    21.07.2016 at 01:27

    Примеры кода в статье на C а прикреплены реализации на Го и питоне, может тогда в статье нужно было рассматривать реализации на этих языках? Или уж добавить реализацию на C что бы сразу можно было под отладчиком и посмотреть и сравнить ощущения с текстом статьи.

  3. Евгений Дроботун

    08.05.2018 at 20:18

Оставить мнение

Check Also

Я у мамы инженер! Как перестать бояться паяльника и начать творить

Ты наверняка встречал в интернете потрясающие проекты вроде оркестра из дисководов, макета…