29 мая 2013
Обзор атак на приложения и протоколы, использующие алгоритм MD5
Часть 5
В конце 2006 г. очередного масштабного успеха в части атак на алгоритм MD5 и его приложения добились Стивенс, Ленстра и де Вегер. В ряде своих работ, вышедших в 2006-2007 гг. (в частности, в работах [1-3]), они предложили методику поиска коллизий для сообщений, префиксы которых имеют различающиеся хэш-значения (коллизия с выбранным префиксом – chosen-prefix collision). В качестве практического примера применения данной методики ее авторы разработали способ конструирования пар сертификатов X.509, принадлежащих различным пользователям и имеющих различающиеся значения открытых ключей, но при этом дающих коллизию.
Во второй и третьей частях статьи мы рассматривали различные варианты «расширения» коллизии MD5, включая предложенный в 2005 г. Ленстрой, Ванг и де Вегером метод конструирования пары сертификатов с различными значениями модулей открытых ключей, но с эквивалентными хэш-значениями. Все эти методы основывались на абстрактной коллизии, например, «двухстороннее расширение»:
MD5(t || x’ || q) = MD5(t || y’ || q),
в основе которого лежала двухблочная коллизия x’ и y’.
Двухблочная коллизия возникала при использовании нестандартного вектора инициализации – MD5(t). Тем не менее, префикс сообщения t был эквивалентен для обоих сообщений, что существенно сужало возможности по практическому использованию коллизий.
Принципиальное отличие коллизий с выбранным префиксом состоит в том, что начальные блоки дающих коллизию сообщений (префиксы) могут быть полностью различными: методика поиска коллизий с выбранным префиксом позволяет для любых сообщений x и y найти такие последовательности q1 и q2, что [1] (см. рис. 1):
MD5(x || q1) = MD5(y || q2.).
Такая коллизия существенно более универсальна и обладает несравнимо большими возможностями по применению на практике.
В [2] методика конструирования коллизии с выбранным префиксом описана подробно; ее основные этапы состоят в следующем (см. рис. 2):
- Выбираются сообщения, для которых будет формироваться коллизия, т. е. сообщения-префиксы x и y. Размер сообщений-префиксов должен быть сравним с 416 по модулю 512; при необходимости, сообщения дополняются любыми данными до требуемого размера.
- Сообщения-префиксы дополняются 96-битовыми строками, которые в результате их обработки функцией сжатия алгоритма MD5 формируют между промежуточными состояниями Ak…Dk и Aksub>’…Dk’ разность специального формата.
- Результирующие сообщения дополняются несколькими (в основном варианте атаки – восемью) 512-битовыми блоками данных, каждая пара которых дает near-коллизию с меньшим количеством различающихся битов, чем предыдущая; в результате обработки последнего из этих блоков формируется коллизия.
Таким образом, значения q1 и q2 состоят из 96-битовых дополнений и восьми пар блоков, т. е. полный размер каждого из дополнений составляет 4192 битов. Трудоемкость поиска последовательностей q1 и q2 определяется, в основном, трудоемкостью поиска 96-битовых дополнений и составляет 250-252 операций. Авторы атаки предложили также ее вариант с эквивалентной трудоемкостью, в котором не требуется наличие 96-битовых дополнений, но количество пар дополнительных блоков увеличено до 14, что сужает возможности практического применения атаки [2].
Стивенс, Ленстра и де Вегер применили данную методику для создания пары сертификатов X.509 (которая будет рассмотрена далее), для чего ими были применены распределенные вычисления с использованием до 1200 компьютеров в течение 6 месяцев. При этом, в [2] сказано, что этот поиск шел не по оптимальному пути и, с использованием накопленного опыта, аналогичную атаку можно выполнить примерно за 2 месяца при наличии эквивалентных ресурсов.
Рис. 1 Коллизия с выбранным префиксом
Рис. 2 Структура пары сообщений
Рассмотрим способ конструирования пары сертификатов с эквивалентными и верными электронными подписями, но с различными уникальными именами пользователей, основанный на коллизии с выбранным префиксом и подробно описанный в [2] и [3]. Последовательность создания пары сертификатов состоит из следующих шагов (см. рис. 3):
- Формируется шаблон сертификата. Как и в более ранних работах Ленстры, Ванг и де Вегера (при создании пары сертификатов с эквивалентными именами пользователей – подробно см. в [4]), предполагается, что сертификаты должны предназначаться для использования в алгоритмах RSA, соответствовать формату X.509 и кодироваться методом ASN1.DER. Кроме того, для успешного формирования коллизии с выбранным префиксом поля каждого из сертификатов, находящиеся до поля «Модуль открытого ключа», должны иметь совокупный размер на 96 битов меньше кратного 64 байтам (512 битам).
- Данные поля сертификатов заполняются необходимой атакующим информацией, которая эквивалентна во всех полях, кроме следующих:
- полей серийных номеров сертификатов, которые являются уникальными для различных сертификатов;
- полей уникальных имен пользователей.
Отметим, что последнее поле является композитным и, помимо собственно имени пользователя, может содержать дополнительную информацию, в частности, об организации, в которой работает пользователь. Авторы атаки при создании первой пары сертификатов по своей методике присвоили им имена «Arjen K. Lenstra» и «Marc Stevens», после чего для обеспечения выравнивания согласно изложенному выше требованию использовали поле организации, записав в него, соответственно, значения «Collisionairs» и «Collision Factory».
Заполненные поля двух сертификатов (до поля «Модуль открытого ключа») представляют собой сообщения-префиксы x и y.
- Сообщения-префиксы (без предусмотренного алгоритмом MD5 дополнения) прогоняются через алгоритм хэширования MD5; в результате получаются два значения вектора инициализации, для которых будет осуществляться поиск коллизии.
- Коллизия формируется с помощью значений модуля открытого ключа n1 (для первого сертификата) и n2 (для второго сертификата), которые имеют следующую структуру:
n1 = Sa || Sb || B;
n2 = Sa’ || Sb’ || B,
где:
- Sa и Sa’ – это 96-битовые дополнения, приводящие к разности специального формата между промежуточными состояниями;
- Sb и Sb’ – это 8-блочные дополнения, приводящие к коллизии в результате обработки алгоритмом MD5;
- B – 4000-битовая последовательность, эквивалентная для обоих модулей (см. далее).
Рис. 3 Пара сертификатов с различными уникальными именами пользователей
Структура модулей n1 и n2 приведена на рис. 4.
Коллизия достигается с помощью вычисления пар значений (Sa, Sa’) и (Sb, Sb’), которые согласно описанной выше схеме поиска коллизии с выбранным префиксом представляют собой 4192-битовые последовательности q1 и q2:
q1 = Sa || Sb;
q2 = Sa’ || Sb’.
После данных значений сертификаты могут быть дополнены только эквивалентными последовательностями. Однако, необходимо сформировать корректные значения модулей n1 и n2, для чего выполняется (аналогично описанному в [4] поиску значений b, но с увеличенной размерностью) поиск такого 4000-битового значенияB, которое давало бы в результате два корректных (разлагаемых на произведение больших простых чисел) модуля размером 8192 битов каждый:
n1 = (Sa *24096 + Sb) * 24000 + B;
n2 = (Sa’ *24096 + Sb’) * 24000 + B.
Рис. 4 Структура модулей открытого ключа
После этого формирование пары сертификатов завершено. Любой из сертификатов может быть обработан алгоритмом хэширования MD5 и подписан; вычисленная для любого из пары сертификатов электронная подпись будет верна и для второго сертификата. При этом сертификаты будут принадлежать различным пользователям, что существенно усилит результативность атаки и позволит, в частности, подделывать подпись владельца парного сертификата. Авторы атаки, однако, отмечали в [2], что им не удалось найти доказуемый эффективный сценарий атаки с использованием такой пары сертификатов, поскольку для ее реализации злоумышленнику требуется контроль над сертификационным центром.
Отметим, что методика является достаточно гибкой и позволяет создавать другие варианты пар сертификатов, например, поля срока действия сертификатов также могут быть заполнены различной информацией – т. е. созданные сертификаты будут обладать различным сроком действия [2].
Наиболее эффектным применение коллизий с выбранным префиксом выглядит именно в части создания пар сертификатов, что не исключает любые другие из описанных ранее возможностей (например, описанные в [5] варианты использования коллизии в качестве переключателя функционала или содержимого программы или документа). Некоторые дополнительные сценарии атак с использованием коллизий с выбранным префиксом описаны, в частности, в [6].
Продолжение следует
Литература
- Stevens M., Lenstra A. K., de Weger B. Colliding X.509 Certificates for Different Identities. // http://www.win.tue.nl – October 23, 2006 – Last Updated January 1, 2009.
- 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.
- Stevens M., Lenstra A., de Weger B. Target Collisions for MD5 and Colliding X.509 Certificates for Different Identities. // http://eprint.iacr.org – Version 1.1 – 4th November 2006.
- Панасенко С. Обзор атак на приложения и протоколы, использующие алгоритм MD5, часть 3. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=40095 – 10.04.2013 г.
- 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.
- Stevens M. M. J. On Collisions for MD5. Master’s Thesis. // http://www.win.tue.nl – Eindhoven University of Technology – June 2007.
Об авторе:
Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.
С автором можно связаться: по телефонам (499)731-0000, (499)731-2050
или по E-mail serg@panasenko.ru
