EXG: перестановка левой и правой частей V. 1010 ... 1010 (двоичное, 128 битов) PS: стадия обработки (processing stage) Vj=6\\Aji 6\\Aj2 6\\Aj3 6\\AjA : конкатенация 6: 000 ... 0 (двоичное, 24 бит) Ayk=4*(/-1)+A-(A-=1,2,3,4, Ayk - 8 битов в длину) Hi = g(M/, e Mi ®

hi=1

128 битов

128 битов

Г- g

Ш (D Ф

128 битов

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

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

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

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

Вход: X= X1IIX2IIX3IIX4 P= P1IIP2IIP3IIP4

32 бита

32 бита

Yi Y2

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

Y3 Y4

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

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

P 32 бита ,ф 8 битов 8 битов

32 бита

8 битов

8 битов

±

-Н S1

32 бита

Y=So(Xi,X2)=Rot2((Xi+X2) mod 256) Y=Si(Xi,X2)=Rot2((Xi+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

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