Функция ГОСТ Р 34. 11-94

В 1994 году был стандартизирован первый отечественный алгоритм бесключевого хэширования, который получил свое имя по номеру стандарта — ГОСТ Р 34.11−94. Данный алгоритм реализован на основе описанного нами выше подхода Меркля-Дамгарда, определяется равенством (8.2) и обладает длиной кода целостности п = 256 и длиной блока разбиения входных данных b = 256.

Однораундовая функция / алгоритма ГОСТ Р 34.11−94 задает отображение

и основана на параллельном применении 4-х алгоритмов блочного шифрования ГОСТ 28 147–89, см. раздел 7.4.2.

Функция / состоит из трех этапов:^[1][2][3]

Рассмотрим указанные этапы более подробно. Определим преобразование.

реализующее перестановку байт вектора u = t/j|| • • • Ци.32 € F₂^{5, где для всех г = 1,…, 32, щ € F₂, по следующему закону:}

^{где 7 г (г + 1 + 4(А; — 1)) = 8 г + к, i = 0,…, 3, к = 1,…, 8.}

^{Далее определим два отображения}

^{реализующих один шаг работы линейного регистра сдвига, определенного соответственно над полями F₂-')2 и F₂i6.}

где Vi € F₂⁶, г — 1,…, 16.

Теперь мы можем описать все этапы одношаговой функции сжатия f (h, a), на вход которой подаются h - элемент последовательности промежуточных значений и а — блок входного сообщения.

1. Для заданных значений h, a е F₂⁵⁶ определим ключ Ад:

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

где i = 2,3.4 и а € F₂⁵⁶ — заданные константы, значения которых могут быть найдены в тексте стандарта ГОСТ Р 34.11−94.^[4]

3. Последний этап функции / состоит в перемешивании блоков е,…, в4, полученных в ходе шифрования, и вычислении значения, то есть.

где -ф^к есть к-я степень преобразования ф, или, другими словами,

Завершающее преобразование д алгоритма ГОСТ Р 34.11−94, применяемое к последнему блоку а_г исходного сообщения, отличается от принятого в схеме Мсркля-Дамгарда и заключается в вычислении значения.

где.

• а* € Ff⁶ — двоичный вектор длины 256, представляющий собой вектор а_г, дополненный нулями до нужной длины, то есть.

• I € F^⁵⁶ — двоичный вектор, содержащий длину исходного сообщения ai||? • • ||a_r в битах, то есть двоичную запись числа.

дополненную нулями до нужной длины.

• se Ff⁶— представляющий собой сумму по модулю ₂256.

всех блоков исходного сообщения, то есть.

Таким образом, отечественная бесключевая функция хэширования ГОСТ Р 34.11−94 определяется равенством (8.2), в котором одношаговая функция / удовлетворяет (8.3), а завершающее преобразование д удовлетворяет (8.4).

Отметим, что текст стандарта ГОСТ Р 34.11−94 не регламентировал начальное значение вектора Hq. На практике, как правило, использовалось значение ho = (0|| • •? ||0) € F^⁵⁶.

Функция ГОСТ Р 34.11−94 действовала в качестве стандарта Российской Федерации в период с 1994 по 2011 год и долгое время считалась стойкой. Однако в 2008 году была предложена атака, см. работу [4], в которой удалось предложить алгоритм обращения функции ГОСТ Р 34.11−94 — решение задачи построения прообраза с трудоемкостью 2²²⁵ операций опробования функции и требуемым объемом памяти 2³⁸ байт. Эта атака послужила причиной принятия в 2012 году следующей версии стандарта — ГОСТ Р 34.11−2012, регламентирующего использование новой функции хэширования «Стрибог».

• [1] генерация ключей к,…, к4 е Ff56 для блочного алгоритмашифрования,
• [2] собственно шифрование блока входных данных а,
• [3] применение линейного преобразования, замешивающего результат шифрования.
• [4] На шаге шифрования блок исходного сообщенияа = сц11"21|"з||"4 разбивается на блоки длины 64 битаи преобразуется с помощью преобразования е: F256 —" F2°6: и Е (к, а) ~ алгоритм блочного шифрования ГОСТ 28 147–89.