В качестве односторонних хэш-функций можно использовать симметричные блочные алгоритмы шифрования. Идея в том, что если безопасен блочный алгоритм, то и односторонняя хэш-функция будет безопасной.
Самым очевидным способом является шифрование сообщения в режиме CBC или CFB с помощью фиксированного ключа и вектора инициализации IV. Последний блок шифртекста можно рассматривать в качестве хэш-значения сообщения M. При таком подходе не всегда возможно построить безопасную одностороннюю хэш-функцию, но всегда можно получить код аутентификации сообщения.
Более безопасный вариант хэш-функции можно получить, используя блок сообщения в качестве ключа, предыдущее хэш-значение – в качестве входа, а текущее хэш-значение – в качестве выхода.
При условии, что хэш-функция корректна, безопасность этой схемы основана на безопасности лежащего в ее основе блочного алгоритма шифрования.
Схема хэширования, у которой длина хэш-значения равна длине блока показана на рис. 4.5. Ее работа описывается выражениями:
h 0= 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) = (x 1 Å x 2) || x 4 || x 3 || x 2, где xi – соответствующие 64 бита 256-битного значения x, символ || обозначает конкатенацию.
Для вычисления ключей присваиваются следующие начальные значения:
i = 1, U = H, V = M.
W = U Å V, K 1 = Р (W)
Затем ключи K 2, K 3, K 4 вычисляются последовательно по следующему алгоритму:
U = A (U) Å Сi,
V = A (A (V)),
W = U Å V,
K i = Р (W).
Далее выполняется шифрование 64-битных элементов текущего значения Н с ключами K 1, K 2, K 3 и K 4. При этом Н рассматривается как последовательность 64-битных значений: H = h 4 || h 3 || h 2 || h 1. Результатом шифрования является S = s 1 || s 2 || s 3 || s 4, где s i = 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(Σ, Н).
Результирующим хэш-значением является Н.
