Обзор атак на приложения и протоколы, использующие алгоритм MD5, часть 7

© Сергей Панасенко, 2013

Вернемся к работам, вышедшим в 2007 г., в частности, к рассмотренной в пятой части статьи работе [1], авторы которой предложили коллизии с выбранным префиксом и методику создания дающих коллизию пар сертификатов различных пользователей на их основе.
В ноябре 2007 г. вышла еще одна работа тех же авторов [2], в которой упоминается идея Эрика Верхеля (Eric Verheul) о том, что произвольные байты данных (требуемые для формирования коллизии) могут быть дописаны к информации, хранящейся во многих различных форматах, а не только к сертификатам формата X.509. Действительно, при разборе файлов какого-либо формата программное обеспечение часто (но далеко не всегда) использует только данные, размер которых указан в заголовке формата, полностью игнорируя данные, находящиеся за пределами этого размера (если таковые существуют). В качестве примера такого формата можно привести графический формат BMP, в котором есть несколько неконтролируемых областей [3]. Таким образом, вполне возможно расширение такого файла с целью формирования коллизии; при этом, дополнительные данные не портят формат файла и не мешают его обработке (см. крайне упрощенную схему на рис. 1).

Стивенс, Ленстра и де Вегер использовали данную идею и коллизии с выбранным префиксом для формирования двух исполняемых файлов Windows (Win32 executable – см., например, [4]), имеющих различную функциональность, но с одинаковым хэшем MD5 [2]. В результате под реальной угрозой оказались, как минимум, следующие применения алгоритма хэширования MD5:

• контроль целостности программных модулей на основе их хэш-значений;
• цифровые подписи программ, используемые для контроля их целостности и аутентичности при установке или обновлении; в качестве широко используемого примера данного применения MD5 в [2] приведена технология Microsoft Authenticode [5];
• репутационные базы, подтверждающие безопасность программных модулей, в том числе, на основе их хэш-значений; репутационные базы используются, в частности, в продуктах «Лаборатории Касперского» для контроля запуска программ [6].

Видно некоторое сходство данной атаки с атакой на документарные форматы, предложенной в [7] и описанной в третьей части статьи. Однако, последствия данной атаки могут быть несравнимо более разрушительны, поскольку она дает возможность злоумышленнику подменять именно исполняемые файлы и внедрять различного рода зловредные программы вместо легальных.
Как и многие из рассмотренных ранее атак, данная атака использует коллизии, а не направлена на поиск прообраза, следовательно, программное обеспечение, разработанное до изобретения атаки с выбранным префиксом, остается вне подозрений. Но с момента выхода работ [1] и [2] перечисленные выше применения алгоритма MD5 нельзя считать безопасными. Работа [2] содержит очередную рекомендацию не использовать алгоритм MD5 в подобных применениях.
В 2008-2009 г. вышло несколько новых работ Стивенса, Ленстры и де Вегера, в том числе, в соавторстве с другими экспертами. Отметим, прежде всего, масштабную работу [8], которая усилила более ранние атаки тех же авторов по ряду направлений:

• Трудоемкость поиска коллизий с выбранным префиксом была принципиально уменьшена – до 2³⁹ операций с 2⁵⁰ – 2⁵² операций в [1]. Данного усиления атаки ее авторы добились за счет автоматизации поиска требуемых разностей между сообщениями, дающими коллизию, и переменными состояния на всех этапах обработки сообщений, что дало возможность определения оптимальных соотношений по сравнению с ручным поиском, а также за счет ряда других усовершенствований.
• С использованием альтернативного метода поиска коллизий, опубликованного в [9] (и обсуждавшегося ранее в [10]), в работе [8] предложен еще один метод поиска коллизий с выбранным префиксом, в котором существенно уменьшен размер дополнений к значащим сообщениям, дающим коллизию (см. пятую часть статьи), – с 4192 до 596 битов. Трудоемкость данного метода составляет около 2^53,2 операций, но он имеет существенно более широкое практическое применение, поскольку позволяет, например, создавать пары дающих коллизии сертификатов с модулями открытых ключей существенно меньших размеров (по сравнению с непрактично большим размером в 8192 битов). При этом, метод позволяет варьировать размерами дополнений в указанном выше диапазоне: чем меньше дополнение, тем выше трудоемкость его поиска.

