|
Обзор атак на приложения и протоколы, использующие алгоритм MD5, часть 3
© Сергей Панасенко, 2013
Менее, чем через две недели после выхода обсуждавшегося в предыдущей части статьи отчета ECRYPT, посвященного коллизиям для известных хэш-функций [1], вышла получившая широкую известность работа Арьена Ленстры (Arjen Lenstra), Сяйюн Ванг и Бена де Вегера (Benne de Weger) [2] (см. также [3], где представлена дополнительная информация, а наиболее полную информацию о данной атаке можно найти в работе [4], которая вышла несколько позднее). Данный коллектив криптоаналитиков представил метод конструирования пары значащих сертификатов формата X.509 [5] с эквивалентными хэш-значениями, вычисляемыми по алгоритму MD5. Электронная подпись сертификационного центра (см. описание инфраструктуры открытых ключей, например, в [6]), вычисленная для валидного сертификата, будет верна и для парного поддельного сертификата, что ставит под угрозу безопасность инфраструктуры открытых ключей (и использующих ее приложений) в случае применения в ней алгоритма MD5.
Пара сертификатов создается следующим образом (см. упрощенную схему на рис. 1, где поле, в котором использована коллизия, обозначено курсивом) [2]:
Авторы атаки используют обсуждавшееся в предыдущей части статьи «двухстороннее расширение» коллизии – присоединение сообщения как перед, так и после двух дающих коллизию блоков:
MD5(t || x’ || q) = MD5(t || y’ || q).
В данном случае t – это поля сертификата до модуля открытого ключа, а MD5(t) – вектор инициализации для поиска двухблочной коллизии x’ и y’.
n1 = x’ * 21024 + b;
n2 = y’ * 21024 + b.
Модуль n1 записывается в валидный, а n2 – в поддельный сертификат (или наоборот) – см. рис. 2.
Корректный модуль должен представлять собой произведение двух больших простых чисел (см. детали в [7]):
n1 = p1 * q1;
n2 = p2 * q2.
Знание разложения на множители модулей n1 и n2 позволяет вычислить соответствующие формируемым сертификатам секретные ключи; их вычисление выполняется на этом же этапе.
Таким образом, полученные сертификаты обладают идентичными и верными электронными подписями. Они содержат идентичную информацию, за исключением значений модуля открытого ключа, который различен, но корректен в каждом из сертификатов. Следовательно, существуют два различных секретных ключа, каждый из которых соответствует одному из сертификатов пары.
Данная атака может позволить владельцу такой пары сертификатов выдать проверенную ранее верную (созданную с помощью секретного ключа, соответствующего валидному сертификату) электронную подпись за неверную подменой валидного сертификата на поддельный (если такая подмена возможна). При этом проверка поддельного сертификата даст положительный результат, не позволяющий сомневаться в его валидности. Иными словами, пользователь может отказаться от собственной верной электронной подписи, что нарушает одно из основных свойств электронной подписи – невозможность отказа от авторства [10]. Еще несколько сценариев злоумышленного использования сконструированной пары сертификатов приведено в [4].
Описанная здесь атака по-прежнему не дает повода сомневаться в подписанных и опубликованных ранее (до выхода работы [9]) сертификатах, поскольку подделка подписи существующего сертификата (в отличие от подобного конструирования пары сертификатов) требует поиска прообраза, а не коллизии [4].
Следующую известную атаку на применения MD5 представили в мае 2005 г. Стефан Лакс (Stefan Lucks) и Магнус Даум (Magnus Daum) [11]. Фактически, их атака была во многом похожа на обсуждавшуюся в первой части статьи атаку Ондрея Микля: в качестве цели атаки был выбран формат документов Postscript, одним из свойств которого является возможность обработки интегрированного в документ кода. Аналогично атаке Микля, злоумышленник мог подготовить два документа с одним и тем же хэшем MD5 и следующим содержимым:
Как видно, здесь используется все то же свойство «двухстороннего расширения» коллизии. Если злоумышленнику удастся получить чью-либо электронную подпись одного из этих документов (а именно, того, который отображает корректный текст), данная подпись будет верна и в отношении документа, который отображает любой текст, в котором заинтересован злоумышленник.
Данная атака имеет явно более широкое практическое применение, чем атака Микля: для примера в [11] в качестве злоумышленника рассматривается секретарь, получающий электронную подпись под таким специально подготовленным документом у своего начальника.
Атака на Postscript была расширена в вышедшей в октябре 2005 г. работе [12] на ряд других форматов документов, в частности:
Во всех этих случаях авторы расширенной атаки смогли найти такие особенности форматов документов, которые позволили с использованием абстрактной коллизии создать пару документов с одинаковым хэш-значением MD5 и различным смысловым наполнением. Таким образом, область возможного практического применения подобных атак существенно увеличилась.
Отметим, что описанные здесь атаки дали криптоаналитикам серьезный повод поставить под сомнение целесообразность использования схемы Меркля-Дамгаарда из-за присущей ей возможности «расширения» коллизий [12].
Литература
Рисунки:
