Алгоритм хеширования MD5: уязвимости и применение

Введение

Алгоритм хеширования сбора сообщений

Алгоритм хеширования сообщений MD5 — широко используемая хеш-функция, генерирующая 128-битное хеш-значение. MD5 был разработан Рональдом Ривестом в 1991 году для замены более ранней хеш-функции MD4 и был специфицирован в 1992 году как RFC 1321. MD5 может использоваться в качестве контрольной суммы для проверки целостности данных от случайных повреждений. Исторически он широко применялся как криптографическая хеш-функция; однако было обнаружено множество уязвимостей. Он по-прежнему подходит для других некриптографических целей, например, для определения раздела для конкретного ключа в секционированной базе данных, и может быть предпочтительнее из-за меньших вычислительных затрат по сравнению с более новыми алгоритмами безопасного хеширования.

История и криптоанализ

MD5 является одним из семейства алгоритмов вычисления дайджеста сообщений, разработанных профессором Рональдом Ривестом из MIT (Rivest, 1992). Когда аналитические исследования показали, что предшественник MD5, MD4, вероятно, является небезопасным, Ривест разработал MD5 в 1991 году как безопасную замену. (Ханс Доббертин действительно позже обнаружил уязвимости в MD4.) В 1993 году Ден Боер и Босселерс представили ранний, хотя и ограниченный, результат обнаружения «псевдоколлизии» функции сжатия MD5; то есть, два различных вектора инициализации, которые производят идентичный дайджест. В 1996 году Доббертин объявил о коллизии функции сжатия MD5 (Dobbertin, 1996). Хотя это не было атакой на полную хеш-функцию MD5, она была достаточно близка, чтобы криптографы рекомендовали перейти на замену, такую как SHA 1 (которая также впоследствии была скомпрометирована) или RIPEMD 160. Размер хеш-значения (128 бит) достаточно мал, чтобы рассматривать возможность атаки «днем рождения». MD5CRK был распределенным проектом, начатым в марте 2004 года, чтобы продемонстрировать практическую небезопасность MD5 путем поиска коллизии с использованием атаки «днем рождения». MD5CRK завершился вскоре после 17 августа 2004 года, когда Сяоюнь Ван, Дэнгуо Фэн, Сюэцзя Лай и Хунбо Ю объявили об обнаружении коллизий для полной функции MD5. Их аналитическая атака, по сообщениям, заняла всего один час на кластере IBM p690. 1 марта 2005 года Арьен Ленстра, Сяоюнь Ван и Бенне де Вегер продемонстрировали построение двух сертификатов X.509 с разными открытыми ключами и одинаковым хеш-значением MD5, что является наглядно продемонстрированной практической коллизией. В конструкцию были включены закрытые ключи для обоих открытых ключей. Через несколько дней Властимил Клима описал улучшенный алгоритм, способный создавать коллизии MD5 за несколько часов на одном ноутбуке. 18 марта 2006 года Клима опубликовал алгоритм, который мог находить коллизию в течение одной минуты на одном ноутбуке, используя метод, который он назвал «туннелированием». Было опубликовано несколько исправлений RFC, связанных с MD5. В 2009 году киберкомандование США использовало хеш-значение MD5 своего заявления о миссии в качестве части своего официального символа. 24 декабря 2010 года Тао Сье и Дэнгуо Фэн объявили о первом опубликованном столкновении MD5 для одного блока (512 бит). (Предыдущие обнаружения коллизий основывались на многоблочных атаках.) Из соображений безопасности Сье и Фэн не раскрыли новый метод атаки. Они бросили вызов криптографическому сообществу, предложив вознаграждение в размере 10 000 долларов США первому, кто найдет другую 64-байтовую коллизию до 1 января 2013 года. Марк Стивенс принял вызов и опубликовал сталкивающиеся сообщения в одном блоке, а также алгоритм построения и исходный код. В 2011 году был утвержден информационный RFC 6151 для обновления соображений безопасности в MD5 и HMAC MD5.