В работе [8] было предложено несколько реалистичных сценариев атак на приложения с использованием коллизий с выбранным префиксом, в том числе, не рассматриваемые ранее сценарии распределенных хранилищ информации, идентифицируемой хэш-значениями. Однако, наиболее интересна атака, описанная в [8] и [11], которая позволила ее авторам получить поддельный сертификат X.509, принадлежащий не конечному пользователю, а сертификационному центру (Certification Authority – CA). Полученный сертификат [11]:

• подписан одним из корневых CA;
• принимается всеми широко используемыми веб-браузерами при установлении соединения по защищенному протоколу HTTPS [12];
• следовательно, позволяет атакующему подписать любой сертификат, т. е. выпустить сертификат для любого поддельного веб-сайта, который будет считаться валидным.

Как отмечают авторы атаки, инфраструктура открытых ключей предназначалась именно для противодействия подобным видам атак.
Принцип атаки состоит в следующем:

• Атакующий запрашивает у вышестоящего (корневого) CA сертификат для некоторого своего веб-сайта; поскольку запрос на получение сертификата (Certificate Signing Request – CSR) является обычной операцией, CA подписывает сертификат и возвращает его атакующему.
• Атакующий заменяет подписанный сертификат веб-сайта заранее созданным поддельным сертификатом CA, хэш-значение которого эквивалентно хэш-значению подписанного сертификата. Таким образом, подпись поддельного сертификата CA оказывается верной.

Основная проблема при использовании данной атаки состоит в том, что при выпуске сертификата CA самостоятельно заполняет некоторые поля сертификата, следовательно, содержимое таких полей атакующий не контролирует. Авторы атаки на основе экспериментальных данных попытались предсказать содержимое данных полей [11]:

• атакуемый корневой CA, как выяснилось в результате экспериментов, подписывает сертификаты в полностью автоматическом режиме, устанавливая период действия сертификата с точностью до секунд: от времени T + (6 секунд) до времени T + (6 секунд) + (1 год), где T – время отправки пользователем запроса на сертификат; таким образом, предсказать значение данного поля атакующему относительно легко;
• несколько сложнее оказалось предсказать серийный номер сертификата с учетом того факта, что атакующему требовалось 3 дня для генерации пары сертификатов, дающих коллизию; данную проблему авторы атаки решили, периодически посылая запросы на получение сертификатов и анализируя разность серийных номеров между ними (на это у атакующих ушло несколько месяцев); в результате наблюдения авторы установили, что серийные номера присваиваются последовательно и за типичные трое суток с вечера четверга до вечера воскресенья разность серийных номеров попадает в диапазон от 800 до 1000; в результате авторы атаки применили следующий алгоритм предсказания серийного номера:

1. в четверг вечером атакующие посылают CSR для получения текущего серийного номера S;
2. в воскресенье вечером, за некоторое время до наступления требуемого времени T, атакующие периодически посылают запросы на получение сертификата для определения текущих серийных номеров, при необходимости увеличивая интенсивность запросов, чтобы за несколько секунд до наступления времени T CA выдал сертификат с серийным номером S + 999;
3. при наступлении времени T атакующие посылают запрос на получение сертификата, дающего коллизию; с достаточно большой вероятностью данный сертификат получит предсказуемый номер S + 1000.

Авторы атаки написали в [11], что после разработки данной методики предсказания они в течение нескольких выходных пытались создать по несколько (от одной до трех) пар сертификатов, но только четвертые выходные оказались удачными – один из сертификатов пользователей оказался заполнен предсказанными значениями.
Кроме того, ряд полей CA заполняет фиксированными значениями, которые атакующие определили с помощью сформированных ранее CSR.
Как и в более ранней работе [1], для формирования коллизии атакующие использовали поле модуля открытого ключа, поистине гениально решив две следующие сложные задачи:

