MD5

Что такое MD5 и как он устроен

MD5 (Message Digest 5) разработан Рональдом Ривестом в 1991 году как усиленная замена MD4 и описан в RFC 1321. Функция принимает данные любой длины и выдаёт 128 бит — 16 байт, которые записывают 32 шестнадцатеричными символами. Дайджест пустой строки известен наизусть многим администраторам: d41d8cd98f00b204e9800998ecf8427e, а для строки abc результат равен 900150983cd24fb0d6963f7d28e17f72.

Конструкция — классическая схема Меркла и Дамгора. Сообщение дополняется: приписывается один бит со значением 1, затем нули, затем 64-битная запись исходной длины в битах, так чтобы итог стал кратен 512 битам. Дополнение добавляется всегда, минимум 65 служебных бит, даже если длина изначально кратна блоку. Длина пишется от младшего байта к старшему, и вся внутренняя арифметика MD5 тоже работает с 32-битными словами в этом порядке — этим он отличается от SHA-2.

Внутреннее состояние — четыре 32-битных регистра с фиксированными начальными значениями 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476. Каждый 512-битный блок обрабатывается за 64 операции, разбитые на четыре раунда по 16. В раундах применяются четыре разные нелинейные функции от трёх регистров, циклические сдвиги на фиксированные величины и сложение по модулю 2 в степени 32. Шестьдесят четыре константы получены как целые части модуля синуса номера шага, умноженного на 2 в степени 32, — приём «чисел из ниоткуда», подтверждающий отсутствие спрятанной закладки. После 64 операций результат складывается с состоянием на входе блока, и обработка идёт дальше.

Терминологическая точность: MD5 — это хеш-функция, то есть алгоритм. Значение, которое она выдаёт для конкретного файла, правильно называть хеш-суммой файла, а не «его MD5».

Почему MD5 больше не считается безопасным

128-битный выход изначально давал запас в 2 в степени 64 операций до коллизии по парадоксу дней рождения — уже небольшой по нынешним меркам. Но обрушили MD5 не переборы, а структурные атаки.

В 2004 году группа Ван Сяоюнь показала способ строить пары сообщений с одинаковым дайджестом за считанные часы. К 2006 году время сократили до минут, сегодня коллизия MD5 считается на обычном ноутбуке за секунды и умещается в лабораторную работу студента.

Опаснее оказались коллизии с выбранным префиксом: атакующий берёт два произвольных, заранее заданных начала и достраивает к ним блоки так, чтобы итоговые дайджесты совпали. Эта техника, доведённая до практики в 2007–2009 годах, ломает подписи: подписывается один документ, а подпись оказывается действительной и для другого. В 2008 году исследователи изготовили работающий поддельный сертификат удостоверяющего центра. В 2012 году тем же приёмом воспользовалась вредоносная программа Flame, подделав подпись обновления Microsoft и распространяясь через штатный механизм обновлений.

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

Отдельный сюжет — пароли. MD5 очень быстр, видеокарта считает десятки миллиардов дайджестов в секунду, поэтому база паролей, захешированная MD5 без соли, вскрывается словарём почти целиком. Хранить пароли так нельзя ни в каком виде: нужны Argon2id, bcrypt или scrypt.

Где MD5 всё ещё уместен

Там, где противника нет, а есть только случайность и невнимательность, MD5 работает нормально и остаётся востребованным по инерции и ради совместимости.

Проверка успешности копирования и переноса больших массивов внутри доверенной сети: диск испортил байт или сеть оборвала передачу — расхождение вылезет.

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

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

Применять MD5 нельзя в электронной подписи и сертификатах, при проверке файлов из недоверенного источника, в схемах лицензирования и защиты от подделки, для хранения паролей и токенов. Российские регламенты юридически значимой подписи требуют ГОСТ Р 34.11-2012, и MD5 там не фигурирует.

MD5, SHA-256 и CRC: как выбирать

Три инструмента решают три разные задачи, и подмена одного другим — распространённая ошибка проектирования.

CRC-32 занимает 4 байта, считается почти бесплатно на аппаратной инструкции и предназначен исключительно для обнаружения помех в канале или на носителе. Подогнать данные под нужный остаток тривиально, поэтому от подмены он не защищает вовсе. CRC применяют в кадрах Ethernet, в архивах ZIP и в платёжных QR-кодах по спецификации EMVCo.

MD5 занимает 16 байт и стоит посередине: перемешивает данные качественно, но допускает подготовленные коллизии.

SHA-256 занимает 32 байта и рассчитан на противника. На процессорах с аппаратными инструкциями SHA-NI он к тому же обгоняет MD5 по скорости, так что довод «MD5 быстрее» на современном железе уже не работает.

Практическое правило: если результат проверки должен кого-то в чём-то убедить — что файл подлинный, что документ не менялся, что обновление выпущено вендором, — нужен SHA-256 или ГОСТ. Если проверка нужна только вам и только против случайного сбоя, хватит MD5, а на коротких сообщениях и CRC.

Частые вопросы

Можно ли расшифровать MD5?

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

Могут ли два разных файла иметь одинаковый MD5?

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

Почему MD5 всё ещё встречается на сайтах с дистрибутивами?

По инерции и ради старых инструментов: команда md5sum есть в любой системе, и многие сборочные конвейеры публикуют этот дайджест десятилетиями. Если рядом лежит SHA-256, проверяйте его. Если только MD5, он подтвердит, что файл скачался целиком, но не подтвердит, что его не подменили на зеркале.

Чем MD5 отличается от MD4 и MD6?

MD4 (1990) быстрее и слабее, коллизии для него находят мгновенно, применяется он теперь только в старых протоколах. MD5 добавил четвёртый раунд, отдельную константу на каждый шаг и изменил порядок обработки слов. MD6 предлагался в 2008 году на конкурс SHA-3, был отозван из финала и распространения не получил.

Сколько символов в MD5 и почему именно столько?

Тридцать два шестнадцатеричных символа. Выход функции — 128 бит, то есть 16 байт; каждый шестнадцатеричный символ кодирует ровно 4 бита, отсюда 128 делить на 4 равно 32. Длина не зависит от размера входа: и пустой файл, и образ на терабайт описываются строкой из 32 символов. По длине строки удобно опознавать алгоритм: 32 символа — MD5, 40 — SHA-1, 64 — SHA-256.