Хэш-коллизии и эксплуатация

Авторы: Ange Albertini и Marc Stevens.

FAQ (TL;DR)

В: Можно ли заставить файл получить произвольный MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3 или такой же хэш, как у другого файла?
О: Нет.

В: Можно ли создать 2 разных файла с одинаковым хэшем?
О: С MD5 — за несколько секунд на обычном компьютере. С SHA1 — возможно, но непрактично для конечных пользователей (Сложность: 2^61.2 Цена: $11k).

В: Можно ли заставить 2 разных файла получить одинаковый хэш, добавив данные?
О: С MD5 — за несколько часов на обычном компьютере. С SHA1 — возможно, но непрактично для конечных пользователей (Сложность: 2^63.4 Цена: $45K)

В: Будут ли 2 файла оставаться корректными?
О: В целом да, так как большинство форматов файлов допускают добавленные данные. С другой стороны, подписи файлов, скорее всего, будут нарушены.

В: Можно ли создать 2 разных файла с произвольным содержимым и одинаковым хэшем?
О: Да, это может быть мгновенным, если опираться на особые структуры файлов:

1. специальный заголовок формата (или пара заголовков) с уловками, действующий как переключатель между 2 содержимыми (некоторые форматы не допускают таких уловок).
   
2. предвычисленные коллизии, основанные на конкретном(ых) заголовке(ах).
   
3. два содержимых определённых форматов, оба присутствующих после коллизии (добавленных после вычисления).

В: Для каких форматов можно мгновенно получить пару файлов с коллизией MD5?
О: JPG, PNG, GIF, GZIP, Portable Executable, MP4, JPEG2000, PDF, DOCX/PPTX/XSLX, EPUB, 3MF, XPS. Просто запустите соответствующий скрипт.

В: А как насчёт SHA1?
О: Для SHA1 вычислена и реализована JPG в PDF.

В: А форматы, уже поддерживаемые для MD5 (JPG, PNG...), но для SHA1?
О: Скорее всего, они поддерживаются и для SHA1, но их коллизии ещё не вычислены.

В: Вычисления для похожих (но разных) содержимых выполняются быстрее?
О: Нет. Любое мельчайшее отличие требует полного вычисления.

В: Какие форматы не имеют такого обходного пути?
О: ELF, Mach-O, Java Class, TAR, ZIP (среди прочих...)

В: Возможны ли классические коллизии (за несколько часов) с этими форматами?
О: Да, если допускается любое количество добавляемых данных (то есть, скорее всего, не ZIP или Class).

В: Предоставляете ли вы примеры коллизий?
О: Да.

Содержание

• Введение
• Статус
• Атаки
  • Одинаковый префикс
    • FastColl (MD5)
    • UniColl (MD5)
    • Shattered (SHA1)
  • Коллизии с выбранным префиксом
    • HashClash (MD5)
    • Shambles (SHA1)
  • Сводка атак
• Эксплуатация
  • Стандартная стратегия
    • JPG
      • нестандартные сканы
    • PNG
      • несовместимость
    • GIF
    • GZIP
    • LZ4 / Zstandard
    • Portable Executable
    • MP4 и другие
      • JPEG2000
    • PDF
      • JPG в PDF
    • ZIP
      • Форматы на основе ZIP
    • Прочие
  • Необычные стратегии
    • MultiColls: цепочка множественных коллизий
      • Hashquines
    • Валидность
    • PolyColls: коллизии разных типов файлов
      • PE - JPG
      • PDF - PE
      • PDF - PNG
    • PileUps (мультиколлизия)
      • PE - PNG - MP4 - PDF
  • Варианты использования
    • Столкни их всех!
    • Компрометирующие файлы
  • Неудачи
    • ELF
    • Mach-O
    • Java Class
    • TAR
  • Сводка по эксплуатации
  • Тестовые файлы
• Обнаружение
  • Безопасные хэши
• Ссылки
• Благодарности
• Заключение

Введение

Цель — всесторонне исследовать существующие атаки — и заодно показать, насколько слаб MD5 (мгновенные коллизии для любых JPG, PNG, PDF, MP4, PE...) — а также детально изучить распространённые форматы файлов, чтобы определить, как их можно эксплуатировать с помощью текущих или будущих атак.

Действительно, один и тот же приём с форматом файла можно использовать для нескольких хэшей (те же приёмы с JPG использовались для MD5, malicious SHA-1 и SHA1), если коллизии следуют одним и тем же байтовым шаблонам.

Этот документ посвящён не новым атакам (самая недавняя была задокументирована в 2012 году), а новым формам эксплуатации существующих атак.

Статус

Текущий статус известных атак:

• заставить файл получить хэш другого файла или заданный хэш: невозможно

  • это по-прежнему непрактично даже с MD2 или MD4.
  • работает для более простых хэшей(*)

• получить два разных файла с одинаковым MD5: мгновенно

  • примеры: 1 ⟷ 2

• заставить два произвольных файла получить одинаковый MD5: несколько часов (72 ядро-часа)

  • примеры: 1 ⟷ 2

• заставить два произвольных файла определённых форматов (PNG, JPG, PE...) получить одинаковый MD5: мгновенно

  • читайте ниже

• получить два разных файла с одинаковым SHA1: 6500 ядро-лет

  • получить два разных PDF с одинаковым SHA-1, чтобы показать другую картину: мгновенно (префиксы уже вычислены)

(*) пример с crypt — спасибо Sven!```

import crypt crypt.crypt("5dUD&66", "br") 'brokenOz4KxMc' crypt.crypt("O!>',%$", "br") 'brokenOz4KxMc'

# Атаки

MD5 и SHA1 работают с блоками по 64 байта.