• атакуемый CA ограничивал модуль открытого ключа размером 2048 битов (в [1] авторам атаки удалось создать сертификаты только с 8192-битовым модулем); данную проблему удалось решить с помощью упомянутого выше метода поиска коллизий с коротким дополнением к выбранным префиксам;
• авторы атаки поставили цель создать поддельный сертификат удостоверяющего центра, который отличается от сертификата конечного пользователя другим заполнением поля основных ограничений («Basic Constraints») [13]; проблема в том, что данное поле находится в расширениях сертификата (но принадлежит к числу обязательно поддерживаемых расширений согласно [13]), располагающихся после модуля открытого ключа – т. е. различия в сертификатах в этом случае невозможно скрыть за счет коллизии, «спрятанной» в модуль открытого ключа.

Кажущуюся нерешаемой вторую проблему авторы решили с помощью нестандартного расширения сертификата «Netscape Comment» (проприетарное расширение компании Netscape [14]), игнорируемого на момент выхода работ [8] и [11] всеми широко используемыми браузерами. Данное расширение представляет собой произвольный текстовый комментарий к сертификату и располагается непосредственно в конце сертификата – перед полем, определяющим алгоритм цифровой подписи, за которым идет непосредственно подпись сертификата. Используя наличие в CSR полей переменного размера (ряда полей, определяющих владельца сертификата), авторы атаки подобрали размер полей в легальном сертификате пользователя и поддельном сертификате CA таким образом, что поддельный сертификат CA оказался существенно более лаконичным. Это позволило:

• расположить (считая смещение от начала сертификатов) поле «Basic Constraints» сертификата CA раньше, чем поле модуля открытого ключа в сертификате пользователя;
• использовать для формирования коллизии различные, но находящиеся на одном смещении от начала сертификатов, поля: поле модуля открытого ключа в сертификате пользователя и поле комментария в поддельном сертификате CA; теоретически, поле комментария должно быть текстовым, но поскольку оно не обрабатывается, а полностью игнорируется, авторы атаки разместили в нем бинарные данные.

Упрощенно структура созданной атакующими пары сертификатов приведена на рис. 2, а сами сертификаты можно найти в работе [11].

Размер сконструированных выбранных префиксов составил по 500 байтов, из которых в сертификате пользователя 26 байтов оказались в составе модуля открытого ключа. Для формирования коллизии понадобились 96-битовые дополнения до размера, кратного размеру блока алгоритма хэширования, и 3 пары блоков, т. е. всего по 1632 бита на каждый из сертификатов. Оставшихся от 2048-битного модуля 208 битов хватило для формирования корректного с точки зрения алгоритма RSA [15] модуля открытого ключа (см. пятую часть статьи). В поддельном сертификате CA дающие коллизию 1632 бита попали в игнорируемое браузерами поле комментария.
Как отметили авторы атаки в [8], с ее помощью можно атаковать любое применение сертификатов X.509 при условии, что в инфраструктуре открытых ключей существует, как минимум, один CA, использующий при подписании сертификатов алгоритм хэширования MD5 и допускающий возможность предсказания сроков действия и серийных номеров сертификатов. Таким образом, данная атака применима на практике с незначительными ограничениями. Отметим, что авторы атаки намеренно «испортили» созданный ими поддельный сертификат CA, установив прошедший срок действия сертификата с 31 июля по 2 сентября 2004 г.
Помимо вывода о необходимости немедленного запрета использования алгоритма MD5, авторы атаки сделали еще одно важное заключение: никто (в данном случае – CA) не должен подписывать данные, формируемые кем-либо другим, без внесения в них случайных (как минимум, непредсказуемых) модификаций. В данном случае для обеспечения невозможности такой атаки было бы достаточно формирования серийных номеров сертификатов случайным образом [8].
Работа [11] была опубликована 30 декабря 2008 г. Реакция многих заинтересованных организаций (сертификационных центров, производителей браузеров, различных организаций в разных странах, имеющих отношение к информационной безопасности, и т. п.) была незамедлительной – в период с 30 декабря 2008 г. по середину января 2009 г. вышло множество различных рекомендаций, выполнение которых позволило бы противодействовать опубликованной атаке (см., в частности, публикации [16-20]). Такой же быстрой была реакция на данную работу различных компьютерных изданий, разместивших 30-31 декабря 2008 г. публикации, разъясняющие пользователям смысл работы [11] и степень опасности ее результатов (см., например, [21] и [22]). Поддельный сертификат сертификационного центра, имеющий верную цифровую подпись реального корневого CA, заставил очень многих экспертов поверить в необходимость принятия срочных мер. Известнейший криптолог Брюс Шнайер (Bruce Schneier) в своем блоге назвал работу [11] «великолепной» («The research is great») [23].
Что удивительно, история алгоритма MD5 на этом не закончилась; данный алгоритм продолжает в ряде случаев применяться до сих пор.

