ГОСТ (хеш-функция)

редактировать
ГОСТ Р 34.11-94
Общие
КонструкторыФАПСИ и ВНИИстандарт (СССР )
Впервые опубликовано23.05.1994 (рассекречено)
На основеблочного шифра ГОСТ
ПреемникиСтрибог
СертификацияСтандарт ГОСТ
Подробно
Размеры дайджеста 256 бит
Раунды32
Лучший публичный криптоанализ
Атака 2008 года нарушает хеш-функцию полного цикла. В статье представлена ​​атака с коллизией за 2 раза и атаки на прообраз за 2 раза.

Хеш-функция ГОСТ, определенная в стандартах ГОСТ Р 34.11-94 и ГОСТ 34.311-95 - 256-битная криптографическая хеш-функция. Первоначально она была определена в российском национальном стандарте ГОСТ Р 34.11-94 Информационные технологии - Криптографическая информация. Безопасность - функция хеширования. Эквивалентным стандартом, используемым в других странах-членах СНГ, является ГОСТ 34.311-95.

Эта функция не следует путать с другой хэш-функцией Streebog, которая определена в новой редакции стандарта GOST R 34.11-2012 .

Хеш-функция GOST основана на GOST блочный шифр.

Содержание
  • 1 Алгоритм
    • 1.1 Базовая нотация
    • 1.2 Описание
    • 1.3 Пошаговая хэш-функция
      • 1.3.1 Генерация ключа
      • 1.3.2 Преобразование шифрования
      • 1.3. 3 Преобразование в случайном порядке
    • 1.4 Начальные значения
      • 1.4.1 S-блок «Параметры теста»
      • 1.4.2 S-блок CryptoPro
  • 2 Криптоанализ
  • 3 Тестовые векторы хеширования ГОСТ
    • 3.1 Хеши для «параметров теста»
    • 3.2 Хэши для параметров КриптоПро
  • 4 См. также
  • 5 Ссылки
    • 5.1 Дополнительная литература
  • 6 Внешние ссылки
Алгоритм

ГОСТ обрабатывает переменную -длины сообщения в выходной файл фиксированной длины 256 бит. Входное сообщение разбивается на блоки по 256 бит (восемь 32-битных little endian целых чисел); сообщение дополняется, добавляя к нему столько нулей, сколько требуется для увеличения длины сообщения до 256 бит. Остальные биты заполняются 256-битной целочисленной арифметической суммой всех ранее хешированных блоков, а затем 256-битным целым числом, представляющим длину исходного сообщения в битах.

Базовая нотация

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

  • f 0 gj {\ displaystyle {\ mathcal {f}} 0 {\ mathcal {g}} ^ {j} }{\ mathcal {f}} 0 {\ mathcal {g}} ^ {j} - j-битовый блок, заполненный нулями.
  • j M j {\ displaystyle {\ mathcal {j}} M {\ mathcal {j}}}{\ mathcal {j}} M {\ mathcal {j}} - длина блок M в битах по модулю 2.
  • k {\ displaystyle {\ mathcal {k}}}{\ mathcal {k}} - объединение двух блоков.
  • + {\ displaystyle +}+ - арифметическая сумма двух блоков по модулю 2
  • ⊕ {\ displaystyle \ oplus}\ oplus - логический xor двух блоков

Далее считаем, что младший бит расположен слева от блока, и старший бит справа.

Описание

Входное сообщение M {\ displaystyle M}M разбивается на 256-битные блоки mn, mn - 1, mn - 2,..., m 1 {\ displaystyle m_ {n}, m_ {n-1}, m_ {n-2},..., m_ {1}}m _ {{n}}, m _ {{n-1}}, m _ {{n -2}},..., m _ {{1}} . В случае, если последний блок m n {\ displaystyle m_ {n}}m_{n}содержит менее 256 бит, перед ним слева добавляются нулевые биты для достижения желаемой длины.

