EXG: перестановка левой и правой частей v 1010 ... 1010 (двоичное, 128 битов) PS: стадия обработки (processing stage)

ty=6Ayi бА/2 бЛуз бА/4

: конкатенация б: 000 ... 0 (двоичное, 24 бит) A/k=4*(/-1)+k(k=1,2,3,4, AJk - 8 битов в длину) Hi = g(Mi, Ни) ® Mi ® Ни

128 битов

hi=i

128 битов

№ Ф Ф

128 битов

Рис. 18-2. Схема N-хэш.

Одна стадия обработки показана на 15-й. Блок сообщения разбивается на четыре 32-битовых значения . Предыдущее хэш-значение также разбивается на четыре 32-битовых значения . Функция f представлена на 14th. Функции S0 и S1 те же самые, что и в FEAL.

S0(a,b) = циклический сдвиг влево на два бита ((a + b) mod 256)

S1(a,b) = циклический сдвиг влево на два бита(( a + b + 1) mod 256)

Xi X2

Вход: X= X1IIX2IIX3IIX4 Р= Р1ЦР2ЦР3ЦР4

X3 X4

32 бита

32 бита

32 бита

32 бита 32 бита 32 бита 32 бита

Yi Y2

Выход: Y= YiY2Y3Y4 Y=PS(X,P)

32 бита

-------------------------------------------L L J

Рис. 18-3. Одна стадия обработки N-хэш.

Выход одной стадии обработки становится входом следующей стадии обработки . После последней стадии обработки выполняется XOR выхода с Mi и Hi-1, а затем к хэшированию готов следующий блок.

„ 32 бита Р -►©

8 битов 8 битов

32 бита

8 битов8 битов

J32 бита

Y=So(Xi,X2)=Rot2((Xi+X2) mod 256) Y=S1(x1,X2)=Rot2((x1+X2+1) mod 256) Y: выходные 8 битов, X1?X2 (8 битов): входы Rot2(Y): циклический сдвиг влево на 2 бита 8-битовых данных Y

Рис. 18-4. Функция f.

Криптоанализ N-хэш

Берт ден Боер (Bert den Boer) открыл способ создавать столкновения в функции этапа N-хэш [1262]. Бихам и Шамир применили дифференциальный криптоанализ для вскрытия 6-этапной N-хэш [169, 172]. Конкретное выполненное ими вскрытие (конечно же, могли быть и другие) работает для любого N, делящегося на 3, и эффективнее вскрытия методом дня рождения для любого N, меньшего 15.

То же самое вскрытие может обнаруживать пары сообщений с одинаковым хэш-значением для 12-этапной N-хэш за 256 операций (для вскрытия грубой силой нужно 264 операций). N-хэш с 15 этапами безопасна по отношению к дифференциальному криптоанализу: для вскрытия потребуется 272 операций.

Разработчики алгоритма рекомендуют использовать N-хэш не меньше, чем с 8 этапами [1106]. С учетом доказанной небезопасности N-хэш и FEAL (и ее скорости при 8 этапах) я рекомендую полностью отказаться от этого алгоритма.

18.4 MD4

MD4 - это однонаправленная хэш-функция, изобретенная Роном Ривестом [1318, 1319, 1321]. MD обозначает Message Digest (краткое изложение сообщения), алгоритм для входного сообщения выдает 128-битовое хэш-значение, или краткое изложение сообщения.

В [1319] Ривест описал цели, преследуемые им при разработке алгоритма :

Безопасность. Вычислительно невозможно найти два сообщения с одинаковым хэш-значением . Вскрытие грубой силой является самым эффективным .

Прямая безопасность. Безопасность MD4 не основывается на каких-либо допущениях, например, предп о-ложении о трудности разложения на множители .

Скорость. MD4 подходит для высокоскоростных программных реализаций . Она основана на простом наборе битовых манипуляций с 32-битовыми операндами.

Простота и компактность. MD4 проста, насколько это возможна, и не содержит больших структур данных или сложных программных модулей .

Удачна архитектура. MD4 оптимизирована для микропроцессорной архитектуры (особенно для микропроцессоров Intel), для более крупных и быстрых компьютеров можно выполнить любые необходимые изменения .

После первого появления алгоритма Берт ден Боер и Антон Босселаерс (Antoon Bosselaers) достигли успеха при криптоанализе последних двух из трех этапов алгоритма [202]. Ральфу Мерклу совершенно независимо удалось вскрыть первые два этапа [202]. Эли Бихам рассмотрел использование дифференциального криптоан а-лиза против первых двух этапов MD4 [159]. Хотя все эти вскрытия не были распространены на полный алгоритм, Ривест усилил свою разработку. В результате появилась MD5.

18.5 MD5

MD5 - это улучшенная версия MD4 [1386, 1322]. Хотя она сложнее MD4, их схемы похожи, и результатом MD5 также является 128-битовое хэш-значение .

Описание MD5

После некоторой первоначальной обработки MD5 обрабатывает входной текст 512-битовыми блоками, разбитыми на 16 32-битовых подблоков. Выходом алгоритма является набор из четырех 32-битовых блоков, которые объединяются в единое 128-битовое хэш-значение.

Во первых, сообщение дополняется так, чтобы его длина была на 64 бита короче числа, кратного 512. Этим дополнением является 1, за которой вплоть до конца сообщения следует столько нулей, сколько нужно . Затем, к результату добавляется 64-битовое представление длины сообщения (истинной, до дополнения). Эти два действия служат для того, чтобы длина сообщения была кратна 512 битам (что требуется для оставшейся части алгоритма), и чтобы гарантировать, что разные сообщения не будут выглядеть одинаково после дополнения . Инициализируются четыре переменных:

A =0x01234567

B = 0x89abcdef

C = 0xfedcba98

D =0x76543210

Они называются переменными сцепления.