SHAttered

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

История открытия

Предпосылки

Криптоанализ SHA-1 велся с начала 2000-х годов. В 2005 году группа китайских криптографов (Ван Сяоюнь, Ицзюнь Инь и Хунбо Юй) опубликовала теоретический метод нахождения коллизий с вычислительной сложностью 2^69 операций, что значительно ниже теоретического предела в 2^80 для полного перебора. В последующие годы сложность атаки последовательно снижалась: в 2015 году французский исследователь Марк Стивенс (один из будущих авторов SHAttered) предложил метод с оценкой 2^57,5 операций. Однако все эти работы оставались теоретическими — для практической реализации требовались огромные вычислительные ресурсы, недоступные большинству исследователей.

Процесс атаки

Проект SHAttered был реализован на базе инфраструктуры Google Cloud Platform. Атака использовала метод, основанный на дифференциальном криптоанализе, и состояла из двух этапов:

1. Поиск столкновений в сжатии — вычисление двух блоков данных, которые при обработке определенного промежуточного состояния хеш-функции дают одинаковый результат. Для этого потребовалось около 6500 лет процессорного времени (в пересчете на одно ядро), но благодаря параллелизации на 110 графических процессорах (GPU) реальное время составило около 110 дней.
2. Формирование коллизионных PDF-файлов — на основе найденных блоков были созданы два PDF-документа одинакового размера (около 300 КБ), но с разным содержимым. При этом оба файла имели один и тот же SHA-1-хеш: 38762cf7f55934b34d179ae6a4c80cadccbb7f0a.

Публикация

Результаты были опубликованы на специально созданном сайте shattered.io, где также были выложены оба коллизионных файла для проверки. Исследователи заявили, что стоимость атаки составила около 110 000 долларов США (включая аренду вычислительных мощностей Google Cloud), что сделало её доступной для крупных организаций и государственных структур.

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

Тип коллизии

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

Структура атаки

Атака базируется на технике разностных путей (differential paths) для SHA-1. Исследователи использовали:

• Метод поиска локальных коллизий — нахождение пар блоков, которые дают одинаковое изменение состояния хеш-функции.
• Оптимизацию с помощью GPU — параллельная обработка миллионов вариантов для поиска подходящих разностных путей.
• Специализированное программное обеспечение — код был написан на C++ с использованием библиотек OpenCL и CUDA для работы с графическими процессорами.

Сравнение с теоретическими оценками

Теоретическая сложность атаки, реализованной в проекте, оценивается в 2^63,1 операций хеширования, что примерно в 100 000 раз быстрее полного перебора (2^80). Фактическая производительность составила около 9,4×10^13 хешей в секунду на одном GPU, что позволило выполнить атаку за 110 дней.

Последствия и реакция

Криптографическое сообщество

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

• NIST (Национальный институт стандартов и технологий США) официально рекомендовал прекратить использование SHA-1 после 2020 года.
• Браузеры (Google Chrome, Mozilla Firefox, Microsoft Edge) начали отображать предупреждения о небезопасности для сайтов, использующих SHA-1 в сертификатах SSL/TLS.
• Системы контроля версий (Git, Mercurial) — разработчики Git подтвердили, что использование SHA-1 в Git не является критическим, так как атака требует контроля над содержимым обоих файлов, что в Git затруднено.

Практические угрозы

SHAttered продемонстрировал несколько сценариев атаки:

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

Ограничения атаки

Исследователи отметили, что атака не является универсальной:

• Она требует значительных вычислительных ресурсов (около 110 000 долларов на момент публикации).
• Для коллизии второго рода (когда одно сообщение фиксировано) сложность остается значительно выше — около 2^80 операций.
• Атака не позволяет восстановить исходное сообщение по хешу (обратная задача), что делает её бесполезной для взлома паролей.

Переход на SHA-2 и SHA-3

SHA-2

Семейство хеш-функций SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) было разработано Агентством национальной безопасности США (NSA) в 2001 году. На момент публикации SHAttered не было известно ни одной практической коллизии для SHA-2, хотя теоретические атаки на уменьшенные версии существовали. SHA-2 использует большую длину хеша (до 512 бит) и более сложную структуру, что делает его устойчивым к атакам, подобным SHAttered.

SHA-3

Стандарт SHA-3, принятый NIST в 2015 году, основан на алгоритме Keccak и имеет принципиально иную конструкцию (sponge function), отличную от семейства SHA-1/SHA-2. На момент 2024 года не было опубликовано ни одной практической коллизии для SHA-3.

Ситуация в России

В Российской Федерации переход на новые стандарты хеширования регулируется ГОСТ Р 34.11-2012 («Стрибог»), который является обязательным для использования в государственных информационных системах. SHA-1 не входит в перечень разрешенных алгоритмов для защиты государственной тайны, однако может использоваться в коммерческих и частных системах. После публикации SHAttered Роскомнадзор и ФСТЭК России рекомендовали организациям отказаться от использования SHA-1 в системах, требующих криптографической защиты.

Критика и обсуждения

Достоверность атаки

Некоторые криптографы выразили сомнения в практической значимости атаки, указывая на то, что:

• Коллизия была получена для специально подготовленных PDF-файлов, а не для произвольных данных.
• Атака требует значительных вычислительных ресурсов, что делает её неприменимой для массовых атак.
• Для большинства реальных сценариев (например, подделка цифровых подписей) требуется коллизия второго рода, которая остается недостижимой.

Влияние на индустрию

Несмотря на критику, SHAttered оказал значительное влияние:

• Крупные технологические компании (Google, Microsoft, Apple) объявили о прекращении поддержки SHA-1 в своих продуктах.
• В 2020 году Mozilla Firefox перестал принимать сертификаты SSL/TLS, использующие SHA-1.
• Банковские и финансовые системы, использующие SHA-1 для подписи транзакций, были вынуждены перейти на SHA-2.

Источники

1. Stevens, M., Bursztein, E., Karpman, P., Albertini, A., Markov, Y. (2017). «The first collision for full SHA-1». — CRYPTO 2017.
2. Wang, X., Yin, Y. L., Yu, H. (2005). «Finding collisions in the full SHA-1». — CRYPTO 2005.
3. NIST Special Publication 800-131A Rev. 2 (2019). «Transitioning the Use of Cryptographic Algorithms and Key Lengths».
4. ГОСТ Р 34.11-2012. «Информационная технология. Криптографическая защита информации. Функция хеширования».
5. Официальный сайт проекта shattered.io.