Каждый блок обрабатывается пошаговой хеш-функцией H out = f (H in, m) {\ displaystyle H_ {out} \ = \ f (H_ {in}, m)}H_ { {out}} \ = \ f (H _ {{in}}, m) , где H out {\ displaystyle H_ {out}}H _ {{out}} , H in {\ displaystyle H_ {in}}H _ {{in}} , m {\ displaystyle m}m - это 256 -битовые блоки.

Каждый блок сообщения, начиная с первого, обрабатывается пошаговой хеш-функцией f {\ displaystyle f}f для вычисления промежуточного хеш-значения. H я + 1 знак равно е (ЧАС я, ми) {\ Displaystyle \! Н_ {я + 1} = е (Н_ {я}, м_ {я})}\! H _ {{i + 1}} = f (H _ {{i}}, m _ {{i}}) . Н 1 {\ Displaystyle H_ { 1}}H_ {1} значение может быть выбрано произвольно, обычно оно равно 0 256 {\ displaystyle 0 ^ {256}}0 ^ {{256}} .

После H n + 1 {\ displaystyle H_ {n + 1}}H _ {{n + 1}} вычисляется, окончательное значение хеш-функции получается следующим образом

  • H n + 2 = f (H n + 1, L) {\ displaystyle H_ {n + 2} \ = \ f (H_ {n + 1}, \ L)}H _ {{n + 2}} \ = \ f (H _ {{n + 1}}, \ L) , где L - длина сообщения M в битах по модулю 2 256 {\ displaystyle 2 ^ {256}}2 ^ {{256}}
  • h = f (H n + 2, K) {\ displaystyle h \ = \ f (H_ {n + 2}, \ K)}h \ = \ f (H _ {{n + 2}}, \ K) , где K - 256-битная контрольная сумма M : м 1 + м 2 + м 3 +... + mn {\ displaystyle m_ {1} + m_ {2} + m_ {3} +... + m_ {n}}m_{1}+m_{2}+m_{3}+...+m_{n}

h {\ displaystyle h}h- это желаемое значение хэш-функции сообщения M.

GOST-hash-Расчет.gif

Итак, алгоритм работает следующим образом.

  1. Инициализация:
    1. h: = initial {\ displaystyle h \: = initial}h \: = начальное - Начальное 256-битное значение хеш-функции, определяемое пользователем.
    2. Σ: = 0 { \ displaystyle \ Sigma \: = \ 0}\ Sigma \ : = \ 0 - Контрольная сумма
    3. L: = 0 {\ displaystyle L \: = \ 0}L \: = \ 0 - Длина сообщения
  2. Функция сжатия внутренних итераций: для i = 1… n - 1 выполните следующие действия (while | M |>256 {\ displaystyle | M |>256}|M|>256 ):
    1. h: = f (h, mi) {\ displaystyle h \: = \ f (h, \ m_ {i})}h \: = \ f (h, \ m_ {i}) - применить ступенчатую хеш-функцию
    2. L: = L + 256 {\ displaystyle L \: = \ L \ + \ 256}L \: = \ L \ + \ 256 - пересчитать длину сообщения
    3. Σ: = Σ + mi {\ displaystyle \ Sigma \: = \ \ Sigma \ + \ m_ {i}}\ Sigma \: = \ \ Sigma \ + \ m_ {i} - вычислить контрольную сумму
  3. Функция сжатия последней итерации:
    1. L: = L + jmnj {\ displaystyle L \: = \ L \ + \ {\ mathcal {j}} \ m_ {n} \ {\ mathcal {j}}}L \: = \ L \ + \ { \ mathcal {j}} \ m_ {n} \ {\ mathcal {j}} - c вычислить полную длину сообщения в битах
    2. mn: = 0 256 - jmnjkmn {\ displaystyle m_ {n} \: = \ {0} ^ {256 \ - \ {\ mathcal {j}} m_ {n} {\ mathcal {j}}} {\ mathcal {k}} m_ {n}}m_ {n} \: = \ {0} ^ {{256 \ - \ {\ mathcal {j}} m_ {n} {\ mathcal {j}}}} {\ mathcal {k}} m_ {n} - дополнить последнее сообщение нулями
    3. Σ: = Σ + mn {\ displaystyle \ Sigma \: = \ \ Sigma \ + \ m_ {n}}\ Sigma \: = \ \ Sigma \ + \ m_ {n} - обновить контрольную сумму
    4. h: = f (h, mn) {\ displaystyle h \: = \ f (h, \ m_ {n})}h \: = \ f (h, \ m_ {n}) - обработать последний блок сообщения
    5. h: = f (h, L) {\ displaystyle h \: = \ f (h, \ L)}h \: = \ f (h, \ L) - MD - усилить вверх на длину сообщения хеширования
    6. h: = f (h, Σ) {\ displaystyle h \: = \ f (h, \ \ Sigma)}h \: = \ f (h, \ \ Sigma) - контрольная сумма хеширования
  4. Выходное значение равно h {\ displaystyle h}h.

