Стандарт ГОСТ 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. Присоединись к сообществу «Xakep.ru», чтобы читать все материалы на сайте

Членство в сообществе в течение указанного срока откроет тебе доступ ко ВСЕМ материалам «Хакера», увеличит личную накопительную скидку и позволит накапливать профессиональный рейтинг Xakep Score! Подробнее

Вариант 2. Открой один материал

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


Check Also

DDoS на Bluetooth. Разбираем трюк, который поможет отключить чужую колонку

На свете существует не так много вещей, которые бесят практически всех без исключения. Это…

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

  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

  4. Аватар

    becka.99

    24.05.2019 at 00:34

    перезалейте плиз статью для скачивания в pdf
    ссылка не работает

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