Алгоритм формирования хэш-функции ГОСТ Р 34.11-94

Хэш-функция - математический расчет, результатом которого является последовательность битов (цифровой код). Имея этот результат, невозможно восстановить исходные данные, использованные для расчета.

Хэш - последовательность битов, полученная в результате расчета хэш-функции.

ГОСТ Р34.11-94 - российский криптографический стандарт вычисления хэш-функции. Был введен 23 мая 1994 года. Размер хэша 256 бит. Размер блока входных данных 256 бит. Алгоритм был разработан ГУБС ФАПСИ и ВНИИС.

Стандарт определяет алгоритм и процедуру вычисления хэш-функции для последовательности символов. Этот стандарт является обязательным для применения в качестве алгоритма хэширования в государственных организациях РФ и ряде коммерческих организаций.

ЦБ РФ требует использовать ГОСТ Р 34.11-94 для электронной подписи предоставляемых ему документов.

Особенностями ГОСТ Р 34.11-94 являются:

При обработке блоков используются преобразования по алгоритму ГОСТ 28147-89;

Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256 бит;

Применены меры борьбы против поиска коллизий, основанном на неполноте последнего блока;

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

Функция используется при реализации систем цифровой подписи на базе асимметричного криптоалгоритма по стандарту ГОСТ Р 34.10-2001. Сообщество российских разработчиков СКЗИ согласовало используемые в Интернет параметры ГОСТ Р 34.11-94:

Использование в сертификатах открытых ключей;

Использование для защиты сообщений в S/MIME (Cryptographic Message Syntax, PKCS#7);

Использование для защиты соединений в TLS (SSL, HTTPS, WEB);

Использование для защиты сообщений в XML Signature (XML Encryption);

Защита целостности Интернет адресов и имён (DNSSEC).

В 2008 году командой экспертов из Австрии и Польши была обнаружена техническая уязвимость, сокращающая поиск коллизий в 223 раз. Количество операций, необходимое для нахождения коллизии, таким образом, составляет 2105, что, однако, на данный момент практически не реализуемо. Проведение коллизионной атаки на практике имеет смысл только в случае цифровой подписи документов, причём если взломщик может изменять неподписанный оригинал.

Алгоритм формирования ЭЦП ГОСТ Р 34.10-2001

Электронно-цифровая подпись (ЭЦП) - аналог собственноручной подписи - для придания электронному документу юридической силы, равной бумажному документу, подписанному собственноручной подписью правомочного лица и/или скрепленного печатью.

Электронная цифровая подпись, или ЭЦП, становится всё более распространённым способом удостоверить документ. В некоторых случаях цифровая отметка не имеет альтернатив. К примеру, при проведении электронных торгов или участии в аукционах, проводимых в Интернете. В таком случае, наличие ЭЦП регламентируется законодательством. В соответствии с Федеральным законом 1-ФЗ от 10.01.2002 года «Об электронной цифровой подписи», ЭЦП в электронном документе является аналогом собственноручной подписи в бумажном документе. Благодаря наличию таковой, электронный документ приобретает юридическую значимость. Наличие ЭЦП гарантирует его подлинность и защищает от подделки, а также помогает идентифицировать владельца сертификата цифровой подписи и предотвратить искажения в документе.

Электронная подпись формируется в результате криптографического преобразования данных и представляет собой уникальную последовательность символов, известную только ее владельцу. Такие свойства ЭЦП как уникальность и надежность делают ее незаменимым атрибутом документов при организации юридически-значимого электронного документооборота.

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

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

Защиту от изменений (подделки) документа: гарантия выявления подделки при контроле целостности делает подделывание нецелесообразным в большинстве случаев;

Доказательное подтверждение авторства документа: Так как создать корректную подпись можно, лишь зная закрытый ключ, а он должен быть известен только владельцу, то владелец пары ключей может доказать своё авторство подписи под документом. В зависимости от деталей определения документа могут быть подписаны такие поля, как «автор», «внесённые изменения», «метка времени» и т. д.

Все эти свойства ЭЦП позволяют использовать её для следующих целей:

Декларирование товаров и услуг (таможенные декларации);

Регистрация сделок по объектам недвижимости;

Использование в банковских системах;

Электронная торговля и госзаказы;

Контроль исполнения государственного бюджета;

В системах обращения к органам власти;

Для обязательной отчетности перед государственными учреждениями;

Организация юридически значимого электронного документооборота;

В расчетных и трейдинговых системах.

ГОСТ Р 34.10-2001 алгоритм разработан главным управлением безопасности связи Федерального агентства правительственной связи и информации при Президенте Российской Федерации при участии Всероссийского научно-исследовательского института стандартизации. Разрабатывался взамен ГОСТ Р 34.10-94 для обеспечения большей стойкости алгоритма.

ГОСТ Р 34.10-2001 основан на эллиптических кривых. Его стойкость основывается на сложности вычисления дискретного логарифма в группе точек эллиптической кривой, а также на стойкости хэш-функции по ГОСТ Р 34.11-94. Принцип подписания электронного документа заключается в шифровании по ГОСТ Р 34.10-2001 полученного хэш алгоритма ГОСТ Р 34.11-94 закрытым ключом на передающей стороне. Проверка подписи на приемной стороне осуществляется путем получения хэш от сообщения и расшифрование открытым ключом зашифрованного значения хэш переданного вместе с сообщением, если эти хэши равны, то подпись верна (рисунок 2.1).

Рисунок 2.1 - Процесс подписания и проверки электронно-цифровой подписи

После подписывания сообщения к нему дописывается цифровая подпись размером 512 бит и текстовое поле. В текстовом поле могут содержаться, например, дата и время отправки или различные данные об отправителе.

Анализ программного криптопровайдера «КриптоПро CSP» показал его эффективность при использовании криптографических алгоритмов шифрования, хэш-функции, электронной цифровой подписи, которые соответствуют стандарту ГОСТ и прошли сертификацию в ФСБ.

Использование на основе криптопровайдера «КриптоПро CSP» приложения позволит автоматизировать процессы: шифрования, электронно-цифровой подписи сразу нескольких документов из пакета программного обеспечения Microsoft Office 2007-2010 Word, Excel, проверки подписи. Это значительно повысит эффективность работы и снизит процент ошибок в процессе обработки электронных документов. Использование шифрования с ГОСТ 28147-89 алгоритмом позволяет передавать по открытым каналам связи информацию содержащую коммерческую тайну, так же возможно сокрытия в зашифрованные архивы особо важную информацию, тем самым ограничив доступ к ней строго определенному кругу лиц.

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

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

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

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

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

WARNING

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

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

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

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

#define BLOCK_SIZE 64 // Размер блока - 64 байта... typedef uint8_t vect; // Определяем тип 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 = { 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]; memcpy(state, internal, BLOCK_SIZE); }

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

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

Static const unsigned char Tau = { 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]; memcpy(state, internal, BLOCK_SIZE); }

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

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

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

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

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

