stringtranslate.com

Атака столкновением

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

Существует два типа атак столкновений:

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

В более общем плане:

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

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

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

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

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

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

Атака с коллизией выбранного префикса

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

Математически это можно выразить так: если заданы два разных префикса p 1 , p 2 , атака находит два суффикса s 1 и s 2 , такие что hash ( p 1 ∥ s 1 ) = hash ( p 2 ∥ s 2 ) (где ∥ — операция конкатенации ).

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

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

Вредоносная программа Flame успешно использовала новую вариацию атаки с коллизией выбранного префикса для подделки подписи кода своих компонентов корневым сертификатом 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. Мэллори прикрепляет подпись из документа А к документу Б.
  4. Затем Мэллори отправляет подпись и документ B Бобу , утверждая, что Алиса подписала B. Поскольку цифровая подпись совпадает с хешем документа B, программное обеспечение Боба не может обнаружить подмену. [ необходима цитата ]

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

Хеш-флуд

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

Чтобы предотвратить хэш-флуд, не делая хэш-функцию слишком сложной, вводятся новые ключевые хэш-функции с целью обеспечения безопасности, чтобы коллизии было трудно обнаружить, пока ключ неизвестен. Они могут быть медленнее предыдущих хэшей, но их все равно гораздо проще вычислять, чем криптографические хэши. По состоянию на 2021 год SipHash (2012) Жана-Филиппа Омассона и Дэниела Дж. Бернстайна является наиболее широко используемой хэш-функцией в этом классе. [18] (Неключевые «простые» хэши остаются безопасными для использования, пока хэш-таблица приложения не контролируется извне.)

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

Смотрите также

Ссылки

  1. ^ ab 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 июля 2008 г.
  2. ^ MMJ Stevens (июнь 2007 г.). «О коллизиях для MD5» (PDF) . [...] мы можем найти коллизии для MD5 примерно за 2 24,1 сжатий для рекомендуемых IHV, что занимает около 6 секунд на 2,6 ГГц Pentium 4. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  3. ^ Магнус Даум; Стефан Лакс . "Hash Collisions (The Poisoned Message Attack)". Eurocrypt 2005 rump session . Архивировано из оригинала 2010-03-27.
  4. ^ abc Макс Гебхардт; Георг Иллиес; Вернер Шиндлер (4 января 2017 г.). «Заметка о практической ценности отдельных коллизий хэшей для специальных форматов файлов» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  5. ^ Марк Стивенс; Арьен Ленстра; Бенне де Вегер (2007-11-30). "Коллизии выбранных префиксов для MD5 и коллизии сертификатов X.509 для разных идентификаторов". Достижения в криптологии - EUROCRYPT 2007. Конспект лекций по информатике. Том 4515. стр. 1. Bibcode : 2007LNCS.4515....1S. doi : 10.1007/978-3-540-72540-4_1 . ISBN 978-3-540-72539-8.
  6. ^ Александр Сотиров и др. (2008-12-30). "Создание мошеннического сертификата CA". Архивировано из оригинала 2012-04-18 . Получено 2009-10-07 .
  7. ^ "Microsoft выпускает Security Advisory 2718704". Microsoft . 3 июня 2012 г. Архивировано из оригинала 7 июня 2012 г. Получено 4 июня 2012 г.
  8. ↑ Марк Стивенс (7 июня 2012 г.). «Криптоаналитик CWI обнаружил новый вариант криптографической атаки во вредоносном ПО Flame Spy». Centrum Wiskunde & Informatica . Получено 9 июня 2012 г.
  9. ^ Catalin Cimpanu (2019-05-13). «Атаки с коллизиями SHA-1 теперь действительно практичны и представляют собой надвигающуюся опасность». ZDNet .
  10. ^ Гаэтан Лёрент; Томас Пейрен (2019-05-06). «От коллизий до применения коллизий с выбранным префиксом к полному SHA-1» (PDF) .
  11. ^ Гаэтан Лёрент; Томас Пейрен (05.01.2020). «SHA-1 — это хаос — столкновение первого выбранного префикса в SHA-1 и его применение в сети доверия PGP» (PDF) .
  12. ^ "Hash Collision Q&A". Cryptography Research Inc. 2005-02-15. Архивировано из оригинала 2008-07-17. Из-за способа использования хэш-функций в конструкции HMAC, методы, использованные в этих недавних атаках, не применимы
  13. ^ Шай Халеви и Хьюго Кравчик, Рандомизированное хеширование и цифровые подписи. Архивировано 20 июня 2009 г. на Wayback Machine.
  14. ^ Александр Сотиров; Марк Стивенс; Джейкоб Аппельбаум; Арьен Ленстра; Дэвид Молнар; Даг Арне Освик; Бенне де Вегер (30 декабря 2008 г.). Сегодня MD5 считается вредным. Конгресс Хаос Коммуникации 2008.
  15. ^ Фалькенберг, Андреас; Майнка, Кристиан; Соморовски, Юрай; Швенк, Йорг (2013). «Новый подход к тестированию на проникновение DoS в веб-сервисы». 2013 IEEE 20th International Conference on Web Services . стр. 491–498. doi :10.1109/ICWS.2013.72. ISBN 978-0-7695-5025-1. S2CID  17805370.
  16. ^ ab "Об уязвимости хэш-флуда в Node.js... · V8". v8.dev .
  17. ^ Скотт А. Кросби и Дэн С. Уоллах. 2003. Отказ в обслуживании с помощью атак на алгоритмическую сложность. В трудах 12-й конференции по симпозиуму по безопасности USENIX - том 12 (SSYM'03), том 12. Ассоциация USENIX, Беркли, Калифорния, США, 3-3.
  18. ^ Жан-Филипп Омассон и Дэниел Дж. Бернстайн (18.09.2012). «SipHash: быстрый PRF с коротким входом» (PDF) .
  19. ^ Gerbet, Thomas; Kumar, Amrit; Lauradoux, Cédric (12 ноября 2014 г.). Сила злых выборов в фильтрах Блума (отчет). INRIA Гренобль.

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