Hi - EM, eя,-1 (Hi-1)

В [1028] была показана небезопасность следующей схемы (c - константа):

я,. - Eс (e я,. 1) e e я,. 1

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

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

я0 = /я, , где /я - случайное начальное значение

яi - Eя,-1, M,(я,-1)

Эта функция хэширует сообщение 64-битовыми блоками и выдает 64-битовое значение (см. 8-й). Более простое вскрытие этой схемы, чем метод грубой силы, неизвестно .

Ключ

Шифрование

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

Preneel-Bosselaers-Govaerts-Vandewalle

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

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

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

я0 = /я, , где /я - другое случайное начальное значение

G - ELi e я- 1 (R e g. 1) e R e g. 1 e я-1 я. - ELi e Ri (я. 1 e G,. 1) e L e g,. 1 e я-1

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

Quisquater-Girault

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

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

я0 = /я, , где /я - другое случайное начальное значение

щ - El, (g..-1 e R.) e R. e я.. 1 G.. - (щ, e L) e G..-1 e я--1 e l.. я - e G,.-1

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

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

Этот алгоритм представляет собой модификацию Quisquater-Cirault, специально спроектированную для ра-

боты с LOKI [273]. Все параметры - те же, что и в Quisquater-Girault.

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

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

= El ©G,-1(Gt-1 © R.) © R. © H--1 Gt = ER ©H 1 (W, © L.) © G,.-1 © H-1 © Lt H- = W © G..-1

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

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

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

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

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

Gt = EL ©R (G,.-1 © L) © L © H.-1

H = EL (H-1 © R) © R © H.-1

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

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

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

Шифрование Ключ

Ключ

Шифрование

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

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

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

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

(H--1)

G.. = G..-1 © Em, w (G.--1)

H- = © H--1

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

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

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

G,. = G,.-1 © Em. ,h.-1(-G..-1) H- = H..-1 © Eg.-1,m. (H,-1)

Шифрование I Ключ]

I Ключ! Шифрование

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

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

Насколько известно, безопасность 128-битовой хэш-функции этих алгоритмов идеальна : для обнаружения сообщения с заданным хэш-значением требуется 2 128 попыток, а для нахождения двух случайных сообщений с одинаковым хэш-значением - 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, длина хэш-значения этой функции в два раза больше размера блока.Ее схема показана на 5-й. MDC-4 также выдает хэш-значение в два раза большее размера блока, а ее ск о-рость хэширования равна 1/4 (см. 4-й).

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