Тандемная (Tandem) и одновременная (Abreast) схемы Davies-Meyer

<89 90 919293 94 95 >

Другой способ обойти ограничения, присущие блочным шифрам с 64-битовым ключом, использует алгоритм, подобный IDEA (см. раздел 13.9), с 64-битовым блоком и 128-битовым ключом. Следующие две схемы выдают 128-битовхэш-значение, а их скорость хэширования равна ¹/₂ [930, 925].

Рис. 18-11. Тандемная (Tandem) схема Davies-Meyer.

В первой схеме две модифицированные функции Davies-Meyer работают тандемом, конвейерно (см. Рис. 18-11).

G₀= I_G, где I_G- случайное начальное значение

H₀= I_H, , где I_H - другое случайное начальное значение

В следующей схеме используются две модифицированные функции, работающие одновременно (см. Рис. 18-12).

G₀= I_G, где I_G- случайное начальное значение

H₀= I_H, , где I_H - другое случайное начальное значение

Рис. 18-12. Одновременная (Abreast) схема Davies-Meyer.

В обеих схемах два 64-битовых значения, G_iи H_i, объединяются, образуя единое 128-битовое хэш-значение.

Насколько известно, безопасность 128-битовой хэш-функции этих алгоритмов идеальна: для обнаружения сообщения с заданным хэш-значением требуется 2¹²⁸ попыток, а для нахождения двух случайных сообщений с одинаковым хэш-значением - 2⁶⁴ попыток, при условии, что лучшим способом вскрытия является применение грубой силы.

MDC-2 и MDC-4

MDC-2 и MDC-4 разработаны в IBM [1081, 1079]. В настоящее время изучается вопрос использования MDC-2, иногда называемой Meyer-Schilling, в качестве стандарта ANSI и ISO [61, 765], этот вариант был предложен в [762]. MDC-4 определена для проекта RIPE [1305] (см. раздел 25.7). Спецификация использует DES в качестве блочной функции, хотя теоретически может быть использован любой блочный алгоритм.

Скорость хэширования MDC-2 равна ¹/₂, длина хэш-значения этой функции в два раза больше размера блока.Ее схема показана на Рис. 18-13. MDC-4 также выдает хэш-значение в два раза большее размера блока, а ее скорость хэширования равна ¹/₄ (см. Рис. 18-14).

Рис. 18-13. MDC-2.

Рис. 18-14. MDC-4.

Эти схемы были проанализированы в [925, 1262]. Они безопасны с учетом сегодняшних возможностей вычислительной техники, но их надежность не так велика, как хотелось разработчикам. Их устойчивость к дифференциальному криптоанализу при DES в качестве блочного алгоритма была рассмотрена в [1262].

MDC-2 и MDC-4 запатентованы [223].

Хэш-функция AR

Хэш-функция AR была разработана Algorithmic Research, Ltd. и затем распространена ISO только для информации [767]. Ее базовая структура является вариантом используемого блочного шифра (DES в упомянутой статье) в режиме CBC. Выполняется XOR последних двух блоков шифротекста, константы и текущего блока сообщения, результат шифруется алгоритмом. Хэш-значением являются последние вычисленные два блока шифротекста. Сообщение обрабатывается дважды, двумя различными ключами, поэтому скорость хэширования равна ¹/₂. Первым ключом служит 0x0000000000000000, вторым - 0x2a41522f4446502a, а значение константы c равно 0x0123456789abcdef. Результат сжимается до одного 128-битового хэш-значения. Подробности приведены в [750].

H_i = E_K(M_i Å H_i_-1 Å H_i_-2 Å c) Å M_i

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

Хэш-функция ГОСТ

Эта хэш-функция появилась в России и определена в стандарте ГОСТ Р 34.11.94 [657]. В ней используется блочный алгоритм ГОСТ (см. раздел 14.1), хотя теоретически может использоваться любой блочный алгоритм с 64-битовым блоком и 256-битовым ключом. Функция выдает 256-битовое хэш-значение.

Функция сжатия, H_i= f(M_i,H_i_-₁) (оба операнда - 256-битовые величины) определяется следующим образом:

(1) При помощи линейного смешивания M_i, H_i_-₁ и некоторых констант генерируется четыре ключа шифрования ГОСТ.

(2) Каждый ключ используется для шифрования отличных 64 битов H_i_-₁ в режиме ECB. Полученные 256 битов сохраняются во временной переменной S.

(3) H_i является сложной, хотя и линейной функцией S, M_i и H_i_-₁.

Хэш-значение последнего блока сообщения не является его окончательным хэш-значением. На деле используется три переменные сцепления: H_n- это хэш-значение последнего блока, Z - это XOR всех блоков сообщения, а L- длина сообщения. С использованием этих переменных и дополненного последнего блока M', окончательное хэш-значение равно:

H = f(Z Å M',f(L,f(M', H_n)))

Документация немного запутана (и на русском языке), но я думаю, что понял все правильно. Во всяком случае эта хэш-функция определена как часть российского Стандарта цифровой подписи (см. раздел 20.3).

Другие схемы

Ральф Меркл предложил схему, использующую DES, но она медленна - обрабатывает только семь битов сообщения за итерацию, и каждая итерация состоит из двух шифрований DES [1065, 1069]. Другая схема [1642, 1645] небезопасна [1267], когда-то она предлагалась в качестве стандарта ISO.

<89 90 919293 94 95 >

Дата добавления: 2021-01-26; просмотров: 334;