Односторонние хэш-функции на основе симметричных блочных алгоритмов

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

Самым очевидным способом является шифрование сообщения в режиме CBC или CFB с помощью фиксированного ключа и вектора инициализации IV. Последний блок шифртекста можно рассматривать в качестве хэш-значения сообщения M. При таком подходе не всегда возможно построить безопасную одностороннюю хэш-функцию, но всегда можно получить код аутентификации сообщения.

Более безопасный вариант хэш-функции можно получить, используя блок сообщения в качестве ключа, предыдущее хэш-значение – в качестве входа, а текущее хэш-значение – в качестве выхода.

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

Схема хэширования, у которой длина хэш-значения равна длине блока показана на рис. 4.5. Ее работа описывается выражениями:

h ₀= IV,

h_i = E_A (B) Å C,

где IV – вектор инициализации (случайное начальное значение); A, B и C могут быть либо M_i, h_{i –1}, (M_i Å h_{i –1}), либо константы (возможно равные 0).

 

Рис. 4.5. Обобщенная схема формирования хэш-функции.

 

Сообщение M разбивается на блоки M_i, принятой длины, которые обрабатываются поочередно.

Три различные переменные 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 на ключах K_i (i = 1, 2, 3, 4) с использованием алгоритма ГОСТ 28147–89 в режиме простой замены.

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

Для генерации ключей используются следующие данные:

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

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

· параметры – три значения С ₂, С ₃ и С ₄ длиной 256 бит следующего вида: С ₂ и С ₄ состоят из одних нулей, а С ₃ равно

1⁸ 0⁸ 1¹⁶ 0²⁴ 1₁₆ 0⁸ (0⁸ 1⁸)² 1⁸ 0⁸ (0⁸ 1⁸)⁴ (1⁸ 0⁸)⁴,

где степень обозначает количество повторений 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 ₁ Å x ₂) || x ₄ || x ₃ || x ₂, где x_i – соответствующие 64 бита 256-битного значения x, символ || обозначает конкатенацию.

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

i = 1, U = H, V = M.

W = U Å V, K ₁ = Р (W)

Затем ключи K ₂, K ₃, K ₄ вычисляются последовательно по следующему алгоритму:

U = A (U) Å С_i,

V = A (A (V)),

W = U Å V,

K _i = Р (W).

Далее выполняется шифрование 64-битных элементов текущего значения Н с ключами K ₁, K ₂, K ₃ и K ₄. При этом Н рассматривается как последовательность 64-битных значений: H = h ₄ || h ₃ || h ₂ || h ₁. Результатом шифрования является S = s ₁ || s ₂ || s ₃ || s ₄, где s _i = E_Ki (h_i), i = 1, 2, 3, 4, E_Ki – шифрование алгоритмом ГОСТ 28147–89 в режиме простой замены.

Наконец на заключительном этапе обработки очередного блока выполняется перемешивание полученной последовательности. 256-битное значение рассматривается как последовательность η₁₆ || η₁₅ ||... || η₁ шестнадцати 16-битных значений.

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

Ψ (η₁₆ || η₁₅ ||... || η₁) = η₁ Å η₂ Å η₃ Å η₄ Å η₁₃ Å η₁₆ || η₁₆ ||... || η₂.

Результирующее значение хэш-кода определяется следующим образом:

,

где H – предыдущее значение хэш-кода, M – текущий обрабатываемый блок, Ψ ⁱ – i -ая степень преобразования Ψ.

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

Входными параметрами этого алгоритма являются:

· исходное сообщение М произвольной длины;

· стартовый вектор хэширования Н, длина которого равна 256 битам;

· контрольная сумма Σ, начальное значение которой равно нулю и длина равна 256 битам;

· переменная L, начальное значение которой равно длине сообщения.

Сообщение М делится на блоки длиной 256 бит и обрабатывается справа налево. Очередной блок i обрабатывается следующим образом:

1.

2.

3. L рассматривается как неотрицательное целое число, к этому числу прибавляется 256 и вычисляется остаток от деления получившегося числа на 2²⁵⁶. Результат присваивается L.

Здесь обозначает следующую операцию: Σ и M_i рассматриваются как неотрицательные целые числа длиной 256 бит. Выполняется обычное сложение этих чисел и находится остаток от деления результата сложения на 2²⁵⁶. Этот остаток и является результатом операции.

Самый левый, т.е. самый последний блок М' обрабатывается следующим образом:

1. Блок М' добавляется слева нулями так, чтобы его длина стала равна 256 битам.

2. Вычисляется .

3. L рассматривается как неотрицательное целое число, к этому числу прибавляется длина исходного сообщения М и находится остаток от деления результата сложения на 2²⁵⁶.

4. Вычисляется Н = c (М', Н).

5. Вычисляется Н = c(L, Н).

6. Вычисляется Н = c(Σ, Н).

Результирующим хэш-значением является Н.