Хеш-функция MD5¶

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

¶История

¶Разработка и стандартизация

MD5 была создана как замена более ранним функциям MD4 (также разработанным Ривестом) и MD2. В 1992 году алгоритм был опубликован в документе RFC 1321, который стал стандартом Интернета. Изначально MD5 предназначалась для использования в криптографических протоколах, таких как цифровые подписи и аутентификация сообщений.

¶Уязвимости и критика

Первые признаки слабости MD5 были обнаружены в 1996 году, когда криптоаналитик Ганс Доббертин показал, что функция не полностью устойчива к коллизиям. В 2004 году китайские исследователи Сяоюнь Ван и Хунбо Ю опубликовали метод, позволяющий находить коллизии MD5 за практическое время (на обычном компьютере). К 2008 году появились инструменты, способные создавать два разных файла с одинаковым MD5-хешем за секунды. После этого MD5 была признана непригодной для криптографических целей, хотя её использование в некритичных приложениях сохраняется.

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

¶Входные данные

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 операций в каждом). В каждом раунде используются нелинейные функции (F, G, H, I), циклические сдвиги и константы, полученные из синусоидальной функции. Результаты раундов суммируются с текущими значениями A, B, C, D.
2. Выход: после обработки всех блоков значения A, B, C, D объединяются в 128-битную строку (в порядке little-endian), которая и является дайджестом MD5.

¶Пример

Для пустой строки MD5-хеш равен d41d8cd98f00b204e9800998ecf8427e. Для строки «The quick brown fox jumps over the lazy dog» — 9e107d9d372bb6826bd81d3542a419d6.

¶Характеристики

¶Длина выхода

128 бит (16 байт), обычно представляется в виде 32-значного шестнадцатеричного числа.

¶Скорость

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

¶Устойчивость к коллизиям

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

¶Устойчивость к прообразу

Найти сообщение по заданному хешу (атака на первый прообраз) для MD5 всё ещё считается вычислительно сложной задачей, хотя существуют методы, снижающие сложность до 2^123,4 операций (вместо 2^128 для полного перебора). Однако для коротких паролей (например, до 6 символов) возможен перебор по радужным таблицам.

¶Применение

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

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

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

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

¶Цифровые подписи и сертификаты

До середины 2000-х годов MD5 применялась в инфраструктуре открытых ключей для создания цифровых подписей. В 2008 году исследователи продемонстрировали возможность подделки сертификата SSL с использованием коллизии MD5, после чего основные центры сертификации (например, VeriSign) прекратили использование MD5.

¶Дубликаты файлов

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

¶Критика и альтернативы

¶Основные недостатки

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

¶Альтернативы

• SHA-1 (160 бит): также устарела, найдены коллизии (2017 год).
• SHA-2 (SHA-256, SHA-512): современный стандарт, рекомендованный для криптографических целей.
• SHA-3: новейший стандарт, основанный на алгоритме Keccak.
• BLAKE2: быстрая и безопасная альтернатива, используемая в некоторых криптовалютах.
• bcrypt, scrypt, Argon2: специализированные функции для хеширования паролей, устойчивые к перебору.

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

• MD5 является частью стандарта цифровых подписей DSS (Digital Signature Standard) в некоторых версиях, хотя в настоящее время не рекомендуется к использованию.
• В 2013 году компания Microsoft объявила, что Windows 8.1 больше не использует MD5 для проверки целостности системных файлов.
• Алгоритм MD5 лёг в основу более сложных функций, таких как MD6 (предложен Ривестом в 2008 году, но не стандартизирован).
• В некоторых базах данных (например, MySQL) до версии 8.0 функция MD5() использовалась для хеширования паролей, что приводило к уязвимостям.

¶Источники

• RFC 1321: The MD5 Message-Digest Algorithm (1992)
• Wang, X., Yu, H. «How to Break MD5 and Other Hash Functions» (2004)
• Dobbertin, H. «The Status of MD5 After a Recent Attack» (1996)
• Stevens, M. et al. «Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate» (2009)
• NIST Special Publication 800-107: Recommendation for Applications Using Approved Hash Algorithms