Что требуется

Так как алгоритм отечественного производства, необходимо установить программные продукты КриптоПро CSP и КриптоПро CADESCOM. После установки программных продуктов КриптоПро будет доступен COM-объект HasheData с ProgID - CAdESCOM.HashedData . Этот объект предоставляет свойства и методы для вычисления хэш-суммы данных.

Реализация

Объект HashedData имеет метод Hash , в который передаются данные для вычисления хэш-суммы. Свойство Value содержит результат вычисления. Напишем функцию, которая принимает строку и возвращает хэш-сумму. Незабываем, что строки в разных кодировках имеют различные хэш-суммы, поэтому строку следует привести к кодировке UTF-8.

// Функция вычисляет хэш-сумму по алгоритму ГОСТ 34.11-94
// Параметры
// Строка - Строка - исходная строка.
// Возвращаемое значение:
// Строка - хэш-сумма в виде 64-х символьной строке в шестнадцатеричном формате.
Функция ВычислитьХэшСуммуПоГОСТ_3411(Строка) Экспорт

CADESCOM_HASH_ALGORITHM_CP_GOST_3411 = 100;

HashedData = Новый COMОбъект("CAdESCOM.HashedData");
// Указываем алгоритм хэширования.
HashedData.Algorithm = CADESCOM_HASH_ALGORITHM_CP_GOST_3411;
// Передаем данные, строку кодируем в последовательность байтов UTF-8.
UTF8Encoding = Новый COMОбъект("System.Text.UTF8Encoding");
HashedData.Hash(UTF8Encoding.GetBytes_4(Строка));

// Возвращаем вычисленную хэш-сумму.
Возврат HashedData.Value;

КонецФункции // ВычислитьХэшСуммуПоГОСТ_3411()

Результат работу функции:
Обработку можно скачать по этой

Алгоритм ГОСТ 3411 является отечественным стандартом для хэш-функций. Длина хэш-кода, 256 битам. Алгоритм разбивает сообщение на блоки, длина которых также равна 256 битам. Кроме того, параметром алгоритма является стартовый вектор хэширования Н - произвольное фиксированное значение длиной также 256 бит.

Сообщение обрабатывается блоками по 256 бит справа налево, каждый блок обрабатывается по следующему алгоритму.

Генерация четырех ключей K j =1…4, длиной 256 бит путем перестановки и сдвига

промежуточного значения хэш-кода Н длиной 256 бит;

текущего обрабатываемого блока сообщения М длиной 256 бит;

и некоторых констант С 2 , С 4 =0, С 3 = 1 8 0 8 1 16 0 24 1 16 0 8 (0 8 1 8) 2 1 8 0 8 (0 8 1 8) 4 (1 8 0 8) 4 , где степень обозначает количество повторений 0 или 1.и =0 длиной 256 бит.

а) Каждое 256-битное значение рассматривается как последовательность 32 8-битных значений, для которых осуществляется перестановка P формуле y = (x) , где x - порядковый номер 8-битного значения в исходной последовательности; y - порядковый номер 8-битного значения в результирующей последовательности.

y =(х) = 8i + k, где i = 0 ÷ 3, k = 1 ÷ 8

б)Сдвиг А определяется по формуле

A (x) = (x 1 x 2) & x 4 & x 3 & x 2, где x i - соответствующие 64 бита 256-битного значения х ,

с) Для определения ключа K 1 присваиваются следующие начальные значения:

K 1 = Р (H M )

Ключи K 2 , K 3 , K 4 вычисляются последовательно по следующему алгоритму:

K i = Р (A(H) С i ) A(A(M)).

2. Шифрование 64-битных значений промежуточного хэш-кода H на ключах K i (i = 1, 2, 3, 4) с использованием алгоритма ГОСТ 28147 в режиме простой замены.

а) Хэш-код Н рассматривается как последовательность 64-битных значений H = h 4 & h 3 & h 2 & h 1

б) Выполняется шифрование алгоритмом ГОСТ 28147

S j = E Ki [ h i ]

в) Результирующая последовательность S j , j = 1, 2, 3, 4 длиной 256 бит запоминается во временной переменной

S = s 1 & s 2 & s 3 & s 4

3.Перемешивание результата шифрования.

а) 256-битное значение рассматривается как последовательность шестнадцати 16-битных значений η 16 & η 15 & ...& η 1

б) Сдвиг обозначается Ψ и определяется следующим образом

η 1 η 2 η 3 η 4 η 13 η 16 & η 16 & ... & η 2