Атака на SHA-1 коллизией хэша стала реальностью

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

Новую атаку на SHA-1 разработала и воплотила в жизнь группа исследователей: Эли Бурштейн (Elie Bursztein), Андже Альбертини (Ange Albertini) и Ярик Марков из Google, а также специалисты по криптографии Марк Стивенс (Marc Stevens) и Пьер Карпман (Pierre Karpman) из исследовательского центра Centrum Wiskunde and Informatica (CWI) в Амстердаме. В минувший четверг соавторы представили результаты двухлетнего исследования в виде блог-записи и научной публикации.

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

«Создание двух конфликтующих PDF-файлов по образу и подобию двух договоров аренды с разным уровнем оплаты позволяет обманом заставить кого-либо создать действительную подпись для контракта с высокой платой, дав ему или ей подписать более дешевый вариант», — поясняют авторы исследования.

Для расчета коллизии была задействована облачная инфраструктура Google — по словам исследователей, это было «одно из самых масштабных вычислений, когда-либо производившихся». Поиск коллизии совокупно потребовал свыше 9 трлн (1018) вычислительных операций, при этом первая фаза атаки могла бы вылиться в 6,5 тыс. лет процессорного времени, вторая — в 110 лет работы графического процессора (GPU). Несмотря на это, авторы исследования утверждают, что их метод более чем в 100 тыс. раз быстрее, чем брутфорс-атака на SHA-1, теоретическая возможность которой была доказана, но практическая реализация требует 12 млн GPU-лет.

Расчеты для первой фазы атаки были выполнены на кластере Google, ЦП которого разнесены по восьми хостинг-площадкам. Вторая фаза обсчитывалась на кластере, составленном из графических процессоров Tesla K20, K40 и K80 и также размещенном у Google. В академической статье отмечено, что использование GPU было критически важным фактором, позволившим «значительно сократить календарное время, необходимое для выполнения вычислений».

Почти одновременно с публикацией SHAttered компания Google начала предлагать поддержку GPU на своей облачной платформе. Такие процессоры не только значительно ускоряют отображение графики, в том числе трехмерной, но также зачастую используются в мощных гибридных системах в качестве ускорителей параллельных вычислений.

Специалисты по криптографии давно предрекли закат SHA-1. Теоретическая возможность атак коллизией хэша на этот алгоритм была впервые доказана в 2005 году. Ведущие IT-компании призывали упразднить SHA-1 еще в 2013 и 2014 годах. В 2012 году известный криптограф Брюс Шнайер (Bruce Schneier) предсказал, что атака коллизией хэша на SHA-1 в 2015 году будет обходиться в $700 тыс., а в 2018-м — в $143 тыс.; по его словам, при такой стоимости ее вполне можно будет осуществить на практике, особенно если инициатор атаки — хорошо финансируемая ОПГ или правительственные хакеры.

В 2015 году исследователи Карпман и Стивенс, объединившись с Томасом Пейрином (Thomas Peyrin), опубликовали результаты теоретического исследования, доказавшие, что атака на функцию компрессии SHA-1 станет финансово возможной в ближайшие месяцы, а не годы, как считалось ранее. Вскоре после этой публикации Стивенс начал работать с Бурштейном над SHAttered.

В последние месяцы наблюдается ускорение процесса снятия SHA-1 с поддержки в браузерах. Google и Mozilla пообещали отказаться от SHA-1 в январе, Microsoft — в феврале. Google также заявила, что усилила защиту Gmail и GSuite от коллизионных атак. Стивенс и Дэн Шумов, специалист по криптографии из Microsoft, создали специальный инструмент командной строки, позволяющий проверять файлы на предмет признаков такой атаки. Этот инструмент выложен на GitHub и доступен онлайн бесплатно.

При наличии разнообразных методов защиты Google решила придерживаться обычных сроков по раскрытию уязвимостей и заявила, что опубликует PoC-код для атаки коллизией хэша в конце мая. «Чем дальше, тем все более настоятельной становится миграция практикующих ИБ-специалистов на более надежные криптографические хэши, такие как SHA-256 и SHA-3, — пишут исследователи. — Следуя политике Google по раскрытию уязвимостей, мы выждем 90 дней, прежде чем выпускать код, позволяющий всем создать два PDF, которые содержат разные изображения, но при некоторых предварительных условиях дают одинаковую сумму хэшей SHA-1».

Несмотря на то что NIST официально признала SHA-1 морально устаревшим и ненадежным в 2011 году, этим криптоалгоритмом до сих пор достаточно широко пользуются, в том числе при обработке транзакций по кредитным картам и раздаче программных обновлений. Его также применяют для подписи электронных документов, резервных копий и даже в GIT — системе, используемой для отслеживания изменений в компьютерных файлах и координирования работы пользователей. Операторам таких систем давно было рекомендовано отказаться от SHA-1, и для тех, кто этого еще не сделал, ныне начался обратный отсчет.