Кратко

  • RFC 1186 сообщал о 1 450 000 байт в секунду на Sun SPARC, примерно 70 000 на DEC MicroVAX II и 32 000 на 20-МГц 80286. Сложность поиска двух сообщений с одинаковым хешем оставалась гипотезой.
  • RFC 1320 заменил документ 1990 года более переносимой эталонной реализацией. RFC 6150 в 2011 году перевёл MD4 в статус Historic после документированных атак.

Ronald Rivest предложил в октябре 1990 года быстрый способ свести длинное сообщение к 128-битному значению. В RFC 1186 MD4 рассматривался, среди прочего, как подготовка большого файла к цифровой подписи RSA. На бумаге короткий хеш представлял весь файл. Подпись должна была опираться на то, что злоумышленник не сможет подменить файл другим с тем же результатом.

Скорость алгоритма документ описывал с инженерной точностью. Sun SPARC обрабатывал 1 450 000 байт за секунду, DEC MicroVAX II — около 70 000, 80286 с частотой 20 МГц — около 32 000. Алгоритму не нужны были большие таблицы подстановок. Приложение включало интерфейс, реализацию на C, тестовую программу и пример её работы. Правила для 32-битных слов, 512-битных блоков, дополнения и исходной длины сообщения позволяли воспроизвести один и тот же расчёт.

Для устойчивости к атакам таблицы измерений не было. RFC предполагал примерно 2^64 операций для получения двух разных сообщений с одинаковым результатом и 2^128 для подбора сообщения к заранее заданному хешу. Сам автор назвал оценку гипотезой и предложил продолжать анализ нового алгоритма. Выполнение программы на известной машине показывает цену одного расчёта. Оно не показывает, сколько таких расчётов потребуется атакующему, который найдёт новый приём.

MD4 передали в общественное достояние для проверки и возможного принятия в качестве стандарта. RFC 1186 оставался информационным документом. Открытый текст дал программистам общую инструкцию, а исследователям — точную мишень. В апреле 1992 года RFC 1320 заменил его. Основным отличием называлась более переносимая эталонная реализация; добавились идентификатор алгоритма и соглашение о параметрах для приложений OSI. Код стало проще переносить в другие среды, а вопрос о коллизиях продолжал жить отдельно.

RFC 6150 записал позднейший ответ. Практическая атака 1996 года оценивалась примерно в 2^20 вычислений MD4; результат 2004 года сократил число до 2^8. По сравнению с исходными 2^64 это была перемена самого решения об использовании хеша. В марте 2011 года IETF перевела RFC 1320 в Historic и рекомендовала отказываться от MD4 в пользу существующих альтернатив, включая SHA-256.

Документ об уходе перечислял и оставшиеся применения, в том числе путь совместимости Microsoft. Статус RFC меняется в день публикации; программные библиотеки и контрагенты меняют свои настройки по собственным графикам. История MD4 — это счёт за разницу между лёгким внедрением и тяжёлым выводом из эксплуатации.

Источники