MD4

MD4 (Message Digest 4) — это криптографическая хеш-функция, разработанная профессором Массачусетского технологического института Рональдом Ривестом в 1990 году. Она предназначена для преобразования входных данных произвольной длины в фиксированное 128-битное (16-байтное) хеш-значение, которое служит цифровым отпечатком сообщения. MD4 является предшественником более известных функций MD5 и SHA-1, но в настоящее время считается криптографически нестойкой и не рекомендуется к использованию в системах, требующих защиты от целенаправленных атак.

История создания

Разработка MD4 была частью серии алгоритмов Message Digest, создаваемых Рональдом Ривестом для компании RSA Data Security (ныне RSA Security). Первая версия алгоритма была представлена в октябре 1990 года. Основной целью создания MD4 было обеспечение высокой скорости вычислений при сохранении приемлемого уровня безопасности для того времени. Алгоритм был оптимизирован для реализации на 32-битных процессорах, что делало его особенно эффективным на архитектурах, распространённых в начале 1990-х годов.

В 1991 году Ривест выпустил исправленную версию алгоритма, известную как MD4 с «дополнительными раундами», которая легла в основу более поздней функции MD5. Однако уже в 1992 году были обнаружены первые коллизии (случаи, когда разные входные данные дают одинаковое хеш-значение) для усечённых версий MD4. К 1995 году криптоаналитики продемонстрировали полные коллизии для всего 128-битного выхода, что фактически сделало алгоритм непригодным для криптографических целей.

Алгоритм работы

MD4 обрабатывает входные данные блоками по 512 бит (64 байта). Если длина сообщения не кратна 512 битам, оно дополняется (паддинг) до необходимой длины: добавляется бит «1», затем необходимое количество нулевых битов, и в конце — 64-битное представление исходной длины сообщения.

Основные этапы

1. Инициализация: Устанавливаются четыре 32-битных переменных состояния (A, B, C, D) с фиксированными начальными значениями:

• A = 0x67452301
• B = 0xEFCDAB89
• C = 0x98BADCFE
• D = 0x10325476

1. Обработка блоков: Каждый 512-битный блок сообщения обрабатывается в три раунда (по 16 шагов в каждом), всего 48 шагов. В каждом раунде используется своя нелинейная функция:

• Раунд 1: F(X,Y,Z) = (X & Y) | ((~X) & Z)
• Раунд 2: G(X,Y,Z) = (X & Y) | (X & Z) | (Y & Z)
• Раунд 3: H(X,Y,Z) = X ^ Y ^ Z

На каждом шаге выполняется циклический сдвиг, сложение с константой и обновление переменных состояния.

1. Финальное преобразование: После обработки всех блоков переменные A, B, C, D объединяются в 128-битное хеш-значение.

Криптоанализ и уязвимости

MD4 страдает от нескольких серьёзных криптографических слабостей, которые были выявлены вскоре после его публикации:

Коллизии

Первые практические коллизии для полной версии MD4 были продемонстрированы в 1995 году группой исследователей под руководством Ханса Доббертина. Для нахождения коллизии требовалось выполнить около 2^20 операций, что на современных компьютерах занимает доли секунды. В 2007 году была продемонстрирована возможность нахождения коллизии за время, эквивалентное 2^8 операций, что делает MD4 практически бесполезным для защиты от подделки данных.

Атаки на прообраз

В 2008 году исследователи показали, что нахождение прообраза (восстановление исходного сообщения по хешу) для MD4 возможно за время 2^55 операций, что значительно быстрее полного перебора (2^128). Для усечённых версий алгоритма атаки ещё более эффективны.

Причины уязвимости

Основные недостатки MD4 связаны с простотой его нелинейных функций и недостаточным количеством раундов (всего 48 по сравнению с 64 в MD5). Кроме того, алгоритм не использует константы, зависящие от номера шага, что делает его более предсказуемым для дифференциального криптоанализа.

Применение

Несмотря на криптографическую нестойкость, MD4 продолжает использоваться в некоторых устаревших системах и протоколах:

Протокол NTLM

В протоколах аутентификации Windows NT (NTLMv1 и NTLMv2) MD4 используется для хеширования паролей. Хеш пароля в Windows NT (NTHash) вычисляется как MD4 от пароля в кодировке UTF-16LE. Это применение остаётся одним из наиболее распространённых случаев использования MD4 в современных системах, хотя и считается небезопасным.

Протокол RSAREF

В ранних версиях криптографической библиотеки RSAREF (разработка RSA Security) MD4 использовался для создания цифровых подписей и проверки целостности данных. С появлением MD5 и SHA-1 библиотека была обновлена.

Другие применения

• В некоторых реализациях протокола BitTorrent для проверки целостности частей файла (устаревшие версии).
• В алгоритме хеширования паролей в старых версиях Unix (например, в системе Tru64).
• В протоколе SMB (Server Message Block) для аутентификации в ранних версиях Windows.

Сравнение с другими хеш-функциями

MD4 значительно быстрее MD5 и SHA-1, но его слабая стойкость делает его непригодным для современных приложений, требующих защиты от подделки данных.

Интересные факты

• MD4 стал основой для разработки более стойкой функции MD5, которая, в свою очередь, также была скомпрометирована к 2004 году.
• Алгоритм MD4 был включён в стандарт Internet Engineering Task Force (IETF) RFC 1320, но впоследствии был заменён на MD5 (RFC 1321) и SHA-1 (RFC 3174).
• В 2011 году была продемонстрирована возможность нахождения коллизии для MD4 на обычном ноутбуке за время менее 1 секунды.
• В некоторых системах MD4 используется в комбинации с другими алгоритмами (например, в протоколе NTLMv2, где пароль сначала хешируется MD4, а затем используется HMAC-MD5).

Критика и современный статус

В настоящее время MD4 считается полностью скомпрометированным алгоритмом. Национальный институт стандартов и технологий США (NIST) не рекомендует использовать MD4 для любых криптографических целей. В Российской Федерации использование MD4 не регламентируется отдельными нормативными актами, но в государственных информационных системах рекомендуется применять сертифицированные криптографические средства, соответствующие ГОСТ Р 34.11-2012 («Стрибог»).

Основная критика MD4 связана с тем, что его разработчик, Рональд Ривест, не учёл возможности дифференциального криптоанализа, который был разработан позже. В результате алгоритм оказался уязвимым к атакам, которые стали возможны с ростом вычислительных мощностей.

Несмотря на устаревание, MD4 продолжает изучаться в академических курсах по криптографии как пример алгоритма, который был разработан с учётом требований скорости, но не выдержал испытания временем в плане безопасности.

Источники

• Rivest, R. (1990). «The MD4 Message Digest Algorithm». RFC 1186.
• Rivest, R. (1992). «The MD4 Message Digest Algorithm (revised)». RFC 1320.
• Dobbertin, H. (1995). «Cryptanalysis of MD4». Fast Software Encryption Workshop.
• Wang, X., Yu, H. (2005). «How to Break MD5 and Other Hash Functions». Advances in Cryptology — EUROCRYPT 2005.
• NIST. (2011). «Secure Hash Standard (SHS)». FIPS PUB 180-4.