Русская Википедия:Коллизионная атака

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

ОриентировочноШаблон:Уточнить существует два различных вида коллизионных атак:

  • коллизионная атакаШаблон:Уточнить: найти 2 разных сообщения m1 и m2 для хеш-функции <math>H</math> таких, что <math>H(m1)=H(m2)</math>.
  • коллизионная атака с заданным префиксом: для функции <math>H</math> заданы 2 различных префикса p1, p2 и ищутся 2 дополнения m1 и m2 такие, что H(p1 ∥ m1)=H(p2 ∥ m2) (где ∥ — это конкатенация).

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

Коллизионная атака находит два разных сообщения m1 и m2, таких, что <math>H(m1)=H(m2)</math>. В классическом случае атаки злоумышленник не имеет никакого контроля над содержанием сообщений, но они произвольно выбираются алгоритмом. Многие симметричные криптосистемы уязвимы для атак полного перебора (методом «грубой силы»), любая криптографическая хеш-функция по определению уязвима для атаки «дней рождения». Из-за парадокса дней рождения последний метод атаки может быть гораздо быстрее, чем метод перебора. Хеш из N бит может быть нарушен 2n/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 с заданным префиксом, требующая примерно 250 вычислений функции MD5. В заметке было представлено два сертификата X.509 для разных доменных имён, имеющих одинаковые хеш-функции. Это значит, что сертификатом одного доверенного домена может пользоваться другой неизвестный домен.[5]

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

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

Схема атаки

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

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

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

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

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

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

Примечания

Шаблон:Примечания

Ссылки

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD Шаблон:Wayback, Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revised 17 Aug 2004. Retrieved July 27, 2008.
  2. ↑ Шаблон:Статья
  3. ↑ Шаблон:Cite web
  4. ↑ 4,0 4,1 4,2 Шаблон:Статья
  5. ↑ Шаблон:Статья
  6. ↑ Шаблон:Cite web
  7. ↑ Шаблон:Cite web
  8. ↑ Шаблон:Cite web
  9. ↑ Шаблон:Cite web
  10. ↑ Shai Halevi and Hugo Krawczyk, Randomized Hashing and Digital Signatures Шаблон:Wayback
  11. ↑ Шаблон:Cite conference
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Коллизионная_атака&oldid=10147638