Литература

1. Stevens M., Lenstra A., de Weger B. Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities. // http://www.iacr.org – 2007.
2. Stevens M., Lenstra A., de Weger B. Vulnerability of software integrity and code signing applications to chosen-prefix collisions for MD5. // http://www.win.tue.nl – November 30, 2007 – Last Updated January 1, 2009.
3. BMP file format. From Wikipedia, the free encyclopedia. // http://en.wikipedia.org.
4. Pietrek M. An In-Depth Look into the Win32 Portable Executable File Format. // http://msdn.microsoft.com – MSDN Magazine – February 2002.
5. Signing and Checking Code with Authenticode. // http://msdn.microsoft.com – MSDN Library.
6. Продукт нового поколения для защиты корпоративной сети. // http://media.kaspersky.com – 2011 – ЗАО «Лаборатория Касперского».
7. Gebhardt M., Illies G., Schindler W. A Note of the Practical Value of Single Hash Collisions for Special File Formats. // http://csrc.nist.gov – 31 October 2005 – BSI, Bonn, Germany.
8. Stevens M., Lenstra A., de Weger B. Chosen-prefix Collisions for MD5 and Applications. // http://documents.epfl.ch.
9. Stevens M., Sotirov A., Appelbaum J., Lenstra A., Molnar D., Osvik D. A., de Weger B. Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate. // http://marc-stevens.nl – 2009.
10. Панасенко С. Обзор атак на алгоритм хэширования MD5: поиск коллизий, часть 4. // Sec.ru. – 17.01.2013 г.
11. Sotirov A., Stevens M., Appelbaum J., Lenstra A., Molnar D., Osvik D. A., de Weger B. MD5 considered harmful today. Creating a rogue CA certificate. // http://www.win.tue.nl – December 30, 2008 – Last Updated June 16, 2011.
12. HTTP Secure. From Wikipedia, the free encyclopedia. // http://en.wikipedia.org.
13. Cooper D., Santesson S., Farrell S., Boeyen S., Housley R., Polk W. RFC 5280. Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile. // http://tools.ietf.org – May 2008.
14. Netscape Certificate Extensions. Communicator 4.0 Version. // http://www.csie.nctu.edu.
15. Jonsson J., Kaliski B. RFC 3447. Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1. // http://tools.ietf.org – February 2003 – RSA Laboratories.
16. Microsoft Security Advisory (961509): Research proves feasibility of collision attacks against MD5. // http://technet.microsoft.com – December 30, 2008 – Microsoft Security TechCenter.
17. Nightingale J. MD5 Weaknesses Could Lead to Certificate Forgery. // http://blog.mozilla.org – Dec 30, 2008 – Mozilla Security Blog.
18. TC TrustCenter Response to SSL Vulnerability Paper. // http://www.trustcenter.de – 31st December 2008 – TrustCenter, Hamburg.
19. CERT Vulnerability Note VU#836068: MD5 vulnerable to collision attacks. // http://www.kb.cert.org – 31 Dec 2008 – Last revised 21 Jan 2009 – Computer Emergency Readiness Team, Software Engineering Institute, Carnegie Mellon University.
20. MD5 Hashes May Allow for Certificate Spoofing. // http://www.cisco.com – Revision 1.0 – 2009 January 15 – Cisco.
21. Stray J. Web browser flaw could put e-commerce security at risk. // http://news.cnet.com – CNET News – December 30, 2008.
22. Poulsen K. Researchers Use PlayStation Cluster to Forge a Web Skeleton Key. // http://wired.com – Wired.com – December 30, 2008.
23. Schneier B. Forging SSL Certificates. // http://www.schneier.com – December 31, 2008.

Рисунки:

1. Файл с неконтролируемой областью.
2. Структура пары сертификатов.

Предыдущая часть статьи

Следующая часть статьи