RFC 1320

RFC 1320 — это запрос на комментарии (Request for Comments), опубликованный в 1992 году, который описывает алгоритм хеширования MD4 (Message Digest 4). Данный алгоритм был разработан Рональдом Ривестом (Ronald Rivest) из Массачусетского технологического института (MIT) и предназначен для создания цифровых отпечатков (дайджестов) сообщений произвольной длины. RFC 1320 является частью серии документов, стандартизирующих криптографические хеш-функции, и в настоящее время считается устаревшим и небезопасным для большинства практических применений.

История

Алгоритм MD4 был разработан в 1990 году как более быстрая альтернатива существовавшим на тот момент хеш-функциям, таким как MD2. Основной целью было создание алгоритма, который мог бы эффективно работать на 32-битных процессорах и обеспечивать высокую производительность при обработке больших объёмов данных. Документ RFC 1320 был опубликован в апреле 1992 года и официально закрепил спецификацию MD4.

В 1991 году, ещё до официальной публикации RFC, были обнаружены первые уязвимости в алгоритме. В 1995 году криптоаналитик Ханс Доббертин (Hans Dobbertin) продемонстрировал атаку на коллизию для MD4, которая позволяла найти два различных сообщения с одинаковым хешем за время, значительно меньшее теоретической оценки. Это сделало алгоритм практически непригодным для использования в криптографических приложениях, требующих устойчивости к коллизиям. Впоследствии MD4 был заменён более надёжными алгоритмами, такими как MD5 (RFC 1321) и SHA-1.

Алгоритм

MD4 является хеш-функцией, которая преобразует входное сообщение произвольной длины в 128-битный (16-байтовый) дайджест. Алгоритм работает с блоками данных размером 512 бит (64 байта) и использует три раунда нелинейных преобразований.

Основные этапы обработки

1. Дополнение сообщения: Исходное сообщение дополняется до длины, кратной 512 битам. Дополнение включает добавление одного бита «1», затем нулевых битов, и в конце — 64-битного представления исходной длины сообщения.
2. Инициализация буфера: Для хранения промежуточных и конечного результата используется 128-битный буфер, состоящий из четырёх 32-битных регистров (A, B, C, D). Эти регистры инициализируются фиксированными шестнадцатеричными значениями:

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

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

• Первый раунд: F(X,Y,Z) = (X & Y) | ((~X) & Z)
• Второй раунд: G(X,Y,Z) = (X & Y) | (X & Z) | (Y & Z)
• Третий раунд: H(X,Y,Z) = X ^ Y ^ Z

В каждом раунде выполняется 16 операций, в ходе которых обновляются значения регистров A, B, C, D.

1. Формирование дайджеста: После обработки всех блоков, значения регистров A, B, C, D конкатенируются (соединяются) в порядке от младшего байта к старшему, образуя 128-битный дайджест сообщения.

Криптостойкость и уязвимости

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

• Коллизии: В 1995 году Ханс Доббертин показал, что коллизии для MD4 можно найти за время, эквивалентное вычислению 2^20 хешей (менее секунды на современном на тот момент оборудовании). Позднее были разработаны ещё более эффективные методы, позволяющие находить коллизии практически мгновенно.
• Атаки на прообраз: В 2007 году были предложены атаки, позволяющие находить прообраз (исходное сообщение по его хешу) для MD4 со сложностью около 2^102, что значительно меньше теоретической сложности 2^128.
• Использование в протоколах: Из-за слабости MD4 его использование в современных криптографических протоколах (например, в аутентификации NTLMv1 в Windows) привело к уязвимостям, позволяющим злоумышленникам восстанавливать пароли.

Применение

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

• Аутентификация NTLMv1: В протоколе аутентификации Windows NT LAN Manager (NTLM) версии 1 для хеширования паролей используется MD4.
• Протокол RSAREF: В некоторых ранних реализациях криптографических библиотек.
• Проверка целостности: В нечувствительных к безопасности приложениях, где скорость обработки была критичнее устойчивости к атакам.
• Электронная подпись: В некоторых ранних реализациях цифровых подписей, которые впоследствии были заменены на более безопасные.

В настоящее время MD4 не рекомендуется к использованию в новых разработках. Для обеспечения криптографической стойкости следует применять алгоритмы семейства SHA-2 (SHA-256, SHA-512) или SHA-3.

Сравнение с другими алгоритмами

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

• Алгоритм MD4 был разработан Рональдом Ривестом, который также является соавтором алгоритмов шифрования RC2, RC4, RC5 и RC6.
• Название «MD4» расшифровывается как «Message Digest 4» (четвёртая версия дайджеста сообщений), хотя предшествующие версии (MD2, MD3) не получили широкого распространения.
• Уязвимость MD4 была использована в некоторых вредоносных программах для подделки цифровых подписей.

Источники

• RFC 1320: The MD4 Message-Digest Algorithm (1992)
• Dobbertin, H. (1995). "The Status of MD5 After a Recent Attack". CryptoBytes.
• Rivest, R. (1992). "The MD4 Message-Digest Algorithm". MIT Laboratory for Computer Science.
• Wang, X., et al. (2005). "How to Break MD5 and Other Hash Functions". EUROCRYPT 2005.