Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Шнайер - Прикладная криптография.doc
Скачиваний:
13
Добавлен:
01.05.2025
Размер:
10 Мб
Скачать
☆

Модификация схемы Davies-Meyer

Лай (Lai) и Массей (Massey) модифицировали метод Davies-Meyer, чтобы можно было использовать шифр IDEA [930, 925]. IDEA использует 64-битовый блок и 128-битовый ключ. Вот предложенная ими схема:

H0 = IH, , где IH - случайное начальное значение

Эта функция хэширует сообщение 64-битовыми блоками и выдает 64-битовое значение (см. Рис. 18 -10).

Более простое вскрытие этой схемы, чем метод грубой силы, неизвестно.

Рис. 18-10. Модификация схемы Davies-Meyer.

Preneel-Bosselaers-Govaerts-Vandewalle

Эта хэш-функция, впервые предложенная в [1266], выдает хэш-значение, в два раза большее длины блока алгоритма шифрования: при 64-битовом алгоритме получается 128-битовое хэш-значение.

При 64-битовом блочном алгоритме схема выдает два 64-битовых хэш-значения, Gi и Hi, объединение которых и дает 128-битовое хэш-значение. У большинства блочных алгоритмов длина блока равна 64 битам. Два соседних блока, Li и Ri, размер каждого равен размеру блока, хэшируются вместе.

G0 = IG, где IG - случайное начальное значение

H0 = IH, , где IH - другое случайное начальное значение

Лай приводит вскрытие этой схемы, которое в некоторых случаях делает вскрытие методом дня рождения тривиальным [925, 926]. Пренел (Preneel) [1262] и Копперсмит (Coppersmith0 [372] также успешно взломали эту схему. Не используйте ее.

Quisquater-Girault

Эта схема, впервые предложенная в [1279], генерирует хэш-значение, в два раза большее длины блока. Ее скорость хэширования равна 1. Она использует два хэш-значения, Gi и Hi, и хэширует вместе два блока, Li и Ri.

G0 = IG, где IG - случайное начальное значение

H0 = IH, , где IH - другое случайное начальное значение

Эта схема появилась в 1989 году в проекте стандарта ISO [764], но была заменена более поздней версией [765]. Проблемы безопасности этой схемы были описаны в [1107, 925, 1262, 372]. (В действительности, версия, описанная в материалах конференции, была после того, как версия, представленная на конференции, была вскрыта.) В ряде случаев сложность вскрытия методом дня рождения имеет равна 239, а не 264, как у вскрытия грубой. Не используйте эту схему.

Loki с удвоенным блоком

Этот алгоритм представляет собой модификацию Quisquater-Cirault, специально спроектированную для работы с LOKI [273]. Все параметры - те же, что и в Quisquater-Girault.

G0 = IG, где IG - случайное начальное значение

H0 = IH, , где IH - другое случайное начальное значение

И снова в некоторых случаях вскрытие методом дня рождения оказывается тривиальным [925, 926, 1262, 372, 736]. Не используйте эту схему.

Параллельная схема Davies-Meyer

Это еще одна попытка создать алгоритм со скоростью хэширования 1, который выдает хэш-значение, в два раза большее длины блока. [736].

G0 = IG, где IG - случайное начальное значение

H0 = IH, , где IH - другое случайное начальное значение

К сожалению эта схема тоже небезопасна [928, 861]. Оказывается, что хэш-функция удвоенной длины со скоростью хэширования, равной 1, не может быть безопаснее, чем Davies-Meyer [861].

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

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

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

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

G0 = IG, где IG - случайное начальное значение

H0 = IH, , где IH - другое случайное начальное значение

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

G0 = IG, где IG - случайное начальное значение

H0 = IH, , где IH - другое случайное начальное значение

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

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

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

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 равна 1/2, длина хэш-значения этой функции в два раза больше размера блока.Ее схема показана на Рис. 18 -13. MDC-4 также выдает хэш-значение в два раза большее размера блока, а ее скорость хэширования равна 1/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 последних двух блоков шифротекста, константы и текущего блока сообщения, результат шифруется алгоритмом. Хэш-значением являются последние вычисленные два блока шифротекста. Сообщение обрабатывается дважды, двумя различными ключами, поэтому скорость хэширования равна 1/2. Первым ключом служит 0x0000000000000000, вторым - 0x2a41522f4446502a, а значение константы c равно 0x0123456789abcdef. Результат сжимается до одного 128-битового хэш-значения. Подробности приведены в [750].

Hi = EK(MiHi-1Hi-2c)  Mi

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

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

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

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

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

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

  3. Hi является сложной, хотя и линейной функцией S, Mi и Hi-1.

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

H = f(ZM',f(L,f(M', Hn)))

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