Правильное хеширование паролей

Наверняка вам известно, что хорошая система контроля доступа, основанная на вводе и проверке правильности пароля, никогда и нигде не сохраняет пароли в открытом виде, а проверяет введенный пользователем пароль с использованием хеш-суммы этого пароля. А очень хорошие системы еще и добавляют к ним «соль» — случайную строку, которая для каждого пользователя уникальна. В этой статье мы на практике рассмотрим вопросы правильного хеширования паролей, руководствуясь при этом актуальными российскими методическими рекомендациями.
Как выглядят записи в базе данных пользователей «хороших систем контроля доступа»? Примерно так (здесь видны имя учетной записи пользователя, значение соли и значение хеша):

...

"Ivanov" "QxLUF1bgIAdeQX" c9e209040c863f84a31e719795b25775239547

"Petrov" "bv5PehSMfV11Cd" d1d3ec2e6f20fd420d50e2642992841d8338a3

"Sidorov" "YYLmfY6IehjZMQ" a49670c3c18b9e079b9cfaf51634f563dc88ed

...

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

Документ называется «Рекомендации по стандартизации Р 50.1.111—2016. Информационная технология. Криптографическая защита информации. Парольная защита ключевой информации». Он разработан техническим комитетом по стандартизации ТК 26 «Криптографическая защита информации» и представляет собой расширение международного стандарта PKCS #5 Version 2.0 (Public Key Cryptography Standart: Password-Based Cryptography Specification): в процедуру хеширования, описанную в PKCS #5, внесена возможность использовать алгоритм из ГОСТ Р 34.11—2012 (да-да, это тот самый «Стрибог» — похоже, нынче без него никуда).

Содержание

Общая схема и исходные данные
Псевдослучайная хеш-функция HMAC_GOST3411
Определение констант
Функция подсчета «стрибог»-хеша
Пишем непосредственно саму функцию HMAC_GOSTR3411
Password-Based Key Derivation Function
Функция вычисления значения первой итерации для i-го цикла
Функция вычисления значения последующих итераций для i-го цикла
Ксорим результаты всех итераций
Собираем результаты расчетов каждого цикла и определяем окончательный хеш
Заключение

Общая схема и исходные данные

Основу алгоритма получения хеша составляет так называемая функция диверсификации PBKDF версии 2.0 (Password-Based Key Derivation Function). Данная функция реализуется путем применения псевдослучайной хеш-функции к строке, в нашем случае к паролю, вместе с солью, процесс повторяется большое число раз.

хеширование паролей — Общая схема выработки нужного хеша

В качестве псевдослучайной хеш-функции мы будем использовать функцию вычисления аутентификационного кода сообщения HMAC_GOST3411 (Hash-based Message Authentication Code) на основе, как ты уже догадался, хеш-функции «Стрибог». Исходные данные для алгоритма:

введенный пользователем пароль (длина не более 512 бит, или 64 байт);
значение соли (произвольной длины);
число итераций (минимально допустимое значение — 1000, максимально допустимое — 4 294 967 295);
необходимая длина вычисляемого хеша.

Псевдослучайная хеш-функция HMAC_GOST3411

Сама функция HMAC_GOST3411 описана в другом нормативно-методическом документе Р 50.1.113—2016 и включает в себя следующие этапы:

дополнение нулями введенного пароля до длины в 64 байт (конечно, в том случае, если его длина меньше этого значения);
побайтовое сложение по модулю 2 получившегося на предыдущем этапе дополненного пароля с 64-байтовой константой ipad, в которой каждый байт равен 0x36;
конкатенация получившегося на предыдущем этапе значения с солью и подсчет «стрибог»-хеша из полученной строки;
конкатенация результата побайтового xor дополненного пароля с 64-байтовой константой opad (значение каждого байта равно 0x5c) с получившимся на предыдущем этапе результатом;
подсчет «стрибог»-хеша из результата предыдущего этапа.

Перед тем как писать код самой функции HMAC_GOST3411, необходимо определить нужные константы ipad и opad и написать функцию подсчета «стрибог»-хеша байтового массива произвольной длины.

Определение констант

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

1	#define BLOCK_SIZE 64

Константу ipad определим таким образом:

uint8_t i_pad[BLOCK_SIZE] = {

0x36, 0x36, 0x36, 0x36, 0x36, ... , 0x36, 0x36

};

а константу opad таким:

uint8_t o_pad[BLOCK_SIZE] = {

0x5c, 0x5c, 0x5c, 0x5c, 0x5c, ... , 0x5c, 0x5c

};

Для экономии места здесь константы описаны не полностью, на самом деле каждая из них длиной по 64 байт.

Функция подсчета «стрибог»-хеша

Для начала скачаем и подключим нужные файлы, в которых реализованы базовые функции алгоритма «Стрибог»:

1	#include "gost_3411_2012_calc.h"

Далее напишем саму функцию. На вход функции подается указатель на строку с исходными данными, указатель на массив, куда будет записан искомый хеш, длина искомого хеша (512 или 256 бит) и длина массива исходных данных:

static void

GetHashString(uint8_t *str, uint8_t *hash,

int hash_size, size_t size_str)

Определяем структуру CTX для хранения всего, что нужно при подсчете хеша, и выделяем для нее память:

1 2	TGOSTHashContext CTX; CTX = (TGOSTHashContext)(malloc(sizeof(TGOSTHashContext)));

Создаем промежуточный буфер и записываем в него исходную строку:

uint8_t *buffer;

buffer = malloc(size_str);

memcpy(buffer, str, size_str);

Считаем хеш-сумму и пишем результат в выходной байтовый массив:

GOSTHashInit(CTX, hash_size);

GOSTHashUpdate(CTX, buffer, size_str);

GOSTHashFinal(CTX);

memcpy(hash, CTX->hash, BLOCK_SIZE);

Пишем непосредственно саму функцию HMAC_GOSTR3411

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

static void

HMAC_GOSTR3411(const uint8_t *K, size_t size_K,

const uint8_t *T, size_t size_T,

uint8_t *HMAC)

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

Далее произведем дополнение пароля нулями и поксорим результат дополнения с ipad:

uint8_t internal_1 [2 * BLOCK_SIZE];

uint8_t *internal_2;

uint8_t hash[BLOCK_SIZE];

internal_2 = malloc(BLOCK_SIZE + size_T);

uint8_t K_[BLOCK_SIZE];

memset(K_, 0x00, BLOCK_SIZE);

memcpy(K_, K, size_K);

add_xor_64(K_, i_pad, internal_2);

Присоединим к полученному соль и вычислим значение «стрибог»-хеша полученного массива:

1 2	memcpy(internal_2 + BLOCK_SIZE, T, size_T); GetHashString(internal_2, hash, 512, BLOCK_SIZE + size_T);

Поксорим дополненный пароль с opad, соединим с хешем, вычисленным на предыдущем шаге, и второй раз посчитаем «стрибог»-хеш. Результат запишем в HMAC:

add_xor_64(K_, o_pad, internal_1);

memcpy(internal_1 + BLOCK_SIZE, hash, BLOCK_SIZE);

GetHashString(internal_1, HMAC, 512, 2 * BLOCK_SIZE);

Основа функции PBKDF в виде HMAC_GOSTR3411 написана, можно приступать к реализации непосредственно самой PBKDF.

Password-Based Key Derivation Function

Первым делом необходимо определить количество 64-байтовых блоков в искомом хеше, для чего установленную ранее длину нужного нам хеша от пароля и соли делим на 64 и округляем результат до ближайшего целого в большую сторону (к примеру, если требуемая длина искомого хеша равна 100 байт, то количество блоков будет равно двум, в стандарте про округление в большую сторону напрямую не сказано, однако это надо иметь в виду). Количество блоков искомого хеша определяет число циклов, каждый из которых включает в себя некоторое число итераций C (об этом числе мы уже говорили выше).

Результатом первой итерации будет результат вычисления HMAC_GOSTR3411 от пароля и значения соли с присоединенным к нему значением текущего номера цикла в байтовом представлении (напомню, номер цикла изменяется в пределах от единицы до N, где N — число блоков в искомом хеше). Результатом последующих итераций будет результат вычисления HMAC_GOSTR3411 от пароля и значения HMAC_GOSTR3411, полученного на предыдущей итерации. Далее результаты каждой итерации побайтно ксорятся между собой, и в итоге мы получаем результат вычислений одного цикла T(i), где i лежит в пределах от единицы до N (число блоков искомого хеша).

Функция вычисления значения первой итерации для [crayon-662c04084af0d298526000-i/]-го цикла

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

static void

U_first(const uint8_t *password, size_t size_pass,

const uint8_t *salt, size_t size_salt,

uint32_t i, uint8_t *U_first_res)

На вход подаем указатель на байтовый массив с паролем, размер этого пароля, указатель на массив с солью, размер соли, номер цикла i, а также указатель на байтовый массив для записи результата. Далее соль и значение номера цикла (в четырехбайтовом представлении) сливаем в один массив и считаем HMAC_GOSTR3411 от значений пароля и объединенного массива с солью и номером текущего цикла:

// Формируем массив для объединения соли и номера цикла

uint8_t *internal;

internal = malloc(size_salt + 4); // Поскольку номер цикла в четырехбайтовом представлении, то размер массива больше длины соли как раз на четыре

memcpy(internal, salt, size_salt);

// Формируем номер цикла в виде четырех байт

internal[size_salt] = (uint8_t)((i >> 24) & 0xff);

internal[size_salt + 1] = (uint8_t)((i >> 16) & 0xff);

internal[size_salt + 2] = (uint8_t)((i >> 8) & 0xff);

internal[size_salt + 3] = (uint8_t)(i & 0xff);

// Считаем HMAC_GOSTR3411

HMAC_GOSTR3411(password, size_pass, internal, size_salt + 4, U_first_res);

Функция вычисления значения последующих итераций для [crayon-662c04084af12850847328-i/]-го цикла

Объявление данной функции выглядит следующим образом:

static void

U_iter(const uint8_t *password, size_t size_pass,

const uint8_t *U_prev, uint8_t *U_iter_res)

На входе у нас: значение пароля (вернее, указатель на байтовый массив с этим значением), длина пароля, указатель на массив с результатом предыдущей итерации и указатель на байтовый массив для записи результата работы функции.

В тело самой функции поместим всего одну строку (что она делает, думаю, понятно):

1	HMAC_GOSTR3411(password, size_pass, U_prev, BLOCK_SIZE, U_iter_res);

Ксорим результаты всех итераций

Для этого действия объявим функцию F:

static void

F(const uint8_t *password, size_t size_pass, const uint8_t *salt,

size_t size_salt, uint64_t num_iter, uint32_t block_number,

uint8_t *F_res)

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

// Объявляем массивы, необходимые для вычислений

uint8_t T[BLOCK_SIZE];

uint8_t T_[BLOCK_SIZE];

uint8_t internal[BLOCK_SIZE];

// Считаем результат первой итерации

U_first(password, size_pass, salt, size_salt, block_number, T);

memcpy(internal, T, BLOCK_SIZE);

// Считаем результаты последующих операций и ксорим их между собой

for (uint64_t i = 1; i < num_iter; i++){

U_iter(password, size_pass, internal, internal);

add_xor_64(internal, T, T_);

memcpy(T, T_, BLOCK_SIZE);

}

memcpy(F_res, T, BLOCK_SIZE);

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

Собираем результаты расчетов каждого цикла и определяем окончательный хеш

После прохода всех циклов мы получим множество значений вида {T(1), T(2), ..., T(N)}, каждое из которых представляет собой результат вычислений одного из циклов. То есть T(1) — результат вычислений первого цикла, T(2) — второго и так далее. Число же циклов, напомню, у нас определяется числом 64-байтовых блоков в искомом хеше. Для того чтобы из полученного множества определить нужное нам значение хеша, необходимо просто выполнить конкатенацию всех значений T из полученного множества (привести все эти значения к одному массиву) и отделить от получившегося массива столько байтов, какую длину искомого хеша нам надо получить (то есть произвести усечение полученного массива справа на лишнее число байтов).

алгоритмы хеширования паролей — Конкатенация массивов и усечение до нужного размера. DK — нужный нам хеш, R — функция усечения)

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

void

PBKDF_2(const uint8_t *password, size_t size_pass,

const uint8_t *salt, size_t size_salt,

uint64_t num_iter, uint64_t key_length, uint8_t *key)

Определяем количество блоков (и, соответственно, число циклов расчета):

uint32_t num_block = key_length / BLOCK_SIZE;

// Округляем в большую сторону

if ((key_length % BLOCK_SIZE) != 0)

num_block += 1;

Резервируем нужные места в памяти:

uint8_t F_res[BLOCK_SIZE]; // Массив для хранения результата одной итерации

uint8_t *DK; // Массив для хранения итогового значения хеша

DK = malloc(num_block * BLOCK_SIZE);

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

for (uint32_t i = 0; i < num_block; i++){

F(password, size_pass, salt, size_salt, num_iter, i + 1, F_res);

memcpy(DK + (i * BLOCK_SIZE), F_res, BLOCK_SIZE);

}

Отсекаем лишнее и пишем результат в нужное место:

1	memcpy(key, DK, key_length);

Заключение

Вот и все. Результат работы написанной нами функции PBKDF_2 с исходными данными из пятого контрольного примера методических рекомендаций Р 50.1.111—2016 (с. 9) показан на рисунке ниже.

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

Думается, написанная нами функция хеширования паролей на основе российского алгоритма «Стрибог» наряду с scrypt, bcrypt, crypt, SHA-2 и прочими алгоритмами подсчета хеша займет свое место в вашей коллекции алгоритмов хеширования паролей, а при выборе алгоритма для своего очередного проекта вы будете знать, что алгоритмам, придуманным за пределами Российской Федерации, есть вполне достойная отечественная альтернатива.

Ссылки