Исследователи из французского государственного института исследований в информатике и автоматике (INRIA) и Наньянского технологического университета (Сингапур) разработали усовершенствованный метод атаки на алгоритм SHA-1, существенно упрощающий создание двух разных документов с одинаковыми хэшами SHA-1. Суть метода в сведении операции полного подбора коллизии в SHA-1 к коллизионной атаке с заданным префиксом, при которой для существующих данных можно подобрать определённые дополнения, при которых для общего набора возникает коллизия. Иными словами, для двух существующих документов можно вычислить два дополнения, и если одно присоединить к первому документу, а другое ко второму — результирующие хэши SHA-1 для этих файлов будут одинаковы.

Данный вид атаки всё ещё требует огромных вычислений и подбор дополнений остаётся сложнее, чем обычный подбор коллизий, но и практическая эффективность результата существенно выше. Если до сих пор самый быстрый метод поиска дополнений для возникновения коллизии в SHA-1 требовал выполнения 2^77.1 операций, то новый метод снижает число вычислений до диапазона от 2^66.9 до 2^69.4. При таком уровне вычислений ориентировочная стоимость атаки составляет менее ста тысяч долларов, что вполне по карману спецслужбам и крупным корпорациям. Для сравнения на поиск обычной коллизии необходимо выполнить примерно 2^64.7 операций.

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

Предложенная стратегия поиска дополнений для возникновения коллизии подразумевает разбиение вычислений на два этапа. На первом этапе выполняется поиск блоков, находящихся на грани коллизии, путём встраивания случайных переменных цепочек в предопределённый целевой набор различий. На втором этапе на уровне отдельных блоков полученные цепочки различий сопоставляются с приводящими к коллизиям парами состояний, используя методы традиционных атак по подбору коллизий.

Несмотря на то, что теоретическая возможность атаки на SHA-1 доказана ещё в 2005 году, а на практике первая коллизия была подобрана в 2017 году, SHA-1 всё ещё остаётся в обиходе и охватывается некоторыми стандартами и технологиями (TLS 1.2, Git и т.п.). Основной целью проделанной работы было желание предоставить ещё один веский аргумент для незамедлительного прекращения использования SHA-1, особенно в сертификатах и цифровых подписях.

Источник: http://www.opennet.ru/opennews/art.shtml?num=50674