Коллизионная атака

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

Ориентировочно^{[уточнить]} существует два различных вида коллизионных атак:

коллизионная атака^{[уточнить]}: найти 2 разных сообщения m1 и m2 для хеш-функции $H$ таких, что $H(m1)=H(m2)$ .
коллизионная атака с заданным префиксом: для функции $H$ заданы 2 различных префикса p1, p2 и ищутся 2 дополнения m1 и m2 такие, что H(p1 ∥ m1)=H(p2 ∥ m2) (где ∥ — это конкатенация).

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

Коллизионная атака находит два разных сообщения m1 и m2, таких, что $H(m1)=H(m2)$ . В классическом случае атаки злоумышленник не имеет никакого контроля над содержанием сообщений, но они произвольно выбираются алгоритмом. Многие симметричные криптосистемы уязвимы для атак полного перебора (методом «грубой силы»), любая криптографическая хеш-функция по определению уязвима для атаки «дней рождения». Из-за парадокса дней рождения последний метод атаки может быть гораздо быстрее, чем метод перебора. Хеш из N бит может быть нарушен 2^n/2 раз (вычислением хеш-функции). Наиболее результативные атаки возможны при использовании криптоанализа к конкретной хеш-функции. Когда коллизионная атака оказывается быстрее, чем атака «дней рождения», хеш-функции часто осуждаются как «сломанные». Создание хеш-функции SHA-3 (конкурс) было во многом вызвано необходимостью замены старых функций MD5^[1] и SHA-1. Коллизионные атаки против алгоритма MD5 улучшились настолько, что на обычном компьютере они займут лишь несколько секунд времени.^[2] Коллизии хеш-функций, созданные данным способом, как правило, постоянной длины и в значительной степени неструктурированны, поэтому не могут быть применены напрямую к атаке распространённых форматов документов или протоколов. Тем не менее, обходные пути возможны при злоупотреблении динамическими конструкциями присутствующими во многих форматах. Таким образом, будут созданы два документа, идентичные друг другу настолько, чтобы у них было одинаковое значение хеш-функции. Если один документ будет подписан доверенным лицом, его подпись может быть скопирована в другой файл. Такой вредоносный документ будет содержать два разных сообщения в одном и том же документе, но при этом сможет отобразить любое из них через небольшие изменения в файле:

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

Коллизионная атака с заданным префиксом

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

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

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

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

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

Схема атаки

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

Электронные подписи

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

Обычно атака проходит следующим образом:

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

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

Примечания

↑ ¹ ² Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD Архивная копия от 3 сентября 2011 на Wayback Machine, Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revised 17 Aug 2004. Retrieved July 27, 2008.
↑ M.M.J. Stevens. On Collisions for MD5 (неопр.). — 2007. — June. Архивировано 17 мая 2017 года.
↑ Magnus Daum, Stefan Lucks. Hash Collisions (The Poisoned Message Attack) (неопр.). Eurocrypt 2005 rump session. Архивировано 27 марта 2010 года.
↑ ¹ ² ³ Max Gebhardt, Georg Illies, Werner Schindler. A Note on the Practical Value of Single Hash Collisions for Special File Formats (англ.) : journal. Архивировано 5 июня 2011 года.
↑ Marc Stevens, Arjen Lenstra, Benne de Weger. Chosen-preﬁx Collisions for MD5 and Colliding X.509 Certiﬁcates for Diﬀerent Identities (англ.) : journal. — 2007. — 30 November. Архивировано 11 мая 2012 года.
↑ Alexander Sotirov. Creating a rogue CA certificate (неопр.) (30 декабря 2008). Дата обращения: 15 декабря 2015. Архивировано из оригинала 18 апреля 2012 года.
↑ Microsoft releases Security Advisory 2718704 (неопр.). Microsoft (3 июня 2012). Дата обращения: 4 июня 2012. Архивировано 7 июня 2012 года.
↑ Marc Stevens. CWI Cryptanalist Discovers New Cryptographic Attack Variant in Flame Spy Malware (неопр.). Centrum Wiskunde & Informatica (7 июня 2012). Дата обращения: 9 июня 2012. Архивировано 28 февраля 2017 года.
↑ Hash Collision Q&A (неопр.). Cryptography Research Inc (15 февраля 2005). — «Because of the way hash functions are used in the HMAC construction, the techniques used in these recent attacks do not apply». Архивировано 17 июля 2008 года.
↑ Shai Halevi and Hugo Krawczyk, Randomized Hashing and Digital Signatures Архивная копия от 20 июня 2009 на Wayback Machine
↑ Sotirov, Alexander; Stevens, Marc; Appelbaum, Jacob; Lenstra, Arjen; Molnar, David; Osvik, Dag Arne; Weger, Benne de (2008-12-30). MD5 considered harmful today. Chaos Communication Congress 2008. Архивировано из оригинала 25 марта 2017. Дата обращения: 15 декабря 2015.

Ссылки

«Meaningful Collisions», attack scenarios for exploiting cryptographic hash collisions
Fast MD5 and MD4 Collision Generators — Bishop Fox (formerly Stach & Liu).

[md5-2004-1] ¹ ² Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD Архивная копия от 3 сентября 2011 на Wayback Machine, Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revised 17 Aug 2004. Retrieved July 27, 2008.

[2] M.M.J. Stevens. On Collisions for MD5 (неопр.). — 2007. — June. Архивировано 17 мая 2017 года.

[3] Magnus Daum, Stefan Lucks. Hash Collisions (The Poisoned Message Attack) (неопр.). Eurocrypt 2005 rump session. Архивировано 27 марта 2010 года.

[special-file-formats-4] ¹ ² ³ Max Gebhardt, Georg Illies, Werner Schindler. A Note on the Practical Value of Single Hash Collisions for Special File Formats (англ.) : journal. Архивировано 5 июня 2011 года.

[md5-chosen-2007-5] Marc Stevens, Arjen Lenstra, Benne de Weger. Chosen-preﬁx Collisions for MD5 and Colliding X.509 Certiﬁcates for Diﬀerent Identities (англ.) : journal. — 2007. — 30 November. Архивировано 11 мая 2012 года.

[6] Alexander Sotirov. Creating a rogue CA certificate (неопр.) (30 декабря 2008). Дата обращения: 15 декабря 2015. Архивировано из оригинала 18 апреля 2012 года.

[7] Microsoft releases Security Advisory 2718704 (неопр.). Microsoft (3 июня 2012). Дата обращения: 4 июня 2012. Архивировано 7 июня 2012 года.

[8] Marc Stevens. CWI Cryptanalist Discovers New Cryptographic Attack Variant in Flame Spy Malware (неопр.). Centrum Wiskunde & Informatica (7 июня 2012). Дата обращения: 9 июня 2012. Архивировано 28 февраля 2017 года.

[collision-qna-9] Hash Collision Q&A (неопр.). Cryptography Research Inc (15 февраля 2005). — «Because of the way hash functions are used in the HMAC construction, the techniques used in these recent attacks do not apply». Архивировано 17 июля 2008 года.

[10] Shai Halevi and Hugo Krawczyk, Randomized Hashing and Digital Signatures Архивная копия от 20 июня 2009 на Wayback Machine

[11] Sotirov, Alexander; Stevens, Marc; Appelbaum, Jacob; Lenstra, Arjen; Molnar, David; Osvik, Dag Arne; Weger, Benne de (2008-12-30). MD5 considered harmful today. Chaos Communication Congress 2008. Архивировано из оригинала 25 марта 2017. Дата обращения: 15 декабря 2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]