Пошаговая хеш-функция

Пошаговая хеш-функция f {\ displaystyle f}f отображает два 256-битных блока в один: H out = f (H in, m) {\ displaystyle H_ {out} \ = \ f (H_ {in}, \ m)}H _ {{out}} \ = \ f (H _ {{in}}, \ m) . Он состоит из трех частей:

ГОСТ-пошаговая хеш-функция.gif
  • Генерация ключей K 1, K 2, K 3, K 4 {\ displaystyle K_ {1}, \ K_ {2}, \ K_ {3}, \ K_ {4 }}K_ {1}, \ K_ {2}, \ K_ {3}, \ K_ {4}
  • Преобразование шифрования H в {\ displaystyle \ H_ {in}}\ H _ {{in}} с использованием ключей K 1, K 2, K 3, K 4 {\ displaystyle K_ {1}, \ K_ {2}, \ K_ {3}, \ K_ {4}}K_ {1}, \ K_ {2}, \ K_ {3}, \ K_ {4}
  • Преобразование в случайном порядке

Генерация ключей

Алгоритм генерации ключей использует:

  • Два преобразования 256-битных блоки:
    • Преобразование A (Y) = A (y 4 ky 3 ky 2 ky 1) = (y 1 ⊕ y 2) ky 4 ky 3 ky 2 {\ displaystyle A (Y) = A (y_ {4} \ {\ mathcal {k}} \ y_ {3} \ {\ mathcal {k}} \ y_ {2} \ {\ mathcal {k}} \ y_ {1}) = (y_ { 1} \ oplus y_ {2}) \ {\ mathcal {k}} \ y_ {4} \ {\ mathcal {k}} \ y_ {3} \ {\ mathcal {k}} \ y_ {2}}A (Y) = A (y_ {4} \ {\ mathcal {k}} \ y_ {3} \ {\ mathcal {k }} \ y_ {2} \ {\ mathcal {k}} \ y_ {1}) = (y_ { 1} \ oplus y_ {2}) \ {\ mathcal {k}} \ y_ {4} \ {\ mathcal {k}} \ y_ {3} \ {\ mathcal {k}} \ y_ {2} , где y 1, y 2, y 3, y 4 {\ displaystyle y_ {1}, \ y_ {2}, \ y_ {3}, \ y_ {4}}y_ {1}, \ y_ {2}, \ y_ {3}, \ y_ {4} - это 64-битные субблоки Y.
    • Преобразование P (Y) = P (y 32 ky 31 k… ky 1) = y φ (32) ky φ (31) к… ky φ (1) {\ Displaystyle P (Y) = P (y_ {32} {\ mathcal {k}} y_ {31} {\ mathca l {k}} \ dots {\ mathcal {k}} y_ {1}) = y _ {\ varphi (32)} {\ mathcal {k}} y _ {\ varphi (31)} {\ mathcal {k}} \ dots {\ mathcal {k}} y _ {\ varphi (1)}}P (Y) = P (y _ {{32}} {\ mathcal {k}} y _ {{31 }} {\ mathcal {k}} \ dots {\ mathcal {k}} y_ {1}) = y _ {{\ varphi (32)}} {\ mathcal {k}} y _ {{\ varphi (31)}} { \ mathcal {k}} \ dots {\ mathcal {k}} y _ {{\ varphi (1)}} , где φ (i + 1 + 4 (k - 1)) = 8 i + k, i = 0,…, 3, к знак равно 1,…, 8 {\ displaystyle \ varphi (я + 1 + 4 (k-1)) = 8i + k, \ i = 0, \ точки, 3, \ k = 1, \ dots, 8}\ varphi (i + 1 + 4 (k- 1)) = 8i + k, \ i = 0, \ dots, 3, \ k = 1, \ dots, 8 и y 32, y 31,…, y 1 {\ displaystyle y_ {32}, \ y_ {31}, \ \ dots, \ y_ {1}}y _ {{32}}, \ y _ {{31}}, \ \ dots, \ y _ {{1}} - 8-битные субблоки Y.
  • Три константы:
    • C2= 0
    • C3= 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00
    • C4= 0

