SHA-1 коллизии с заданным префиксом
From Collisions to Chosen-Prefix Collisions Application to Full SHA-1.pdf
Оригинал: https://mailarchive.ietf.org/arch/msg/cfrg/NhiGvOFzcEw108YLwF_ndyfB1k4
[Cfrg] Notice on chosen-prefix collisions for SHA-1
Thomas Peyrin Fri, 10 May 2019 14:09 UTC
Dear CFRG members,
We, Gaetan Leurent and myself, would like to emphasize some results we will present in a few days at Eurocrypt 2019 [LP19]. ePrint version available here: https://eprint.iacr.org/2019/459.pdf
[TL;DR] Chosen-prefix collisions for SHA-1 hash function are now practical (cost lower than 100K $), all hope is lost.
As you might know, SHA-1 hash function has been broken theoretically since 2005 [W+05] and an actual collision was computed in 2017 [S+17]. This clearly makes SHA-1 a function to avoid, but even though deprecation efforts have been conducted since many years, SHA-1 is still used in several security products and RFC standards (TLS 1.2, git, ...)
Finding a collision attack breaks the hash function, but the actual damage that can be done with such a collision is somewhat limited as the attacker will have little to no control on the actual data that collides. A much more interesting attack is to find a so-called chosen-prefix collision, where the attacker can freely choose the prefix for the two colliding messages. This was for example used to create rogue-CA for MD5 [S+09] and in general chosen-prefix collision attacks have a huge impact on security [BL16].
Yet, these chosen-prefix collisions are believed to be much harder to find than classical collisions. For SHA-1, the best previous search method required 2^77 SHA-1 evaluations [S13], which remained out of reach in practice. In our article, we explain how to drastically reduce the cost of finding chosen-prefix collisions for SHA-1, down to almost the same cost as finding a classical collision. With some additional improvements that we are currently working on, we evaluate that one can find a chosen-prefix collision for SHA-1 with a budget of less than 100K US$. We therefore recommend to avoid SHA-1 at all cost, especially for use in certificates/digital signatures.
[BL16] Karthikeyan Bhargavan, Gaëtan Leurent, "Transcript Collision Attacks: Breaking Authentication in TLS, IKE and SSH", NDSS 2016
[LP19] Gaetan Leurent Thomas Peyrin, “From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1”, Eurocrypt 2019
[S+09] Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen K. Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger, “Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate”, Crypto 2009
[S13] Marc Stevens, “New Collision Attacks on SHA-1 Based on Optimal Joint Local-Collision Analysis”, Eurocrypt 2013
[S+17] Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov, "The first collision for full SHA-1", Crypto 2017
[W+05] Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, “Finding Collisions in the Full SHA-1”, Crypto 2005
Regards,
Thomas.
Представлена первая в истории атака поиска коллизий хэш-функций SHA-1 с заданным префиксом, представляющая собой более практичную версию коллизионной атаки на SHA-1, продемонстрированной экспертами Google два года назад. Это значит, что теперь атаки поиска коллизий хэш-функций могут осуществляться с использованием заданных значений и больше не являются случайными. Другими словами, отныне с их помощью злоумышленники смогут создавать дубликаты и подделывать определенные файлы.
Теоретическое описание взлома хэш-функций SHA-1 было опубликовано еще в 2005 году, но на практике осуществить атаку удалось лишь спустя 12 лет. В 2017 году ученым впервые удалось создать два файла с одинаковым хэшем SHA-1. Атака получила название SHAttered.
Криптографы предупреждали, что когда-нибудь алгоритм SHA-1 будет взломан на практике, но SHAttered появилась на три года раньше, чем они предполагали, и стоила намного дешевле - $110 тыс. ушло на аренду облачных вычислительных мощностей.
На прошлой неделе команда специалистов из Франции и Сингапура представила усовершенствованную версию SHAttered. С ее помощью злоумышленник может на свое усмотрение выбирать префикс для двух сообщений, что превращает атаку в серьезную угрозу. Например, атакующий может подделать любой подписанный SHA-1 документ, начиная от деловых бумаг и заканчивая TLS-сертификатами.
Команда исследователей из Франции и Сингапура не только представила атаку в теории, но и протестировала на практике все ее компоненты (правда, пример коллизии с заданным префиксом ученые не представили). Более того, атака обошлась намного дешевле, чем предполагалось. По подсчетам специалистов, на ее осуществление требуется менее $100 тыс. - сумма, вполне вписывающаяся в бюджет финансируемых правительством киберпреступников.
Исследователи из французского государственного института исследований в информатике и автоматике (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, особенно в сертификатах и цифровых подписях.
Коллизионная атака
Оригинал: https://mailarchive.ietf.org/arch/msg/cfrg/NhiGvOFzcEw108YLwF_ndyfB1k4
[Cfrg] Notice on chosen-prefix collisions for SHA-1
Thomas Peyrin Fri, 10 May 2019 14:09 UTC
Dear CFRG members,
We, Gaetan Leurent and myself, would like to emphasize some results we will present in a few days at Eurocrypt 2019 [LP19]. ePrint version available here: https://eprint.iacr.org/2019/459.pdf
[TL;DR] Chosen-prefix collisions for SHA-1 hash function are now practical (cost lower than 100K $), all hope is lost.
As you might know, SHA-1 hash function has been broken theoretically since 2005 [W+05] and an actual collision was computed in 2017 [S+17]. This clearly makes SHA-1 a function to avoid, but even though deprecation efforts have been conducted since many years, SHA-1 is still used in several security products and RFC standards (TLS 1.2, git, ...)
Finding a collision attack breaks the hash function, but the actual damage that can be done with such a collision is somewhat limited as the attacker will have little to no control on the actual data that collides. A much more interesting attack is to find a so-called chosen-prefix collision, where the attacker can freely choose the prefix for the two colliding messages. This was for example used to create rogue-CA for MD5 [S+09] and in general chosen-prefix collision attacks have a huge impact on security [BL16].
Yet, these chosen-prefix collisions are believed to be much harder to find than classical collisions. For SHA-1, the best previous search method required 2^77 SHA-1 evaluations [S13], which remained out of reach in practice. In our article, we explain how to drastically reduce the cost of finding chosen-prefix collisions for SHA-1, down to almost the same cost as finding a classical collision. With some additional improvements that we are currently working on, we evaluate that one can find a chosen-prefix collision for SHA-1 with a budget of less than 100K US$. We therefore recommend to avoid SHA-1 at all cost, especially for use in certificates/digital signatures.
[BL16] Karthikeyan Bhargavan, Gaëtan Leurent, "Transcript Collision Attacks: Breaking Authentication in TLS, IKE and SSH", NDSS 2016
[LP19] Gaetan Leurent Thomas Peyrin, “From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1”, Eurocrypt 2019
[S+09] Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen K. Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger, “Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate”, Crypto 2009
[S13] Marc Stevens, “New Collision Attacks on SHA-1 Based on Optimal Joint Local-Collision Analysis”, Eurocrypt 2013
[S+17] Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov, "The first collision for full SHA-1", Crypto 2017
[W+05] Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, “Finding Collisions in the Full SHA-1”, Crypto 2005
Regards,
Thomas.
Представлена первая в истории атака поиска коллизий хэш-функций SHA-1 с заданным префиксом, представляющая собой более практичную версию коллизионной атаки на SHA-1, продемонстрированной экспертами Google два года назад. Это значит, что теперь атаки поиска коллизий хэш-функций могут осуществляться с использованием заданных значений и больше не являются случайными. Другими словами, отныне с их помощью злоумышленники смогут создавать дубликаты и подделывать определенные файлы.
Теоретическое описание взлома хэш-функций SHA-1 было опубликовано еще в 2005 году, но на практике осуществить атаку удалось лишь спустя 12 лет. В 2017 году ученым впервые удалось создать два файла с одинаковым хэшем SHA-1. Атака получила название SHAttered.
Криптографы предупреждали, что когда-нибудь алгоритм SHA-1 будет взломан на практике, но SHAttered появилась на три года раньше, чем они предполагали, и стоила намного дешевле - $110 тыс. ушло на аренду облачных вычислительных мощностей.
На прошлой неделе команда специалистов из Франции и Сингапура представила усовершенствованную версию SHAttered. С ее помощью злоумышленник может на свое усмотрение выбирать префикс для двух сообщений, что превращает атаку в серьезную угрозу. Например, атакующий может подделать любой подписанный SHA-1 документ, начиная от деловых бумаг и заканчивая TLS-сертификатами.
Команда исследователей из Франции и Сингапура не только представила атаку в теории, но и протестировала на практике все ее компоненты (правда, пример коллизии с заданным префиксом ученые не представили). Более того, атака обошлась намного дешевле, чем предполагалось. По подсчетам специалистов, на ее осуществление требуется менее $100 тыс. - сумма, вполне вписывающаяся в бюджет финансируемых правительством киберпреступников.
Исследователи из французского государственного института исследований в информатике и автоматике (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, особенно в сертификатах и цифровых подписях.
Коллизионная атака