5.2.2 MD4

Алгоритм MD4 (Message Digest) был разработан Ривестом [Ri1], [Ri2], [Ri3]. Размер вырабатываемого хэш-кода -- 128 битов. По заявлениям самого разработчика при создании алгоритма он стремился достичь следующих целей:

• Безопасность. Для построения коллизий не существует алгоритма эффективнее метода "грубой силы" (т. е. метода, основанного на "парадоксе дня рождения").

• Алгоритм построен без использования каких-либо предположительно трудных задач, т. е. его стойкость должна, подобно шифраторам, обеспечиваться его собственной конструкцией.

• Скорость. Алгоритм допускает эффективную программную реализацию на 32-разрядном процессоре.

• Простота и компактность. Алгоритм MD4 не использует сложных структур данных и подпрограмм.

• Алгоритм оптимизирован с точки зрения его реализации на микропроцессорах типа Intel.

После того, как алгоритм был впервые опубликован, ден Бур и Босселэр [dBB] построили коллизии для последних двух из трех раундов, используемых в MD4. Меркль предложил метод компрометации двухраундового алгоритма (для первых двух раундов оригинального MD4). Бихам [Bi] опубликовал работу, в которой изложил возможные варианты применения метода дифференциального анализа для построения коллизий от полного MD4. Несмотря на то, что ни один из предложенных методов построения коллизий не приводит к успеху (т. е. они оказываются менее эффективными, чем метод "грубой силы") для полного MD4, Ривест усилил алгоритм и предложил новую схему хэширования MD5 [Ri4].