Атака столкновения - Collision attack

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

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

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

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

Атака столкновения с выбранным префиксом
Для двух разных префиксов p 1 и p 2 найдите два придатка m 1 и m 2 такие, что hash ( p 1m 1 ) = hash ( p 2m 2 ), где обозначает операцию конкатенации .

Классическая атака на столкновение

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

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

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

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

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

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

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

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

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

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

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

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

Сценарии атак

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

Цифровые подписи

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

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

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

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

Хеш-флуд

Хеш-флуд - это атака типа «отказ в обслуживании», в которой использовались коллизии хешей для использования наихудшего случая (линейный зонд) при поиске в хеш-таблице . Первоначально он был описан в 2003 году. Чтобы выполнить такую ​​атаку, злоумышленник отправляет на сервер несколько фрагментов данных, которые имеют одно и то же значение, а затем пытается заставить сервер выполнить медленный поиск. Поскольку основное внимание в хэш-функциях, используемых в хэш-таблицах, уделялось скорости, а не безопасности, были затронуты большинство основных языков программирования, при этом новые уязвимости этого класса все еще проявлялись спустя десятилетие после первоначальной презентации.

Чтобы предотвратить переполнение хеш-функций, не делая хеш-функцию чрезмерно сложной, вводятся новые хеш-функции с ключами, цель которых заключается в том, что коллизии трудно обнаружить, пока ключ неизвестен. Они могут быть медленнее, чем предыдущие хэши, но их все же намного проще вычислить, чем криптографические хэши. По состоянию на 2021 г. , Daniel J. Bernstein «s SipHash (2012) является наиболее широко используемым хеш - функция этого класса. («Простые» хэши без ключей остаются безопасными для использования до тех пор, пока хеш-таблица приложения не управляется извне.)

Можно выполнить аналогичную атаку, чтобы заполнить фильтры Блума, используя (частичную) атаку по прообразу.

использованная литература

внешние ссылки