Войти
В криптографии атака коллизией на криптографический хэш пытается найти два входа, дающих одно и то же значение хеш-функции, то есть коллизию хэша. Это контрастирует с атакой на прообраз, где указывается конкретное целевое хеш-значение.
Существует примерно два типа атак с коллизией:
В более общем смысле :
С математической точки зрения атака на коллизию находит два разных сообщения m1 и m2, так что hash (m1) = hash (m2). В классической коллизионной атаке злоумышленник не может контролировать содержимое любого сообщения, но они произвольно выбираются алгоритмом.
Так же, как шифры с симметричным ключом уязвимы для атак грубой силы, каждая криптографическая хеш-функция по своей природе уязвима для коллизий с использованием Атака в день рождения. Из-за проблемы дня рождения эти атаки выполняются намного быстрее, чем может быть грубая сила. Хэш из n бит может быть разбит за 2 раза (оценка хеш-функции).
Более эффективные атаки возможны при использовании криптоанализа для конкретных хэш-функций. Когда обнаруживается коллизионная атака и оказывается, что она быстрее, чем атака дня рождения, хеш-функция часто объявляется «сломанной». Конкуренция хэш-функций NIST была в значительной степени вызвана опубликованными атаками на коллизию двух очень часто используемых хэш-функций, MD5 и SHA-1. Атаки на столкновение с MD5 настолько улучшились, что по состоянию на 2007 год на обычном компьютере они занимают всего несколько секунд. Создаваемые таким образом конфликты хэшей обычно имеют постоянную длину и в значительной степени неструктурированы, поэтому их нельзя напрямую применять для атаки широко распространенных форматов документов или протоколов.
Однако обходные пути возможны при злоупотреблении динамическими конструкциями, присутствующими во многих форматах. Таким образом будут созданы два документа, которые максимально похожи, чтобы иметь одинаковое хеш-значение. Один документ будет показан органу для подписания, а затем подпись может быть скопирована в другой файл. Такой вредоносный документ может содержать два разных сообщения в одном и том же документе, но условно отображать одно или другое посредством незначительных изменений в файле:
Расширением атаки коллизии является атака коллизии с выбранным префиксом, которая специфична для Хэш-функции Меркла – Дамгарда. В этом случае злоумышленник может выбрать два произвольно разных документа, а затем добавить разные вычисленные значения, в результате чего все документы будут иметь одинаковое хеш-значение. Эта атака намного мощнее классической атаки столкновения.
С математической точки зрения, учитывая два разных префикса p1, p2, атака находит два придатка m1 и m2, такие что hash (p1 ∥ m1) = hash (p2 ∥ m2) (где ∥ - конкатенация операция).
В 2007 году против MD5 была обнаружена коллизионная атака с выбранным префиксом, требующая примерно двух оценок функции MD5. В документе также демонстрируются два сертификата X.509 для разных доменных имен с конфликтующими хэш-значениями. Это означает, что центр сертификации можно попросить подписать сертификат для одного домена, а затем этот сертификат (особенно его подпись) можно будет использовать для создания нового поддельного сертификата для олицетворения другого домена.
Реальная атака коллизий была опубликована в декабре 2008 года, когда группа исследователей безопасности опубликовала поддельный сертификат подписи X.509, который можно было использовать для олицетворения центра сертификации , принимая преимущество атаки на префиксную коллизию против хеш-функции MD5. Это означало, что злоумышленник мог выдать себя за любой веб-сайт, защищенный SSL, как посредник, тем самым нарушив проверку сертификатов, встроенную в каждый веб-браузер для защиты электронной торговли. Поддельный сертификат не может быть отозван настоящими властями, а также может иметь произвольно поддельный срок действия. Несмотря на то, что в 2004 году было известно, что MD5 был очень слабым, центры сертификации по-прежнему были готовы подписывать сертификаты, подтвержденные MD5, в декабре 2008 года, и по крайней мере один сертификат для подписи кода Microsoft все еще использовал MD5 в мае 2012 года.
Вредоносная программа Flame успешно использовала новый вариант атаки с выбранным префиксом для подмены подписи кода своих компонентов корневым сертификатом Microsoft, который по-прежнему использовал скомпрометированный алгоритм MD5.
В 2019 году исследователи обнаружили атаку коллизии с выбранным префиксом против SHA-1 со сложностью вычислений от 2 до 2 и стоимостью менее 100 000 долларов США. В 2020 году исследователи снизили сложность коллизионной атаки с выбранным префиксом против SHA-1 до 2.
Многие приложения криптографических хеш-функций не полагаются на устойчивость к коллизиям, таким образом, коллизионные атаки не влияют на их безопасность. Например, HMAC не уязвимы. Чтобы атака была полезной, злоумышленник должен контролировать ввод в хеш-функцию.
Поскольку алгоритмы цифровой подписи не могут эффективно подписывать большой объем данных, большинство реализаций используют хеш-функцию для уменьшения («сжатия») объема данных. которые необходимо подписать до постоянного размера. Схемы цифровой подписи часто уязвимы для хеш-коллизий, если не используются такие методы, как рандомизированное хеширование.
Обычный сценарий атаки выглядит следующим образом:
В 2008 году исследователи использовали атаку с использованием коллизии с выбранным префиксом против MD5, используя этот сценарий, чтобы создать поддельный сертификат сертификат органа. Они создали две версии сертификата открытого ключа TLS , одна из которых оказалась законной и была отправлена на подпись центром сертификации RapidSSL. Вторая версия, имевшая такой же хеш MD5, содержала флаги, которые сигнализируют веб-браузерам о том, что они должны принять ее в качестве законного органа для выдачи произвольных других сертификатов.
В 2003 г. Атака отказа в обслуживании (DoS) была описана, в которой использовались хэш-коллизии для использования наихудшего времени выполнения поиска по хеш-таблице. Эта проблема затронула большинство основных языков программирования, поскольку они использовали более слабые хэш-функции.