MD5 is one in a series of message digest algorithms designed by Professor Ronald Rivest of MIT (Rivest, 1992). When analytic work indicated that MD5's predecessor MD4 was likely to be insecure, Rivest designed MD5 in 1991 as a secure replacement. (Hans Dobbertin did indeed later find weaknesses in MD4.) In 1993, Den Boer and Bosselaers gave an early, although limited, result of finding a "pseudo collision" of the MD5 compression function; that is, two different initialization vectors that produce an identical digest. In 1996, Dobbertin announced a collision of the compression function of MD5 (Dobbertin, 1996). While this was not an attack on the full MD5 hash function, it was close enough for cryptographers to recommend switching to a replacement, such as SHA 1 (also compromised since) or RIPEMD 160. The size of the hash value (128 bits) is small enough to contemplate a birthday attack. MD5CRK was a distributed project started in March 2004 to demonstrate that MD5 is practically insecure by finding a collision using a birthday attack. MD5CRK ended shortly after 17 August 2004, when collisions for the full MD5 were announced by Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu. Their analytical attack was reported to take only one hour on an IBM p690 cluster. On 1 March 2005, Arjen Lenstra, Xiaoyun Wang, and Benne de Weger demonstrated construction of two X.509 certificates with different public keys and the same MD5 hash value, a demonstrably practical collision. The construction included private keys for both public keys. A few days later, Vlastimil Klima described an improved algorithm, able to construct MD5 collisions in a few hours on a single notebook computer. On 18 March 2006, Klima published an algorithm that could find a collision within one minute on a single notebook computer, using a method he calls tunneling. Various MD5 related RFC errata have been published. In 2009, the United States Cyber Command used an MD5 hash value of their mission statement as a part of their official emblem. On 24 December 2010, Tao Xie and Dengguo Feng announced the first published single block (512 bit) MD5 collision. (Previous collision discoveries had relied on multi block attacks.) For "security reasons", Xie and Feng did not disclose the new attack method. They issued a challenge to the cryptographic community, offering a US$10,000 reward to the first finder of a different 64 byte collision before 1 January 2013. Marc Stevens responded to the challenge and published colliding single block messages as well as the construction algorithm and sources. In 2011 an informational RFC 6151 was approved to update the security considerations in MD5 and HMAC MD5.

Безопасность

Одно из основных требований к любой криптографической хеш-функции заключается в том, чтобы вычислительно было невозможно найти два различных сообщения, дающих одинаковое хеш-значение. MD5 катастрофически не удовлетворяет этому требованию. 31 декабря 2008 года Институт программной инженерии CMU пришел к выводу, что MD5 фактически "криптографически скомпрометирован и непригоден для дальнейшего использования". Уязвимости MD5 были использованы на практике, наиболее известным примером является вредоносное ПО Flame в 2012 году. По состоянию на 2019 год MD5 продолжает широко использоваться, несмотря на хорошо задокументированные уязвимости и отказ от его использования экспертами по безопасности. Более того, существует атака на основе коллизий с заданным префиксом, позволяющая получить коллизию для двух входных данных с указанными префиксами за несколько секунд, используя стандартное вычислительное оборудование (сложность 2<sup>39</sup>). Возможность поиска коллизий значительно упростилась благодаря использованию стандартных графических процессоров. На графическом процессоре NVIDIA GeForce 8400GS можно вычислить 16–18 миллионов хешей в секунду. NVIDIA GeForce 8800 Ultra способна вычислять более 200 миллионов хешей в секунду. Эти атаки, направленные на поиск хешей и коллизий, были продемонстрированы публично в различных ситуациях, включая коллизии файлов документов и цифровых сертификатов. По состоянию на 2019 год, одна четверть широко используемых систем управления контентом по-прежнему использовала MD5 для хеширования паролей.

Обзор вопросов безопасности