Алгоритм:

  1. U: = H in, V: = m, W: знак равно U ⊕ V, К 1 знак равно п (W) {\ Displaystyle U \: = \ H_ {in}, \ quad V \: = \ m, \ quad W \: = \ U \ \ oplus \ V, \ quad K_ {1} \ = \ P (W)}U \: = \ H _ {{in}}, \ quad V \: = \ m, \ quad W \: = \ U \ \ oplus \ V, \ quad K_ {1} \ = \ P (W)
  2. Для j = 2,3,4 выполните следующие действия:
    U: = A (U) ⊕ C j, V: = A (A (V)), W: знак равно U ⊕ V, К J знак равно п (W) {\ Displaystyle U: = A (U) \ oplus C_ {j}, \ quad V: = A (A (V)), \ quad W: = U \ oplus V, \ quad K_ {j} = P (W)}U: = A (U) \ oplus C_ {j}, \ quad V: = A (A (V)), \ quad W: = U \ oplus V, \ quad K_ {j} = P (W)

Преобразование шифрования

После генерации ключей шифрование H в {\ displaystyle H _ {in}}H _ {{in}} выполняется по ГОСТ 28147-89 в режиме простой подстановки на клавишах K 1, K 2, K 3, K 4 {\ displaystyle K_ {1}, К_ {2}, К_ {3}, К_ {4}}K_ {1}, K_ {2}, K_ {3}, K_ {4} . Обозначим преобразование шифрования как E (Примечание: преобразование E шифрует 64-битные данные с использованием 256-битного ключа). Для шифрования H в {\ displaystyle H_ {in}}H _ {{in}} разбивается на четыре 64-битных блока: H in = h 4 kh 3 kh 2 kh 1 {\ displaystyle H_ {in} = h_ {4} {\ mathcal {k}} h_ {3} {\ mathcal {k}} h_ {2} {\ mathcal {k}} h_ {1}}H _ {{in}} = h_ {4} {\ mathcal {k}} h_ {3} {\ mathcal {k}} h_ {2} {\ mathcal {k}} h_ {1} , и каждый из этих блоков зашифрован как:

  • s 1 = E (h 1, K 1) {\ displaystyle s_ {1} = E (h_ {1}, K_ {1})}s_ {1} = E (h_ {1}, K_ {1})
  • s 2 = E (час 2, К 2) {\ Displaystyle s_ {2} = E (h_ {2}, K_ {2})}s_ {2} = E (h_ {2}, K_ {2})
  • s 3 = E (час 3, K 3) {\ displaystyle s_ {3} = E (h_ {3}, K_ {3})}s_{3}=E(h_{3},K_{3})
  • s 4 = E (h 4, K 4) {\ displaystyle s_ {4} = E (h_ {4}, K_ {4})}s_ {4 } = E (h_ {4}, K_ {4})

