Атака SHAttered

Атака SHAttered — это первая в истории публично продемонстрированная практическая коллизионная атака на криптографическую хеш-функцию SHA-1, в результате которой были найдены два различных набора данных (PDF-файла), имеющих одинаковый 160-битный дайджест (хеш-сумму). Атака была осуществлена исследовательской группой компании Google совместно с сотрудниками голландского Центра математики и информатики (CWI) и впервые представлена публике 23 февраля 2017 года.

История

Предпосылки

Криптографическая хеш-функция SHA-1 (Secure Hash Algorithm 1) была разработана Агентством национальной безопасности США (NSA) в 1995 году и на протяжении десятилетий являлась одним из самых распространённых алгоритмов для обеспечения целостности данных, цифровых подписей и аутентификации. Однако уже к началу 2000-х годов теоретическая стойкость SHA-1 начала вызывать сомнения. В 2005 году группа криптографов под руководством Ван Сяоюня (Wang Xiaoyun) опубликовала теоретическую атаку, снижающую сложность нахождения коллизии с 2^80 (полный перебор) до 2^69 операций. В последующие годы сложность атаки последовательно снижалась: в 2015 году Марк Стивенс (Marc Stevens) из CWI предложил метод, требующий 2^57,5 операций, а в 2016 году — 2^55,1.

Демонстрация атаки

Атака SHAttered стала результатом многолетней работы, объединившей усилия Google (команда безопасности и команда Chrome) и CWI. Для её проведения потребовались значительные вычислительные ресурсы: 9,223×10^18 операций SHA-1, что эквивалентно примерно 110 годам работы одного графического процессора (GPU) или 6500 годам работы одного центрального процессора (CPU). В реальности вычисления были распределены между несколькими кластерами Google и заняли несколько месяцев.

23 февраля 2017 года исследователи опубликовали два различных PDF-файла (один — с белым фоном, другой — с цветным), которые имели одинаковую SHA-1-хеш-сумму. Файлы были созданы таким образом, что их содержимое различалось визуально, но алгоритм хеширования выдавал идентичный результат. Это стало первым публичным доказательством возможности практической коллизии SHA-1.

Технические детали

Принцип атаки

Атака SHAttered относится к классу атак на основе дифференциального криптоанализа. Она использует метод «выбора префикса» (chosen-prefix collision), при котором злоумышленник может заранее задать начальные части двух сообщений, а затем вычислить дополнительные блоки данных, приводящие к коллизии. В случае SHAttered исследователи использовали 64-байтовый блок данных, который добавлялся к каждому из двух PDF-файлов, чтобы их хеши совпали.

Сложность и ресурсы

Для проведения атаки потребовалось:

• 9,223×10^18 операций хеширования SHA-1.
• 6,5×10^15 байт (6,5 петабайт) промежуточных данных, сохранённых на дисках.
• Распределённые вычисления на нескольких кластерах Google (включая GPU-ускорители).
• Специализированное программное обеспечение, разработанное для оптимизации поиска коллизий.

Результат

Исследователи создали два PDF-файла, которые:

• Имеют одинаковую SHA-1-хеш-сумму: 38762cf7f55934b34d179ae6a4c80cadccbb7f0a.
• Различаются визуально: один файл содержит белый фон, другой — цветной.
• Имеют одинаковый размер (около 1,5 МБ).
• Содержат идентичные метаданные и структуру PDF.

Последствия

Криптографическая безопасность

Атака SHAttered продемонстрировала, что SHA-1 больше не может считаться криптостойкой хеш-функцией. Хотя стоимость атаки (около 110 000 долларов США по оценкам Google на момент публикации) была относительно высока для индивидуального злоумышленника, она оказалась доступной для крупных организаций и государственных структур. Это означало, что SHA-1 стал уязвим для практических атак, в том числе для подделки цифровых подписей, сертификатов и целостности данных.

Реакция индустрии

После публикации атаки SHAttered большинство крупных технологических компаний, включая Google, Microsoft, Mozilla и Apple, ускорили процесс отказа от SHA-1. В частности:

• Google Chrome начал блокировать сайты, использующие SHA-1-сертификаты, с 2017 года.
• Microsoft выпустила обновления для Windows, отключающие поддержку SHA-1 в системных компонентах.
• Mozilla Firefox прекратил доверять SHA-1-сертификатам с 2017 года.
• Браузеры и операционные системы начали требовать использования SHA-2 или более новых алгоритмов (например, SHA-3).

Научное значение

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

Критика и ограничения

Несмотря на значимость, атака SHAttered имела ряд ограничений:

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

Интересные факты

• Название «SHAttered» является игрой слов: «SHA» (сокращение от SHA-1) и «shattered» (англ. «разбитый, разрушенный»), что символизирует крах доверия к алгоритму.
• Один из созданных PDF-файлов был опубликован с открытым исходным кодом для проверки коллизии.
• Атака SHAttered была удостоена премии Levchin Prize за вклад в криптографию в 2018 году.

Источники

• Stevens, M., Bursztein, E., Karpman, P., Albertini, A., & Markov, Y. (2017). The first collision for full SHA-1. Proceedings of the 37th Annual International Cryptology Conference (CRYPTO 2017).
• Google Security Blog (2017). Announcing the first SHA-1 collision.
• CWI (2017). SHAttered: The first practical collision for SHA-1.
• Wang, X., Yin, Y. L., & Yu, H. (2005). Finding collisions in the full SHA-1. Proceedings of the 25th Annual International Cryptology Conference (CRYPTO 2005).