В 1996 году в дизайне MD5 была обнаружена уязвимость. Хотя в то время она не рассматривалась как критическая, криптографы стали рекомендовать использование других алгоритмов, таких как SHA-1, который впоследствии также оказался уязвим. В 2004 году было продемонстрировано, что MD5 не обладает устойчивостью к коллизиям. Следовательно, MD5 не пригоден для приложений, таких как SSL-сертификаты или цифровые подписи, которые зависят от этого свойства для обеспечения цифровой безопасности. Исследователи также обнаружили более серьезные недостатки в MD5 и описали осуществимую коллизионную атаку – метод создания пары входных данных, для которых MD5 генерирует одинаковые контрольные суммы. В 2005, 2006 и 2007 годах были достигнуты дальнейшие успехи в взломе MD5. В декабре 2008 года группа исследователей использовала эту технику для подделки действительности SSL-сертификата. По состоянию на 2010 год, Институт программной инженерии CMU считает MD5 "криптографически скомпрометированным и непригодным для дальнейшего использования", и большинство государственных приложений в США теперь требуют использования семейства хеш-функций SHA-2. В 2012 году вредоносное ПО Flame использовало уязвимости MD5 для подделки цифровой подписи Microsoft.

Уязвимости столкновения

В 1996 году были обнаружены коллизии в функции сжатия MD5, и Ханс Доббертин написал в техническом бюллетене RSA Laboratories: "Представленная атака пока не представляет угрозы для практического применения MD5, но она довольно близка. В будущем MD5 не следует использовать там, где требуется хэш-функция, устойчивая к коллизиям". В 2005 году исследователям удалось создать пары документов PostScript и сертификатов X.509 с одинаковым хэшем. Позже в том же году разработчик MD5 Рон Ривест написал, что "md5 и sha1 однозначно взломаны (с точки зрения устойчивости к коллизиям)". 30 декабря 2008 года группа исследователей на 25-м Конгрессе хаоса сообщила о том, как они использовали коллизии MD5 для создания промежуточного сертификата центра сертификации, который казался легитимным при проверке его MD5-хэша, чтобы изменить обычный SSL-сертификат, выданный RapidSSL, на рабочий сертификат ЦС для этого эмитента, который затем можно было использовать для создания других сертификатов, выглядящих легитимными и выданными RapidSSL. VeriSign, эмитенты сертификатов RapidSSL, заявили, что прекратили выдачу новых сертификатов с использованием MD5 в качестве контрольной суммы для RapidSSL после объявления об уязвимости. Хотя Verisign отказались отзывать существующие сертификаты, подписанные с использованием MD5, их ответ был признан достаточным авторами эксплойта (Александр Сотиров, Марк Стивенс, Джейкоб Аппельбаум, Арьен Ленстра, Дэвид Молнар, Даг Арне Освик и Бенне де Вегер). Исследователи в области SSL написали: "Наш ожидаемый эффект заключается в том, что центры сертификации прекратят использовать MD5 при выдаче новых сертификатов. Мы также надеемся, что использование MD5 в других приложениях будет пересмотрено". Разница между двумя образцами заключается в том, что старший бит в каждом полубайте был инвертирован. Например, 20-й байт (смещение 0x13) в верхнем образце, 0x87, равен 10000111 в двоичном виде. Старший бит в байте (также старший бит в первом полубайте) инвертируется, чтобы получить 00000111, что равно 0x07, как показано в нижнем образце. Позже также было обнаружено, что можно построить коллизии между двумя файлами с отдельно выбранными префиксами. Этот метод был использован при создании поддельного сертификата ЦС в 2008 году. В 2014 году Антон Кузнецов предложил новый вариант параллельного поиска коллизий с использованием MPI, который позволил найти коллизию за 11 часов на вычислительном кластере.

In 1996, collisions were found in the compression function of MD5, and Hans Dobbertin wrote in the RSA Laboratories technical newsletter, "The presented attack does not yet threaten practical applications of MD5, but it comes rather close in the future MD5 should no longer be implemented where a collision resistant hash function is required." In 2005, researchers were able to create pairs of PostScript documents and X.509 certificates with the same hash. Later that year, MD5's designer Ron Rivest wrote that "md5 and sha1 are both clearly broken (in terms of collision resistance)". On 30 December 2008, a group of researchers announced at the 25th Chaos Communication Congress how they had used MD5 collisions to create an intermediate certificate authority certificate that appeared to be legitimate when checked by its MD5 hash. to change a normal SSL certificate issued by RapidSSL into a working CA certificate for that issuer, which could then be used to create other certificates that would appear to be legitimate and issued by RapidSSL. VeriSign, the issuers of RapidSSL certificates, said they stopped issuing new certificates using MD5 as their checksum algorithm for RapidSSL once the vulnerability was announced. Although Verisign declined to revoke existing certificates signed using MD5, their response was considered adequate by the authors of the exploit (Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, and Benne de Weger). The SSL researchers wrote, "Our desired impact is that Certification Authorities will stop using MD5 in issuing new certificates. We also hope that use of MD5 in other applications will be reconsidered as well." The difference between the two samples is that the leading bit in each nibble has been flipped. For example, the 20th byte (offset 0x13) in the top sample, 0x87, is 10000111 in binary. The leading bit in the byte (also the leading bit in the first nibble) is flipped to make 00000111, which is 0x07, as shown in the lower sample. Later it was also found to be possible to construct collisions between two files with separately chosen prefixes. This technique was used in the creation of the rogue CA certificate in 2008. A new variant of parallelized collision searching using MPI was proposed by Anton Kuznetsov in 2014, which allowed finding a collision in 11 hours on a computing cluster.

