Google продемонстрировал первую успешную атаку на алгоритм хеширования SHA-1


Через десять лет после начала использования алгоритма хэширования SHA-1 компания Google объявила о первом практическом методе генерации коллизии для SHA-1. Результаты были получены после двух лет исследований, проведённых корпорацией совместно с институтом CWI в Амстердаме. В качестве доказательства возможности совершения атаки, компания Google предоставила два PDF-файла, которые имеют одинаковые хеши SHA-1, но разное содержание.

Количество вычислений, необходимых для проведения разработанной в Google атаки, которая получила название SHAttered, ошеломляет: девять квинтильонов (9,223,372,036,854,775,808) операций подсчёта SHA-1 в общей сложности, которые потребовали бы 6500 лет вычислений на одном CPU или 110 лет вычислений на одном GPU. При этом на системе со 110 GPU усовершенствованная атака занимает примерно год. Для сравнения, применение метода полного перебора (brute force) в 100 тысяч раз медленнее и для нахождения коллизии за год потребуется 12 миллионов GPU. Для проведения атак не требуется каждый раз производить вычисления, например, для атаки на PDF можно использовать уже вычисленный типовой набор данных для вызова коллизии.


Google считает, что необходимо переходить на новые алгоритмы хеширования, такие как SHA-256 и SHA-3. Однако стоит отметить, что в настоящее время нет способов найти коллизии для хэшей MD5 и SHA-1 одновременно, что означает, что чтобы быть в безопасности все еще можно использовать старые доказанные хэш-функции, которые к тому же ускоряются аппаратно.

В рамках соглашения о раннем неразглашении уязвимостей, компания Google на 90 дней задержит публикацию практической реализации метода подбора коллизий (теоретическое описание уже доступно). После публикации кода для проведения атаки, им сможет воспользоваться любой желающий для создания одинаковых хэшей SHA-1 для разных PDF-файлов. Тем не менее для реализации защиты в настоящее время уже опубликован код библиотеки и утилиты, позволяющих выдавать предупреждения для файлов, вызывающих коллизии в SHA-1.

Дополнение 1: По мнению Линуса Торвальдса, реальную степень угрозы для Git, в котором хэш SHA-1 используется для контроля целостности цепочки коммитов, можно будет оценить только после изучения кода для проведения атаки. Предварительно, Линус считает атаку на Git маловероятной, так как хэширование охватывает не только данные, но и заголовок, в котором указывается тип и размер. Таким образом атака существенно усложняется, так как потребуется не просто подобрать текст, вызывающий коллизию, но в этом тексте должен быть корректный заголовок, в котором указан правильный размер. В случае PDF атака упрощается, так как заголовок фиксирован и в файл можно вставить большие куски произвольных данных, которые не будут отображаться.

Дополнение 2: Компания Mozilla объявила о расширении действия выборочного прекращения поддержки SHA-1 на всех пользователей Firefox 51. В Firefox 52 SHA-1 будет отключен по умолчанию. В Chrome поддержка SHA-1 уже прекращена ранее в январском выпуске (Chrome 56).

Дополнение 3: Энтузиасты не дожидаясь открытия кода эксплоита создали собственную реализацию метода, позволяющую создать разные PDF, выдающие один хэш SHA-1. В случае предложенной атаки на PDF, для создания двух PDF-файлов с одинаковыми хэшами SHA-1 больших вычислительных ресурсов не требуется, так как используется уже готовый набор данных для вызова коллизии.