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

H, = Ec (M, © H,-1) © M, © H,-1

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

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

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

H = Eh, 1, M, (Hi-1)

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

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

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

Preneel-Bosselaers-Govaerts-Vandewalle

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

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

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

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

G = El, ©н, 1 (R © G,-1) © R © G,-1 © И--1 И- = El, © r, (И--1 © G,-1) © L, © G,-1 © И,-1

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

Quisquater-Girault

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

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

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

W = El, (G,-1 © R,) © R, © И,-1

G, = Er, (jyt © L,) © G,-1 © H-1 © L,

H = W © G,-1

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

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

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

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

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

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

w = e, © g, (Gt-1 © r.) © r. © я-1

(w © l) © g,-1 © h-1 © l

h = w © g,-1

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

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

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

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

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

g = е,, © r, (g,-1 © l ) © l © я-1

я = е,, (h-1 © r) © r © я-1

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

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

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

Hi-i

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

Gi-i

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

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

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

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

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

w = Eg,м. (я-1)

g, = g,-1 © Ем,,w (g,-1)

я = w © я-1

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

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

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

g, = g,-1 © Ем, ,я,-1)

я = я-1 © Eg,-1,м. (я-1)

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

Gi-1

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

>Ф-► Gi

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

В обеих схемах два 64-битовых значения, и объединяются, образуя единое 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-й).

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

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