Уязвимость преимагера

В апреле 2009 года была опубликована атака на MD5, которая взламывает устойчивость MD5 к прообразам. Эта атака пока что является лишь теоретической, с вычислительной сложностью 2¹²³․⁴ для полного нахождения прообраза.

Приложения

MD5-дайджесты широко используются в сфере программного обеспечения для обеспечения определенной уверенности в целостности переданного файла. Например, файловые серверы часто предоставляют предварительно вычисленную контрольную сумму MD5 (известную как md5sum) для файлов, чтобы пользователь мог сравнить контрольную сумму загруженного файла с ней. Большинство операционных систем на базе Unix включают в свои дистрибутивы утилиты для вычисления MD5-суммы; пользователи Windows могут использовать встроенную функцию PowerShell "Get-FileHash", встроенную функцию командной строки "certutil -hashfile <имя_файла> MD5", установить утилиту Microsoft или использовать сторонние приложения. В Android ROM также используется этот тип контрольной суммы. Поскольку легко генерировать коллизии MD5, создатель файла может создать второй файл с той же контрольной суммой, поэтому этот метод не защищает от некоторых видов злонамеренного вмешательства. В некоторых случаях контрольной сумме нельзя доверять (например, если она получена по тому же каналу, что и загружаемый файл), в этом случае MD5 может выполнять только функцию проверки ошибок: он обнаружит поврежденную или неполную загрузку, что становится более вероятным при загрузке больших файлов. Ранее MD5 использовался для хранения одностороннего хэша пароля, часто с применением растяжки ключа. NIST не включает MD5 в список рекомендуемых хэшей для хранения паролей. MD5 также используется в сфере электронного обнаружения (eDiscovery) для предоставления уникального идентификатора каждому документу, обмениваемому в ходе юридического процесса обнаружения доказательств. Этот метод может заменить систему нумерации штампов Бейтса, используемую на протяжении десятилетий при обмене бумажными документами. Как и ранее, такое использование не рекомендуется из-за простоты организации коллизий.

Алгоритм

MD5 обрабатывает сообщение переменной длины, преобразуя его в выходные данные фиксированной длины – 128 бит. Входное сообщение разбивается на блоки по 512 бит (шестнадцать 32-битных слов); сообщение дополняется таким образом, чтобы его длина делилась на 512. Дополнение происходит следующим образом: сначала к концу сообщения добавляется один бит, равный 1. Затем добавляется столько нулей, сколько необходимо, чтобы длина сообщения стала на 64 бита меньше кратного 512. Оставшиеся биты заполняются 64 битами, представляющими длину исходного сообщения по модулю 264. Основной алгоритм MD5 оперирует 128-битным состоянием, разделенным на четыре 32-битных слова, обозначаемых A, B, C и D. Они инициализируются определенными фиксированными константами. Основной алгоритм затем последовательно использует каждый 512-битный блок сообщения для изменения состояния. Обработка блока сообщения состоит из четырех аналогичных этапов, называемых раундами; каждый раунд состоит из 16 аналогичных операций, основанных на нелинейной функции F, модульном сложении и циклическом сдвиге влево. На рисунке 1 показана одна операция в рамках раунда. Существует четыре возможных функции; в каждом раунде используется различная функция: обозначают операции исключающее ИЛИ, И, ИЛИ и НЕ соответственно.