Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Существует примерно два типа коллизионных атак:

Атака столкновения
Найдите два разных сообщения m1 и m2, такие что hash (m1) = hash (m2) .

В более общем смысле:

Атака столкновения с выбранным префиксом
Для двух разных префиксов p1 и p2 найдите два придатка m1 и m2 такие, что hash (p1 ∥ m1) = hash (p2 ∥ m2) , где ∥ обозначает операцию конкатенации .

Классическая атака на столкновение [ править ]

С математической точки зрения, атака с коллизией находит два разных сообщения m1 и m2 , так что hash (m1) = hash (m2) . В классической коллизионной атаке злоумышленник не может контролировать содержимое любого сообщения, но они произвольно выбираются алгоритмом.

Подобно тому, как шифры с симметричным ключом уязвимы для атак грубой силы , каждая криптографическая хеш-функция по своей природе уязвима для коллизий с использованием атаки по случаю дня рождения . Из-за проблемы с днем рождения эти атаки выполняются намного быстрее, чем грубая сила. Хэш из n битов может быть разбит за 2 n / 2 раза (оценка хеш-функции).

Более эффективные атаки возможны при использовании криптоанализа для конкретных хеш-функций. Когда обнаруживается коллизионная атака и оказывается, что она быстрее, чем атака дня рождения, хеш-функция часто объявляется «сломанной». Конкуренция функция NIST хэш был в значительной степени индуцируется опубликованных атак столкновений против двух очень часто используемых хэш - функций, MD5 [1] и SHA-1 . Атаки на столкновение с MD5 настолько улучшились, что по состоянию на 2007 год на обычном компьютере они занимают всего несколько секунд. [2] Создаваемые таким образом конфликты хэшей обычно имеют постоянную длину и в значительной степени неструктурированы, поэтому не могут напрямую применяться для атаки широко распространенных форматов документов или протоколов.

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

  • Некоторые форматы документов, такие как PostScript или макросы в Microsoft Word , имеют условные конструкции. [3] [4] (if-then-else), которые позволяют проверить, имеет ли место в файле то или иное значение, чтобы контролировать то, что отображается.
  • Файлы TIFF могут содержать обрезанные изображения, при этом отображается другая часть изображения, не влияя на значение хеш-функции. [4]
  • PDF- файлы уязвимы для атак столкновения с помощью значения цвета (например, текст одного сообщения отображается белым цветом, который сливается с фоном, а текст другого сообщения отображается темным цветом), которое затем можно изменить, чтобы изменить содержание подписанного документа. [4]

Атака столкновения с выбранным префиксом [ править ]

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

С математической точки зрения, с учетом двух разных префиксов p1, p2 , атака находит два придатка m1 и m2, такие что hash (p1 ∥ m1) = hash (p2 ∥ m2) (где ∥ - операция конкатенации ).

В 2007 году против MD5 была обнаружена коллизионная атака с выбранным префиксом, потребовавшая примерно 250 оценок функции MD5. В документе также демонстрируются два сертификата X.509 для разных доменных имен с конфликтующими хэш-значениями. Это означает, что центр сертификации можно попросить подписать сертификат для одного домена, а затем этот сертификат (особенно его подпись) можно использовать для создания нового поддельного сертификата для олицетворения другого домена. [5]

Реальная атака коллизий была опубликована в декабре 2008 года, когда группа исследователей безопасности опубликовала поддельный сертификат подписи X.509, который можно было использовать для олицетворения центра сертификации , воспользовавшись атакой коллизионного префикса против хеш-функции MD5. Это означало, что злоумышленник мог выдавать себя за любой веб-сайт, защищенный SSL, как посредника , тем самым нарушая проверку сертификата, встроенную в каждый веб-браузер для защиты электронной коммерции . Поддельный сертификат не может быть отозван настоящими властями, а также может иметь произвольно поддельный срок действия. Хотя в 2004 году было известно, что MD5 очень слаб, [1]центры сертификации по-прежнему были готовы подписывать сертификаты, подтвержденные MD5, в декабре 2008 года [6], и по крайней мере один сертификат для подписи кода Microsoft все еще использовал MD5 в мае 2012 года.

Пламя вредоносных программ успешно используется новый вариант с использованием выбранного префикса столкновения атаки подменить код подписания его компонентов с помощью корневого сертификата Microsoft , которая до сих пор используется скомпрометированы алгоритм MD5. [7] [8]

В 2019 году исследователи обнаружили коллизионную атаку с выбранным префиксом против SHA-1 со сложностью вычислений от 2 66,9 до 2 69,4 и стоимостью менее 100 000 долларов США. [9] [10] В 2020 году исследователи снизили сложность коллизионной атаки с выбранным префиксом против SHA-1 до 2 63,4 . [11]

Сценарии атак [ править ]

Многие приложения криптографических хеш-функций не полагаются на устойчивость к коллизиям , таким образом, коллизионные атаки не влияют на их безопасность. Например, HMAC не уязвимы. [12] Чтобы атака была полезной, злоумышленник должен контролировать входные данные хэш-функции.

Цифровые подписи [ править ]

Поскольку алгоритмы цифровой подписи не могут эффективно подписывать большой объем данных, в большинстве реализаций используется хеш-функция для уменьшения («сжатия») количества данных, которые необходимо подписать, до постоянного размера. Схемы цифровой подписи часто уязвимы для хеш-коллизий, если не используются такие методы, как рандомизированное хеширование. [13]

