Столкновение атака

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

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

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

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

Атака коллизией выбранного префикса: Учитывая два разных префикса p ₁ и p ₂ , найдите два суффикса s ₁ и s ₂ такие, что хэш ( p ₁ ∥ s ₁ ) = хеш ( p ₂ ∥ s ₂ ), где ∥ обозначает операцию конкатенации .

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

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

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

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

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

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

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

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

Математически говоря, при наличии двух разных префиксов p ₁ , p ₂ атака находит два суффикса s ₁ и s ₂ такие, что хеш ( p ₁ ∥ s ₁ ) = хэш ( p ₂ ∥ s ₂ ) (где ∥ — операция конкатенации ) .

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

Реальная коллизионная атака была опубликована в декабре 2008 года, когда группа исследователей безопасности опубликовала поддельный сертификат подписи X.509 , который можно было использовать для выдачи себя за центр сертификации , воспользовавшись атакой коллизии префиксов против хеш-функции MD5. Это означало, что злоумышленник мог выдать себя за любого веб-сайта, защищенного SSL , как посредника , тем самым нарушая проверку сертификата, встроенную в каждый веб-браузер для защиты электронной коммерции . Мошеннический сертификат не может быть отозван реальными властями, а также может иметь произвольный поддельный срок действия. Хотя в 2004 году было известно, что MD5 очень слаб, ^{[ 1 ]} в декабре 2008 года центры сертификации все еще были готовы подписывать проверенные MD5 сертификаты. ^{[ 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 ]}

Обычный сценарий атаки выглядит следующим образом:

Мэллори создает два разных документа A и B, которые имеют одинаковое значение хеш-функции, т. е. происходит коллизия. Мэллори пытается обманом заставить Боба принять документ Б, якобы от Алисы.
Мэллори отправляет документ A Алисе , которая соглашается с тем, что написано в документе, подписывает его хэш и отправляет подпись Мэллори.
Мэллори прикрепляет подпись документа А к документу Б.
Затем Мэллори отправляет подпись и документ B Бобу , утверждая, что Алиса подписала B. Поскольку цифровая подпись соответствует хешу документа B, программное обеспечение Боба не может обнаружить подмену. ^{[ нужна ссылка ]}

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

Хеш-флуд

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

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

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

См. также

Дружелюбие к головоломкам

Ссылки

