Представлен более эффективный метод определения префиксов коллизий для SHA-1

Discussion in 'Мировые новости. Обсуждения.' started by Suicide, 13 May 2019.

  1. Suicide

    Suicide Super Moderator
    Staff Member

    Joined:
    24 Apr 2009
    Messages:
    2,577
    Likes Received:
    3,507
    Reputations:
    693
    Исследователи из французского государственного института исследований в информатике и автоматике (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, особенно в сертификатах и цифровых подписях.


     
    seostock and CKAP like this.
  2. CKAP

    CKAP Well-Known Member

    Joined:
    9 Oct 2015
    Messages:
    612
    Likes Received:
    2,401
    Reputations:
    7
    Сложно..[​IMG]
     
    Suicide likes this.
  3. user100

    user100 Moderator

    Joined:
    24 Dec 2011
    Messages:
    3,283
    Likes Received:
    9,531
    Reputations:
    338
    Ништяк, брут будет ещё быстрее :)
     
    _________________________
    Suicide likes this.
Loading...