Криптография, защита компьютерных данных: информация, исследования, аналитика, экспертиза

Rambler's Top100

OZON.ru

Перейти на главную страницу

Карта сайта

Список статей

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

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

 

Менее, чем через две недели после выхода обсуждавшегося в предыдущей части статьи отчета ECRYPT, посвященного коллизиям для известных хэш-функций [1], вышла получившая широкую известность работа Арьена Ленстры (Arjen Lenstra), Сяйюн Ванг и Бена де Вегера (Benne de Weger) [2] (см. также [3], где представлена дополнительная информация, а наиболее полную информацию о данной атаке можно найти в работе [4], которая вышла несколько позднее). Данный коллектив криптоаналитиков представил метод конструирования пары значащих сертификатов формата X.509 [5] с эквивалентными хэш-значениями, вычисляемыми по алгоритму MD5. Электронная подпись сертификационного центра (см. описание инфраструктуры открытых ключей, например, в [6]), вычисленная для валидного сертификата, будет верна и для парного поддельного сертификата, что ставит под угрозу безопасность инфраструктуры открытых ключей (и использующих ее приложений) в случае применения в ней алгоритма MD5.

Пара сертификатов создается следующим образом (см. упрощенную схему на рис. 1, где поле, в котором использована коллизия, обозначено курсивом) [2]:

  1. Формируется шаблон сертификата, который для успешного формирования пары сертификатов должен соответствовать следующим ограничениям:
  1. Поля созданного шаблона сертификата заполняются осмысленной информацией (эквивалентной для обоих сертификатов), кроме значения полей модуля открытого ключа и электронной подписи.
  2. Поля, находящиеся до поля «Модуль открытого ключа», прогоняются через алгоритм хэширования MD5; результат их хэширования (без предусмотренного алгоритмом MD5 дополнения) является значением вектора инициализации, для которого выполняется поиск двухблочной коллизии.

Авторы атаки используют обсуждавшееся в предыдущей части статьи «двухстороннее расширение» коллизии – присоединение сообщения как перед, так и после двух дающих коллизию блоков:

MD5(t || x’ || q) = MD5(t || y’ || q).

В данном случае t – это поля сертификата до модуля открытого ключа, а MD5(t) – вектор инициализации для поиска двухблочной коллизии x’ и y’.

  1. Вычисляются 1024-битные строки x’ и y’, дающие коллизию. Данный шаг (на момент публикации работы [2]) являлся наиболее трудоемким и определял общую трудоемкость атаки.
  2. Найденные значения x’ и y’ представляют собой старшие части 2048-битных модулей n1 и n2, записываемых в сертификаты. Поскольку необходимо найти модуль целиком, авторы атаки по определенному алгоритму (подробно описан в [4]) выполняют поиск такого значения b, которое дает два корректных модуля n1 и n2:

n1 = x’ * 21024 + b;
n2 = y’ * 21024 + b.

Модуль n1 записывается в валидный, а n2 – в поддельный сертификат (или наоборот) – см. рис. 2.
Корректный модуль должен представлять собой произведение двух больших простых чисел (см. детали в [7]):

n1 = p1 * q1;
n2 = p2 * q2.

Знание разложения на множители модулей n1 и n2 позволяет вычислить соответствующие формируемым сертификатам секретные ключи; их вычисление выполняется на этом же этапе.

  1. После этого формирование пары сертификатов завершено. Любой из сертификатов может быть обработан алгоритмом хэширования MD5 и подписан; вычисленная для любого из пары сертификатов электронная подпись будет верна и для второго сертификата.

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

Данная атака может позволить владельцу такой пары сертификатов выдать проверенную ранее верную (созданную с помощью секретного ключа, соответствующего валидному сертификату) электронную подпись за неверную подменой валидного сертификата на поддельный (если такая подмена возможна). При этом проверка поддельного сертификата даст положительный результат, не позволяющий сомневаться в его валидности. Иными словами, пользователь может отказаться от собственной верной электронной подписи, что нарушает одно из основных свойств электронной подписи – невозможность отказа от авторства [10]. Еще несколько сценариев злоумышленного использования сконструированной пары сертификатов приведено в [4].

Описанная здесь атака по-прежнему не дает повода сомневаться в подписанных и опубликованных ранее (до выхода работы [9]) сертификатах, поскольку подделка подписи существующего сертификата (в отличие от подобного конструирования пары сертификатов) требует поиска прообраза, а не коллизии [4].

Следующую известную атаку на применения MD5 представили в мае 2005 г. Стефан Лакс (Stefan Lucks) и Магнус Даум (Magnus Daum) [11]. Фактически, их атака была во многом похожа на обсуждавшуюся в первой части статьи атаку Ондрея Микля: в качестве цели атаки был выбран формат документов Postscript, одним из свойств которого является возможность обработки интегрированного в документ кода. Аналогично атаке Микля, злоумышленник мог подготовить два документа с одним и тем же хэшем MD5 и следующим содержимым:

Как видно, здесь используется все то же свойство «двухстороннего расширения» коллизии. Если злоумышленнику удастся получить чью-либо электронную подпись одного из этих документов (а именно, того, который отображает корректный текст), данная подпись будет верна и в отношении документа, который отображает любой текст, в котором заинтересован злоумышленник.

Данная атака имеет явно более широкое практическое применение, чем атака Микля: для примера в [11] в качестве злоумышленника рассматривается секретарь, получающий электронную подпись под таким специально подготовленным документом у своего начальника.

Атака на Postscript была расширена в вышедшей в октябре 2005 г. работе [12] на ряд других форматов документов, в частности:

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

Отметим, что описанные здесь атаки дали криптоаналитикам серьезный повод поставить под сомнение целесообразность использования схемы Меркля-Дамгаарда из-за присущей ей возможности «расширения» коллизий [12].

Литература

  1. Recent Collision Attacks on Hash Functions: ECRYPT Position Paper. // http://www.ecrypt.eu.org – Revision 1.1 – 17. February 2005.
  2. Lenstra A., Wang X., de Weger B. Colliding X.509 Certificates. // http://eprint.iacr.org – version 1.0, 1st March 2005.
  3. Lenstra A., Wang X., de Weger B. Colliding X.509 Certificates based on MD5-collisions. // http://www.win.tue.nl – March 1, 2005. Latest update: March 17, 2006.
  4. Lenstra A., de Weger B. On the possibility of constructing meaningful hash collisions for public keys. // http://www.win.tue.nl.
  5. Housley R., Ford W., Polk W., Solo D. RFC 2459. Internet X.509 Public Key Infrastructure. Certificate and CRL Profile. // http://tools.ietf.org – January 1999.
  6. Панасенко С. П., Батура В. П. Основы криптографии для экономистов: учебное пособие. Под ред. Л. Г. Гагариной. – М.: Финансы и статистика, 2005 – 176 с.
  7. 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.
  8. ITU-T Recommendation X.690. Information technology – ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER). // http://www.itu.int – International Telecommunication Union – 07/2002.
  9. Wang X., Feng D., Lai X., Yu H. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. // http://eprint.iacr.org – Revised on August 17, 2004.
  10. Электронная цифровая подпись. Материал из Википедии – свободной энциклопедии. // http://ru.wikipedia.org.
  11. Lucks S., Daum M. The Story of Alice and her Boss: Hash Functions and the Blind Passenger Attack. // http://www.cits.rub.de.
  12. 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.

Рисунки:

  1. Пара сертификатов с эквивалентными и верными электронными подписями.
  2. Структура полей «Модуль открытого ключа».

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

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