MD5

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

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

Разработка MD5 началась в 1990 году как усиленная версия предшествующей функции MD4, также созданной Ривестом. MD4, опубликованная в 1990 году, была первой в семействе Message Digest, но уже в 1991 году были обнаружены её уязвимости. В ответ на это Ривест представил MD5 в апреле 1992 года в документе RFC 1321. Основные изменения по сравнению с MD4 включали добавление дополнительного раунда преобразований, усложнение нелинейных функций и изменение констант, что должно было повысить устойчивость к атакам.

В 1990-е и начале 2000-х годов MD5 стала одной из самых популярных хеш-функций в мире. Она использовалась в протоколах SSL/TLS, в системах аутентификации Unix (в виде MD5-хешей паролей), в программах для проверки целостности файлов (например, утилита md5sum) и в качестве основы для некоторых алгоритмов цифровой подписи.

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

MD5 обрабатывает входное сообщение блоками по 512 бит (64 байта). Процесс состоит из нескольких этапов:

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

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

1. Обработка блоков: каждый 512-битный блок делится на 16 32-битных слов. Затем выполняется четыре раунда (по 16 шагов в каждом) нелинейных преобразований. На каждом шаге используется одна из четырёх нелинейных функций (F, G, H, I), константа, сдвиг и текущее слово блока. Результат каждого шага обновляет значения регистров A, B, C, D.
2. Вывод: после обработки всех блоков содержимое четырёх регистров (A, B, C, D) конкатенируется в обратном порядке (младший байт первым) и образует 128-битный дайджест.

Математически алгоритм является детерминированным: одно и то же входное сообщение всегда даёт один и тот же дайджест.

Применение

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

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

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

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

В ранних версиях Unix и в некоторых веб-приложениях MD5 использовалась для хеширования паролей. Вместо хранения пароля в открытом виде система хранила его MD5-дайджест. При аутентификации введённый пароль хешировался, и результат сравнивался с хранящимся значением. Однако из-за высокой скорости вычисления MD5 и уязвимости к атакам по словарю и радужным таблицам такой подход сейчас считается небезопасным. Современные системы используют медленные хеш-функции (например, bcrypt, scrypt, Argon2) с добавлением соли.

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

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

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

Криптостойкость MD5 была поставлена под сомнение вскоре после её публикации. Основные слабости связаны с возможностью нахождения коллизий и атак на прообраз.

Коллизии

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

• 1996 год: Ханс Доббертин (Hans Dobbertin) объявил о нахождении коллизии для сжатия MD5, хотя полная функция оставалась стойкой.
• 2004 год: группа китайских исследователей (Ван Сяоюнь, Фэн Дэнго, Лай Сюэцзя, Юй Хунбо) на конференции CRYPTO 2004 представила метод нахождения коллизий для полной MD5 за время, меньшее одного часа на обычном компьютере. Это стало поворотным моментом.
• 2007 год: исследователи продемонстрировали возможность создания двух разных исполняемых файлов с одинаковой MD5-суммой, что имело практические последствия для безопасности.
• 2008 год: группа учёных, включая Александра Сотникова, представила метод создания поддельного SSL-сертификата, который имел ту же MD5-сумму, что и легитимный сертификат, что позволило бы проводить атаки «человек посередине» (man-in-the-middle). Это фактически похоронило использование MD5 в PKI (инфраструктуре открытых ключей).

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

Атака на прообраз — это нахождение сообщения по его хешу. Для MD5 не было найдено эффективных практических атак на первый прообраз (нахождение сообщения по дайджесту), однако теоретическая стойкость снижена. Атаки на второй прообраз (нахождение другого сообщения с тем же хешем, что и у заданного) также возможны, но требуют значительно больше ресурсов, чем атаки на коллизии.

Последствия

К 2010 году большинство крупных организаций и стандартов (NIST, IETF) официально рекомендовали отказаться от MD5 в пользу более стойких функций, таких как SHA-2 или SHA-3. В операционных системах и программном обеспечении поддержка MD5 для криптографических целей (например, в качестве алгоритма подписи) была поэтапно прекращена.

Современное состояние

В настоящее время MD5 не рекомендуется для использования в системах, где требуется криптографическая стойкость, то есть защита от злонамеренной подделки данных. Её применение оправдано только в не криптографических контекстах:

• Контрольные суммы для некритичных данных: проверка целостности файлов при отсутствии атакующего (например, при скачивании с доверенного зеркала).
• Идентификация дубликатов: в системах хранения данных (дедупликация) для быстрого сравнения файлов, где коллизия маловероятна и не приведёт к катастрофическим последствиям.
• Некриптографические хеш-таблицы: для равномерного распределения ключей.

В криптографии её полностью заменили функции семейства SHA-2 (SHA-256, SHA-512) и SHA-3. Для хранения паролей используются специализированные функции (bcrypt, PBKDF2, Argon2).

Источники

• RFC 1321 — The MD5 Message-Digest Algorithm (1992).
• Wang, X., Feng, D., Lai, X., Yu, H. (2004). Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. CRYPTO 2004.
• Stevens, M., Lenstra, A., de Weger, B. (2007). Chosen-Prefix Collisions for MD5 and Applications. International Journal of Applied Cryptography.
• Сотников, А. (2008). MD5 considered harmful today: Creating a rogue CA certificate.