Исследователи из французского государственного института исследований в информатике и автоматике (INRIA) и Наньянского технологического университета (Сингапур) разработали усовершенствованный метод атаки на алгоритм SHA-1, существенно упрощающий создание двух разных документов с одинаковыми хэшами SHA-1. Суть метода в сведении операции полного подбора коллизии в SHA-1 к коллизионной атаке с заданным префиксом, при которой для существующих данных можно подобрать определённые дополнения, при которых для общего набора возникает коллизия. Иными словами, для двух существующих документов можно вычислить два дополнения, и если одно присоединить к первому документу, а другое ко второму - результирующие хэши SHA-1 для этих файлов будут одинаковы.
Данный вид атаки всё ещё требует огромных вычислений и подбор дополнений остаётся сложнее, чем обычный подбор коллизий, но и практическая эффективность результата существенно выше. Если до сих пор самый быстрый метод поиска дополнений для возникновения коллизии в SHA-1 требовал выполнения 277.1 операций, то новый метод снижает число вычислений до диапазона от 266.9 до 269.4. При таком уровне вычислений ориентировочная стоимость атаки составляет менее ста тысяч долларов, что вполне по карману спецслужбам и крупным корпорациям. Для сравнения на поиск обычной коллизии необходимо выполнить примерно 264.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, особенно в сертификатах и цифровых подписях.
Поддержать публикацию: Coinbase, Yandex.Money