После этого блоки результатов объединяются в один 256-битный блок: S = s 4 ks 3 ks 2 ks 1 {\ displaystyle S = s_ {4} {\ mathcal {k}} s_ {3} { \ mathcal {k}} s_ {2} {\ mathcal {k}} s_ {1}}S = s_ {4} {\ mathcal {k}} s_ {3} {\ mathcal {k }} s_ {2} {\ mathcal {k}} s_ {1} .

Преобразование в случайном порядке

На последнем шаге преобразование в случайном порядке применяется к H в { \ displaystyle H_ {in}}H _ {{in}} , S и m с использованием регистра сдвига с линейной обратной связью. В результате получается промежуточное хеш-значение H o u t {\ displaystyle H_ {out}}H _ {{out}} .

Сначала мы определяем функцию ψ, выполняя LFSR на 256-битном блоке: ψ (Y) = ψ (y 16 ky 15 k... Ky 2 ky 1) = (y 1 ⊕ y 2 ⊕ y 3 ⊕ y 4 ⊕ y 13 ⊕ y 16) ky 16 ky 15 k... ky 3 ky 2 {\ displaystyle \ psi (Y) = \ psi (y_ {16} {\ mathcal {k}} y_ {15} {\ mathcal {k}}... {\ mathcal {k}} y_ { 2} {\ mathcal {k}} y_ {1}) = (y_ {1} \ oplus y_ {2} \ oplus y_ {3} \ oplus y_ {4} \ oplus y_ {13} \ oplus y_ {16}) {\ mathcal {k}} y_ {16} {\ mathcal {k}} y_ {15} {\ mathcal {k}}... {\ mathcal {k}} y_ {3} {\ mathcal {k} } y_ {2}}\ psi (Y) = \ psi (y _ {{16}} {\ mathcal {k}} y _ {{15}} {\ mathcal {k}}... {\ mathcal {k}} y_ {2} {\ mathcal {k}} y_ {1}) = (y_ {1} \ oplus y_ {2} \ oplus y_ {3} \ oplus y_ {4} \ oplus y _ {{13}} \ oplus y_ {{16}}) {\ mathcal {k}} y _ {{16}} {\ mathcal {k}} y _ {{15}} {\ mathcal {k}}... {\ mathcal {k}} y_ {3} {\ mathcal {k}} y_ {2} , где y 16, y 15,..., y 2, y 1 {\ displaystyle y_ {16}, y_ {15},..., y_ {2}, y_ {1}}y _ {{16}}, y _ {{15}},..., y _ {{2}}, y _ {{1}} - это 16-битные субблоки Y.

GOST-psi-function.gif

Преобразование в случайном порядке: H out = ψ 61 (H in ⊕ ψ (m ⊕ ψ 12 (S))) {\ displaystyle H_ {out} = {\ psi} ^ {61} (H_ {in } \ oplus \ psi (m \ oplus {\ psi} ^ {12} (S)))}H _ {{out}} = {\ psi} ^ {{61}} (H _ {{in}} \ oplus \ psi (m \ oplus {\ psi} ^ {{12}}) (S))) , где ψ i {\ displaystyle {\ psi} ^ {i}}{\ psi} ^ {i} обозначает i-ю степень функции ψ {\ displaystyle \ psi}\ psi .

GOST-R-34.11-94-shuffle-transformation.gif

Начальные значения

Для ГОСТ Р 34.11 94 обычно используются два набора начальных параметров. Начальный вектор для обоих наборов равен

H 1 {\ displaystyle H_ {1}}H_ {1} = 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.

Хотя сам стандарт ГОСТ Р 34.11 94 не указывает начальное значение алгоритма H 1 {\ displaystyle H_ {1}}H_ {1} и S-блок преобразования шифрования E {\ displaystyle E}E , но в разделах примеров используются следующие «тестовые параметры».

«Параметры тестирования» S-box

RFC 5831 определяет только эти параметры, но RFC 4357 называет их «параметрами тестирования» и не рекомендует их для использования в производственных приложениях.

Номер S-блокаЗначение
14109213801461111271553
21411412613151023810759
35811310342141512760911
47131010891514461211253
56127151513841091403112
64111007211336859121514
71311413155901014768212
81151305710492314611812