^ Перейти обратно: ^а ^б Сяоюнь Ван, Дэнго Фэн, Сюэцзя Лай, Хунбо Ю: Коллизии хеш-функций MD4, MD5, HAVAL-128 и RIPEMD , Архивный отчет Cryptology ePrint 2004/199, 16 августа 2004 г., исправлено 17 августа 2004 г. Проверено 27 июля 2008 г.
^ MMJ Стивенс (июнь 2007 г.). «О столкновениях для MD5» (PDF) . [...] мы можем найти коллизии для MD5 примерно за 2 ^24.1 сжатия для рекомендуемых IHV, которые занимают ок. 6 секунд на процессоре Pentium 4 с частотой 2,6 ГГц. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Магнус Даум; Стефан Лакс . «Хеш-коллизии (атака отравленных сообщений)» . Eurocrypt Итоговая сессия 2005 . Архивировано из оригинала 27 марта 2010 г.
^ Перейти обратно: ^а ^б ^с Макс Гебхардт; Георг Иллиес; Вернер Шиндлер (4 января 2017 г.). «Заметка о практической ценности одиночных коллизий хэшей для специальных форматов файлов» (PDF) . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Марк Стивенс; Арьен Ленстра; Бенне де Вегер (30 ноября 2007 г.). «Конфликты выбранных префиксов для MD5 и конфликтующие сертификаты X.509 для разных удостоверений» . Достижения в криптологии – EUROCRYPT 2007 . Конспекты лекций по информатике. Том. 4515. с. 1. Бибкод : 2007LNCS.4515....1S . дои : 10.1007/978-3-540-72540-4_1 . ISBN 978-3-540-72539-8 .
^ Александр Сотиров; и др. (30 декабря 2008 г.). «Создание мошеннического сертификата ЦС» . Архивировано из оригинала 18 апреля 2012 г. Проверено 7 октября 2009 г.
^ «Microsoft выпускает рекомендации по безопасности 2718704» . Майкрософт . 3 июня 2012 года. Архивировано из оригинала 7 июня 2012 года . Проверено 4 июня 2012 г.
^ Марк Стивенс (7 июня 2012 г.). «Криптоаналитик CWI обнаруживает новый вариант криптографической атаки во вредоносном ПО Flame Spy» . Центр Вискунде и информатики . Проверено 9 июня 2012 года .
^ Каталин Чимпану (13 мая 2019 г.). «Атаки столкновением SHA-1 теперь действительно практичны и представляют собой надвигающуюся опасность» . ЗДНет .
^ Гаэтан Леран; Томас Пейрин (06 мая 2019 г.). «От коллизий к приложениям коллизий выбранного префикса к полному SHA-1» (PDF) .
^ Гаэтан Леран; Томас Пейрин (05 января 2020 г.). «SHA-1 - это беспорядок - первый конфликт выбранного префикса в SHA-1 и приложении к сети доверия PGP» (PDF) .
^ «Вопросы и ответы по хэш-конфликтам» . Cryptography Research Inc., 15 февраля 2005 г. Архивировано из оригинала 17 июля 2008 г. Из-за того, как при построении HMAC используются хэш-функции, методы, использованные в этих недавних атаках, не применимы.
^ Шай Халеви и Хьюго Кравчик, Рандомизированное хеширование и цифровые подписи. Архивировано 20 июня 2009 г. в Wayback Machine.
^ Александр Сотиров; Марк Стивенс; Джейкоб Аппелбаум; Арьен Ленстра; Дэвид Молнар; Дэй Арне Освик; Бенне де Вегер (30 декабря 2008 г.). MD5 сегодня считается вредным . Конгресс Хаос Коммуникации 2008.
^ Фалькенберг, Андреас; Майнка, Кристиан; Соморовский, Юрай; Швенк, Йорг (2013). «Новый подход к тестированию на проникновение DoS в веб-сервисах». 20-я Международная конференция IEEE по веб-сервисам , 2013 г. стр. 491–498. дои : 10.1109/ICWS.2013.72 . ISBN 978-0-7695-5025-1 . S2CID 17805370 .
^ Перейти обратно: ^а ^б «Об уязвимости переполнения хеша в Node.js... · V8» . v8.dev .
^ Скотт А. Кросби и Дэн С. Уоллах. 2003. Отказ в обслуживании посредством атак с алгоритмической сложностью. В материалах 12-й конференции симпозиума по безопасности USENIX - том 12 (SSYM'03), Vol. 12. Ассоциация USENIX, Беркли, Калифорния, США, 3–3.
^ Жан-Филипп Омассон и Дэниел Дж. Бернштейн (18 сентября 2012 г.). «SipHash: быстрый PRF с коротким вводом» (PDF) .
^ Гербет, Томас; Кумар, Амрит; Лораду, Седрик (12 ноября 2014 г.). Сила злого выбора в фильтрах Блума (отчет). ИНРИА Гренобль.

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

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

[md5-2004-1] Перейти обратно: ^а ^б Сяоюнь Ван, Дэнго Фэн, Сюэцзя Лай, Хунбо Ю: Коллизии хеш-функций MD4, MD5, HAVAL-128 и RIPEMD , Архивный отчет Cryptology ePrint 2004/199, 16 августа 2004 г., исправлено 17 августа 2004 г. Проверено 27 июля 2008 г.

[2] MMJ Стивенс (июнь 2007 г.). «О столкновениях для MD5» (PDF) . [...] мы можем найти коллизии для MD5 примерно за 2 ^24.1 сжатия для рекомендуемых IHV, которые занимают ок. 6 секунд на процессоре Pentium 4 с частотой 2,6 ГГц. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[3] Магнус Даум; Стефан Лакс . «Хеш-коллизии (атака отравленных сообщений)» . Eurocrypt Итоговая сессия 2005 . Архивировано из оригинала 27 марта 2010 г.

[special-file-formats-4] Перейти обратно: ^а ^б ^с Макс Гебхардт; Георг Иллиес; Вернер Шиндлер (4 января 2017 г.). «Заметка о практической ценности одиночных коллизий хэшей для специальных форматов файлов» (PDF) . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[md5-chosen-2007-5] Марк Стивенс; Арьен Ленстра; Бенне де Вегер (30 ноября 2007 г.). «Конфликты выбранных префиксов для MD5 и конфликтующие сертификаты X.509 для разных удостоверений» . Достижения в криптологии – EUROCRYPT 2007 . Конспекты лекций по информатике. Том. 4515. с. 1. Бибкод : 2007LNCS.4515....1S . дои : 10.1007/978-3-540-72540-4_1 . ISBN 978-3-540-72539-8 .

[6] Александр Сотиров; и др. (30 декабря 2008 г.). «Создание мошеннического сертификата ЦС» . Архивировано из оригинала 18 апреля 2012 г. Проверено 7 октября 2009 г.

[7] «Microsoft выпускает рекомендации по безопасности 2718704» . Майкрософт . 3 июня 2012 года. Архивировано из оригинала 7 июня 2012 года . Проверено 4 июня 2012 г.

[8] Марк Стивенс (7 июня 2012 г.). «Криптоаналитик CWI обнаруживает новый вариант криптографической атаки во вредоносном ПО Flame Spy» . Центр Вискунде и информатики . Проверено 9 июня 2012 года .

[SHA-1_collision_attacks_are_now_actually_practical_and_a_looming_danger_2019-9] Каталин Чимпану (13 мая 2019 г.). «Атаки столкновением SHA-1 теперь действительно практичны и представляют собой надвигающуюся опасность» . ЗДНет .

[Collisions_of_Chosen-Prefix_Collisions_SHA-1_2019-10] Гаэтан Леран; Томас Пейрин (06 мая 2019 г.). «От коллизий к приложениям коллизий выбранного префикса к полному SHA-1» (PDF) .

[SHA-1_is_a_Shambles_-_First_Chosen-Prefix_Collision_on_SHA-1_and_Application_to_the_PGP_Web_of_Trust-11] Гаэтан Леран; Томас Пейрин (05 января 2020 г.). «SHA-1 - это беспорядок - первый конфликт выбранного префикса в SHA-1 и приложении к сети доверия PGP» (PDF) .

[collision-qna-12] «Вопросы и ответы по хэш-конфликтам» . Cryptography Research Inc., 15 февраля 2005 г. Архивировано из оригинала 17 июля 2008 г. Из-за того, как при построении HMAC используются хэш-функции, методы, использованные в этих недавних атаках, не применимы.

[13] Шай Халеви и Хьюго Кравчик, Рандомизированное хеширование и цифровые подписи. Архивировано 20 июня 2009 г. в Wayback Machine.

[14] Александр Сотиров; Марк Стивенс; Джейкоб Аппелбаум; Арьен Ленстра; Дэвид Молнар; Дэй Арне Освик; Бенне де Вегер (30 декабря 2008 г.). MD5 сегодня считается вредным . Конгресс Хаос Коммуникации 2008.

[15] Фалькенберг, Андреас; Майнка, Кристиан; Соморовский, Юрай; Швенк, Йорг (2013). «Новый подход к тестированию на проникновение DoS в веб-сервисах». 20-я Международная конференция IEEE по веб-сервисам , 2013 г. стр. 491–498. дои : 10.1109/ICWS.2013.72 . ISBN 978-0-7695-5025-1 . S2CID 17805370 .

[v8-16] Перейти обратно: ^а ^б «Об уязвимости переполнения хеша в Node.js... · V8» . v8.dev .

[17] Скотт А. Кросби и Дэн С. Уоллах. 2003. Отказ в обслуживании посредством атак с алгоритмической сложностью. В материалах 12-й конференции симпозиума по безопасности USENIX - том 12 (SSYM'03), Vol. 12. Ассоциация USENIX, Беркли, Калифорния, США, 3–3.

[SipHash-18] Жан-Филипп Омассон и Дэниел Дж. Бернштейн (18 сентября 2012 г.). «SipHash: быстрый PRF с коротким вводом» (PDF) .

[19] Гербет, Томас; Кумар, Амрит; Лораду, Седрик (12 ноября 2014 г.). Сила злого выбора в фильтрах Блума (отчет). ИНРИА Гренобль.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]