Обычный сценарий атаки выглядит так:

  1. Мэллори создает два разных документа A и B, которые имеют одинаковое хеш-значение, т. Е. Конфликт. Мэллори пытается обманом заставить Боба принять документ B, якобы от Алисы.
  2. Мэллори отправляет документ А Алисе , которая соглашается с тем, что говорится в документе, подписывает свой хэш и отправляет подпись Мэллори.
  3. Мэллори прикрепляет подпись документа A к документу B.
  4. Затем Мэллори отправляет подпись и документ B Бобу , утверждая, что Алиса подписала B. Поскольку цифровая подпись совпадает с хэшем документа B, программное обеспечение Боба не может обнаружить подстановку.

В 2008 году исследователи применили коллизионную атаку с выбранным префиксом против MD5, используя этот сценарий, для создания поддельного сертификата центра сертификации. Они создали две версии сертификата открытого ключа TLS , одна из которых оказалась законной и была отправлена ​​на подпись в центр сертификации RapidSSL. Вторая версия, имевшая такой же хэш MD5, содержала флаги, которые сигнализируют веб-браузерам о том, что они должны принимать ее как законный орган для выдачи произвольных других сертификатов. [14]

Использование в DoS-атаках [ править ]

В 2003 году была описана атака типа «отказ в обслуживании» (DoS), в которой использовались хеш-коллизии для использования наихудшего времени выполнения поиска по хеш-таблице. [15] Эта проблема затронула большинство основных языков программирования, поскольку они использовали более слабые хэш-функции.

Ссылки [ править ]

  1. ^ a b Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD , Cryptology ePrint Archive Report 2004/199, 16 августа 2004 г., отредактировано 17 августа 2004 г. Получено 27 июля 2004 г. 2008 г.
  2. ^ MMJ Стивенс (июнь 2007). «О коллизиях для MD5» (PDF) . [...] мы можем найти коллизии для MD5 примерно за 2 сжатия 24,1 для рекомендованных IHV, что занимает прибл. 6 секунд на Pentium 4 2,6 ГГц. Цитировать журнал требует |journal=( помощь )
  3. ↑ Магнус Даум; Стефан Люкс . «Хеш-коллизии (атака отравленным сообщением)» . Eurocrypt 2005 основная сессия . Архивировано из оригинала на 2010-03-27.
  4. ^ a b c Макс Гебхардт; Георг Иллиес; Вернер Шиндлер. «Примечание о практическом значении коллизий единичных хэшей для специальных форматов файлов» (PDF) . Цитировать журнал требует |journal=( помощь )
  5. ^ Марк Стивенс; Арьен Ленстра; Бенн де Вегер (30 ноября 2007 г.). «Конфликты выбранного префикса для MD5 и конфликтующих сертификатов X.509 для разных удостоверений» . Цитировать журнал требует |journal=( помощь )
  6. ^ Александр Сотиров; и другие. (30 декабря 2008 г.). «Создание поддельного сертификата ЦС» . Архивировано из оригинала на 2012-04-18 . Проверено 7 октября 2009 .
  7. ^ «Microsoft выпускает совет по безопасности 2718704» . Microsoft . 3 июня 2012 года Архивировано из оригинала 7 июня 2012 года . Проверено 4 июня 2012 года .
  8. ↑ Марк Стивенс (7 июня 2012 г.). «CWI Cryptanalist обнаруживает новый вариант криптографической атаки в вредоносном ПО Flame Spy» . Centrum Wiskunde & Informatica . Проверено 9 июня 2012 года .
  9. ^ Catalin Cimpanu (2019-05-13). «Коллизионные атаки SHA-1 теперь действительно практичны и представляют собой надвигающуюся опасность» . ZDNet .
  10. ^ Гаэтан Леурент; Томас Пейрин (06.05.2019). «От коллизий к применению коллизий с выбранным префиксом к полному SHA-1» (PDF) .
  11. ^ Гаэтан Леурент; Томас Пейрин (05.01.2020). «SHA-1 - это беспорядок - конфликт первого выбранного префикса на SHA-1 и приложение к сети доверия PGP» (PDF) .
  12. ^ «Hash Collision Q&A» . Cryptography Research Inc. 15 февраля 2005 г. Архивировано из оригинала на 2008-07-17. Из-за того, как хэш-функции используются в конструкции HMAC, методы, использованные в этих недавних атаках, не применяются.
  13. ^ Шай Халеви и Хьюго Кравчик, рандомизированное хеширование и цифровые подписи
  14. ^ Александр Сотиров; Марк Стивенс; Яков Аппельбаум; Арьен Ленстра; Дэвид Мольнар; Даг Арне Освик; Бенн де Вегер (30 декабря 2008 г.). MD5 сегодня считается вредным . Конгресс Хаоса 2008.
  15. ^ "Хэш-DoS-атака на Wayback Machine" . Crossmatch, часть HID Global . Архивировано из оригинала на 2019-08-17 . Проверено 17 августа 2019 .

Внешние ссылки [ править ]

  • «Значимые коллизии», сценарии атак для использования криптографических хеш-коллизий.
  • Генераторы быстрых столкновений MD5 и MD4 - Bishop Fox (ранее Stach & Liu). Создавайте коллизии хешей MD4 и MD5, используя новый революционный код, который улучшает методы, первоначально разработанные Сяоюнь Ванем. Используя Pentium 4 1,6 ГГц, конфликты MD5 могут быть сгенерированы в среднем за 45 минут, а конфликты MD4 могут быть сгенерированы в среднем за 5 секунд. Первоначально выпущено 22 июня 2006 г.