RFC 1321

RFC 1321 — это документ, опубликованный в сети Интернет в рамках серии Request for Comments (RFC), который описывает алгоритм хеширования MD5 (Message Digest 5). RFC 1321 был разработан Рональдом Ривестом (Ronald L. Rivest) из Массачусетского технологического института (MIT) и опубликован в апреле 1992 года. Документ определяет точную спецификацию алгоритма, который преобразует входное сообщение произвольной длины в 128-битное (16-байтное) хеш-значение, называемое дайджестом сообщения. Основное назначение RFC 1321 — предоставить стандартизированный, детерминированный и вычислительно простой метод получения цифрового «отпечатка» данных для проверки их целостности.

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

Разработка MD5 была частью эволюции криптографических хеш-функций, начатой с MD2 (RFC 1319, 1989 год) и MD4 (RFC 1320, 1990 год). Рональд Ривест, один из соавторов алгоритма шифрования RSA, создал MD4 как быструю и эффективную функцию, но вскоре были обнаружены её потенциальные уязвимости. MD5 был разработан как усиленная версия MD4 с дополнительными раундами преобразований и более сложной структурой, чтобы повысить устойчивость к криптоанализу.

RFC 1321 был опубликован в 1992 году, когда безопасность сетевых протоколов и целостность передаваемых данных стали критически важными. Документ быстро стал стандартом де-факто для многих приложений, включая хранение паролей, проверку целостности файлов и создание цифровых подписей.

Алгоритм MD5

Общее описание

Алгоритм MD5, описанный в RFC 1321, принимает на вход сообщение произвольной длины и выводит 128-битный дайджест. Процесс состоит из нескольких этапов:

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

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

1. Обработка блоков: Сообщение обрабатывается блоками по 512 бит (16 32-битных слов). Каждый блок проходит четыре раунда преобразований, каждый из которых использует нелинейную функцию (F, G, H, I), константы T[i] (синусоидальные значения) и циклические сдвиги. В каждом раунде выполняется 16 операций, всего 64 операции на блок.
2. Вывод: После обработки всех блоков значения регистров A, B, C, D конкатенируются (объединяются) в порядке little-endian, образуя 128-битный дайджест.

Нелинейные функции

RFC 1321 определяет четыре нелинейные функции, каждая из которых используется в одном из раундов:

• F(X,Y,Z) = (X & Y) | ((~X) & Z)
• G(X,Y,Z) = (X & Z) | (Y & (~Z))
• H(X,Y,Z) = X ^ Y ^ Z (исключающее ИЛИ)
• I(X,Y,Z) = Y ^ (X | (~Z))

Константы

Для каждого из 64 шагов используется 32-битная константа T[i], вычисляемая как целая часть от \( 2^{32} \times |\sin(i)| \), где i — номер шага (от 1 до 64). Это обеспечивает псевдослучайное распределение значений.

Применение

Благодаря простоте реализации и высокой скорости работы, MD5, описанный в RFC 1321, получил широкое распространение в 1990-х и начале 2000-х годов.

Проверка целостности данных

MD5 использовался для создания контрольных сумм файлов. Пользователи могли вычислить хеш загруженного файла и сравнить его с эталонным значением, предоставленным разработчиком, чтобы убедиться, что файл не был повреждён при передаче или изменён злоумышленником. Этот метод применялся для дистрибутивов операционных систем, программного обеспечения и архивов.

Хранение паролей

Многие системы аутентификации хранили не сами пароли, а их MD5-хеши. При входе пользователя система вычисляла хеш введённого пароля и сравнивала его с хранящимся значением. Это снижало риск компрометации паролей при утечке базы данных. Однако данный подход оказался уязвимым из-за возможности использования радужных таблиц и коллизий.

Цифровые подписи

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

Протоколы

MD5 был включён в ряд сетевых протоколов, таких как:

• HTTP Digest Access Authentication: Использовался для аутентификации пользователей на веб-серверах.
• NTLM: Протокол аутентификации в Windows, использующий MD4 и MD5.
• SSL/TLS: В ранних версиях протокола MD5 применялся в составе алгоритмов обмена ключами и сертификатов.

Критика и уязвимости

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

Коллизии

Основная уязвимость MD5 — возможность нахождения коллизий, то есть двух разных входных сообщений, дающих одинаковый хеш. Первая успешная атака на MD5 была продемонстрирована в 2004 году китайской группой исследователей (Ван Сяоюнь и др.). Они показали, что коллизии могут быть найдены за время, значительно меньшее, чем теоретический предел в \( 2^{64} \) операций.

В 2005 году исследователи продемонстрировали создание двух разных исполняемых файлов с одинаковым MD5-хешем. В 2008 году группа учёных (Стивенс, Сотников, Александер и др.) создала метод, позволяющий генерировать коллизии за считанные секунды на обычном компьютере. В 2009 году они опубликовали сертификат X.509, подделанный с помощью коллизии MD5, что позволило бы выдавать себя за любой домен.

Атаки на пароли

Из-за высокой скорости вычисления MD5 (миллиарды хешей в секунду на современном GPU) и отсутствия соли (дополнительной случайной строки) в большинстве реализаций, MD5 стал крайне уязвим для атак полным перебором и с использованием радужных таблиц.

Статус на сегодня

Начиная с середины 2000-х годов, MD5 считается криптографически сломанным и не рекомендуется для использования в приложениях, требующих устойчивости к коллизиям. Крупные организации, такие как Национальный институт стандартов и технологий США (NIST), отозвали сертификацию MD5 для использования в цифровых подписях. Вместо MD5 рекомендуется использовать алгоритмы семейства SHA-2 (например, SHA-256) или SHA-3.

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

Влияние на криптографию

RFC 1321 и алгоритм MD5 сыграли важную роль в развитии криптографии. Они стимулировали исследования в области криптоанализа хеш-функций, что привело к созданию более надёжных алгоритмов. Документ стал эталоном для описания криптографических алгоритмов в формате RFC, задав стандарт ясности и детализации спецификации. Несмотря на свою уязвимость, MD5 остаётся важным историческим примером как успешной, так и неудачной конструкции хеш-функции.

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

• RFC 1321 содержит не только описание алгоритма, но и полный код реализации на языке C, что способствовало его быстрому распространению.
• MD5 — это аббревиатура от «Message Digest 5», то есть «дайджест сообщения версии 5».
• Алгоритм MD5 был разработан до того, как стали широко известны методы линейного и дифференциального криптоанализа, что объясняет его уязвимости.

Источники

• RFC 1321 — The MD5 Message-Digest Algorithm (R. Rivest, 1992)
• Handbook of Applied Cryptography (Menezes, van Oorschot, Vanstone, 1996)
• Wang, X., & Yu, H. (2005). How to Break MD5 and Other Hash Functions. Advances in Cryptology — EUROCRYPT 2005.
• Stevens, M., Sotnikov, A., & Lenstra, A. (2009). Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate. Advances in Cryptology — CRYPTO 2009.