КриптоПро S-бокс

КриптоПро S- Поле происходит из набора параметров «готово к производству», разработанного компанией CryptoPro, он также указан как часть RFC 4357, раздел 11.2.

Номер S-блокаЗначение
11045681371312140921115
25154021311917631214108
37151214941031152610813
44107120152814165131193
57641191221018014151335
67624139150101511814123
71314417051031281562911
81310951141586714130212
Криптоанализ

В 2008 году была опубликована атака, которая нарушает полноценная хеш-функция ГОСТ. В статье представлена ​​атака с коллизией за 2 раза и первая и вторая атаки с прообразом за 2 раза (2 раза означает приблизительное количество вычислений алгоритма при атаке).

тестовые векторы хеширования ГОСТ

Хеши для «параметров теста»

256-битные (32-байтовые) хэши ГОСТ обычно представлены как 64-значные шестнадцатеричные числа. Вот тестовые векторы для хэша ГОСТ с «параметрами теста»

GOST («Быстрая коричневая лиса перепрыгивает через ленивую собаку») = 77b7fa410c9ac58a25f49bca7d0468c9296529315eaca76bd1a10f376d1f4294

Даже небольшое изменение в сообщении с подавляющей вероятностью приведет к совершенно другому хешу из-за лавинного эффекта. Например, изменение d на c:

GOST («Быстрая коричневая лисица перепрыгивает через ленивую шестеренку») = a3ebc4daaab78b0be131dab5737a7f67e602670d543521319150d2e14eeec445

Два образца из GOST 34 -94 стандарт:

GOST («Это сообщение, длина = 32 байта») = b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffa GOST («Предположим, что исходное сообщение имеет длину = 50 байтов») = 471bexe2e7e2e7e7e7e7e8e7e8e7e8e8ae :

ГОСТ ( "") = ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8d ГОСТ ( "A") = d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314dd ГОСТ ( "дайджеста сообщения") = ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4d ГОСТ (128 символов 'U') = 53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4 ГОСТ (1000000 символов 'а') = 5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa

Хэши для параметров CryptoPro

Алгоритм ГОСТ с КриптоПро S-box генерирует другой набор хеш-значений.

= 981e5f3ca30c841487830f84fb433e13ac1101569b9c13584ac483234cd656c0

ГОСТ ( "а") = e74c52dd282183bf37af0079c9f78055715a103f17e3133ceff1aacf2f403011 ГОСТ ( "ABC") = b285056dbf18d7392d7677369524dd14747459ed8143997e163b2986f92fd42c ГОСТ ( "дайджеста сообщения") = bc6041dd2aa401ebfa6e9886734174febdb4729aa972d60f549ac39b29721ba0 ГОСТ ( "быстрая коричневая лиса прыгает через ленивую собака ") = 9004294a361a508c586fe53d1f1b02746765e71b765472786e4770d565830a76 ГОСТ (" ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789 ") = 73b70a39497de53a6e08c67b6d4db853540f03e9389299d9b0156ef7e85d0f61 ГОСТ (" 12345678901234567890123456789012345678901234567890123456789012345678901234567890 ") = 6bc7b38989b28cf93ae8842bf9d752905910a7528a61e5bce0782de43e610c90 ГОСТ (" Это сообщение, длина = 32 байта ") = 2cefc2f7b7bdc514e18ea57fa74ff357e7fa17d652c75f69cb1be7893ede48eb ГОСТ (" Предположим, что исходное сообщение имеет длина = 50 байт ") = c3730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011 ГОСТ (128 из "U") = 1 c4ac7614691bbf427fa2316216be8f10d92edfd37cd1027514c1008f649c4e8 ГОСТ (+1000000 из "а") = 8693287aa62f9478f7cb312ec0866b6c4e4a0f11160441e8f4ffcd2715dd554f
Смотрите также
Ссылки

Дополнительная литература

Внешние ссылки
Последняя правка сделана 2021-05-21 09:14:20
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте