Односторонние хэш-функции на основе симметричных блочных алгоритмов
В качестве односторонних хэш-функций можно использовать симметричные блочные алгоритмы шифрования. Идея в том, что если безопасен блочный алгоритм, то и односторонняя хэш-функция будет безопасной.
Самым очевидным способом является шифрование сообщения в режиме CBC или CFB с помощью фиксированного ключа и вектора инициализации IV. Последний блок шифртекста можно рассматривать в качестве хэш-значения сообщения M. При таком подходе не всегда возможно построить безопасную одностороннюю хэш-функцию, но всегда можно получить код аутентификации сообщения.
Более безопасный вариант хэш-функции можно получить, используя блок сообщения в качестве ключа, предыдущее хэш-значение – в качестве входа, а текущее хэш-значение – в качестве выхода.
При условии, что хэш-функция корректна, безопасность этой схемы основана на безопасности лежащего в ее основе блочного алгоритма шифрования.
Схема хэширования, у которой длина хэш-значения равна длине блока показана на рис. 4.5. Ее работа описывается выражениями:
h0= IV,
hi = EA(B) Å C,
где IV – вектор инициализации (случайное начальное значение); A, B и C могут быть либо Mi, hi–1, (Mi Å hi–1), либо константы (возможно равные 0).
![]() |
Рис. 4.5. Обобщенная схема формирования хэш-функции. |
Сообщение M разбивается на блоки Mi, принятой длины, которые обрабатываются поочередно.
Три различные переменные A, B и С могут принимать одно из четырех возможных значений, поэтому в принципе можно получить 64 варианта общей схемы этого типа. Из них 52 варианта являются либо тривиально слабыми, либо небезопасными. Остальные 12 безопасных схем хэширования перечислены в таблице 4.1.
Таблица 4.1 (начало)
Схемы безопасного хэширования
Номер схемы | Функция хэширования |
1. | ![]() |
2. | ![]() |
3. | ![]() |
4. | ![]() |
5. | ![]() |
6. | ![]() |
7. | ![]() |
8. | ![]() |
9. | ![]() |
Таблица 4.1 (окончание)
Схемы безопасного хэширования
Номер схемы | Функция хэширования |
10. | ![]() |
11. | ![]() |
12. | ![]() |
Первые четыре схемы безопасны против всех криптографических атак. Они приведены на рис. 4.6.
![]() |
Рис. 4.6. Четыре схемы безопасного хэширования. |
4.2.3. Алгоритм хэширования ГОСТ Р 34.11–94
Стандарт ГОСТ Р 34.11–94 определяет алгоритм и процедуру вычисления хэш-функции для любой последовательности двоичных символов, которые применяются в криптографических методах обработки и защиты информации. Этот стандарт базируется на блочном алгоритме шифрования ГОСТ 28147–89.
Хэш-функция, определяемая стандартом, формирует 256 битовое значение. Параметром алгоритма является стартовый вектор хэширования Н – произвольное фиксированное значение длиной также 256 бит.
Сообщение M обрабатывается блоками по 256 бит справа налево. Каждый блок сообщения обрабатывается так называемой шаговой функцией хэширования c по следующему алгоритму.
1. Генерация четырех ключей длиной 256 бит каждый.
2. Шифрование 64-битных значений промежуточного хэш-кода H на ключах Ki (i = 1, 2, 3, 4) с использованием алгоритма ГОСТ 28147–89 в режиме простой замены.
3. Перемешивание результата шифрования.
Для генерации ключей используются следующие данные:
· промежуточное значение хэш-кода Н длиной 256 бит;
· текущий обрабатываемый блок сообщения М длиной 256 бит;
· параметры – три значения С2, С3 и С4 длиной 256 бит следующего вида: С2 и С4 состоят из одних нулей, а С3 равно
18 08 116 024 116 08 (08 18)2 18 08 (08 18)4 (18 08)4,
где степень обозначает количество повторений 0 или 1.
Для формирования ключей используются две формулы, определяющие перестановку и сдвиг. Перестановка Р байтов определяется следующим образом: каждое 256-битное значение рассматривается как последовательность тридцати двух 8-битных значений. Перестановка Р элементов 256-битной последовательности выполняется по формуле y = j(x), где x – порядковый номер 8-битного значения в исходной последовательности; y – порядковый номер 8-битного значения в результирующей последовательности.
j(i + 1 + 4(k – 1)) = 8×i + k,
где i = 0…3, k = 1…8.
Сдвиг А определяется по формуле A(x) = (x1 Å x2) || x4 || x3 || x2, где xi – соответствующие 64 бита 256-битного значения x, символ || обозначает конкатенацию.
Для вычисления ключей присваиваются следующие начальные значения:
i = 1, U = H, V = M.
W = U Å V, K1 = Р (W)
Затем ключи K2, K3, K4 вычисляются последовательно по следующему алгоритму:
U = A(U) Å Сi,
V = A(A(V)),
W = U Å V,
Ki = Р(W).
Далее выполняется шифрование 64-битных элементов текущего значения Н с ключами K1, K2, K3 и K4. При этом Н рассматривается как последовательность 64-битных значений: H = h4 || h3 || h2 || h1. Результатом шифрования является S = s1 || s2 || s3 || s4, где si = EKi(hi), i = 1, 2, 3, 4, EKi – шифрование алгоритмом ГОСТ 28147–89 в режиме простой замены.
Наконец на заключительном этапе обработки очередного блока выполняется перемешивание полученной последовательности. 256-битное значение рассматривается как последовательность η16 || η15 || ... || η1 шестнадцати 16-битных значений.
Сдвиг обозначается Ψ и определяется следующим образом:
Ψ (η16 || η15 || ... || η1) = η1 Å η2 Å η3 Å η4 Å η13 Å η16 || η16 || ... || η2.
Результирующее значение хэш-кода определяется следующим образом:
,
где H – предыдущее значение хэш-кода, M – текущий обрабатываемый блок, Ψi – i-ая степень преобразования Ψ.
Шаговая функция хэширования используется непосредственно в процедуре формирования хэш-значения.
Входными параметрами этого алгоритма являются:
· исходное сообщение М произвольной длины;
· стартовый вектор хэширования Н, длина которого равна 256 битам;
· контрольная сумма Σ, начальное значение которой равно нулю и длина равна 256 битам;
· переменная L, начальное значение которой равно длине сообщения.
Сообщение М делится на блоки длиной 256 бит и обрабатывается справа налево. Очередной блок i обрабатывается следующим образом:
1.
2.
3. L рассматривается как неотрицательное целое число, к этому числу прибавляется 256 и вычисляется остаток от деления получившегося числа на 2256. Результат присваивается L.
Здесь обозначает следующую операцию: Σ и Mi рассматриваются как неотрицательные целые числа длиной 256 бит. Выполняется обычное сложение этих чисел и находится остаток от деления результата сложения на 2256. Этот остаток и является результатом операции.
Самый левый, т.е. самый последний блок М' обрабатывается следующим образом:
1. Блок М' добавляется слева нулями так, чтобы его длина стала равна 256 битам.
2. Вычисляется .
3. L рассматривается как неотрицательное целое число, к этому числу прибавляется длина исходного сообщения М и находится остаток от деления результата сложения на 2256.
4. Вычисляется Н = c(М', Н).
5. Вычисляется Н = c(L, Н).
6. Вычисляется Н = c(Σ, Н).
Результирующим хэш-значением является Н.