Демонстрация столкновения SHA1 / пример

Question

Этот вопрос похож на на , но этот вопрос касается только демонстраций коллизий MD5.

Существуют ли какие-либо фактические пары коллизий SHA1 произвольных сообщений, известных до сих пор?

Я хотел бы использовать их, чтобы проверить, как различные программные продукты (мой собственный и какой-то сторонний) справляются с ним.

Выполнение некоторых поисков в Google только выявляло очень известные коллизии MD5 / SHA0 инекоторые намеки на подход к созданию коллизий SHA1, но я не смог достать ни одного примера.

Answer 1

По состоянию на 23 февраля 2017 г. этот ответ более не точен.

Более шести лет криптографическая хеш-функция SHA1, лежащая в основе безопасности Интернета, находится у двери смерти. Теперь он официально мертв, благодаря представлению первого известного случая фатального подвига, известного как «столкновение».

Нет известных столкновений для SHA-1. Прямо сейчас:

• Есть некоторые коллизии на уменьшенных версиях SHA-1, с менее чем 80 раундами стандартного SHA-1.
• Был описан алгоритм, который должен получить столкновение SHA-1 с вычислительным усилием, примерно эквивалентным 2 ⁶³ вызовам SHA-1 для маленьких сообщений; это намного лучше, чем универсальные алгоритмы (которые требуют в среднем 2 ⁸⁰ вызовов), но это все еще довольно много, и этот алгоритм еще не запущен.

Была предпринята попытка получить коллизию SHA-1, используя энергию от тех, у кого были запасные тактовые циклы ЦП, чтобы пожертвовать, с помощью структуры BOINC для организации всего этого, но не было достаточно добровольцев и усилия были прекращены в прошлом году. Следовательно, фактического столкновения SHA-1 пока нет.

Теоретические атаки основаны на некоторых предположениях, которые могут оказаться слегка ложными; например, атака на MD5 на самом деле немного быстрее, чем ожидалось (в какой-то момент есть свойство, которое должно быть выполнено, с теоретической вероятностью 2 ^-28 , но на практике это больше похоже на 2 ^-27,7 , т. Е. Атака на 20% быстрее, чем предполагалось). До сих пор считается, что теоретическая атака верна, а сложность «довольно точна».

Answer 2

Блог безопасности Google описывает первое публичное преднамеренное столкновение SHA-1 здесь: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

Прямые ссылки на 2 PDF-файла с тем же SHA-1 (из )сайт, посвященный этой находке ):

• https://shattered.it/static/shattered-1.pdf
• https://shattered.it/static/shattered-2.pdf

Снова Марк Стивенс был вовлечен вместе с CWI Amsterdamи некоторые сотрудники Google, но на этот раз для полного цикла SHA-1 на двух построенных PDF-файлах.

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

Google, очевидно, опубликует сопроводительный исходный код через 90 дней (23 февраля,2017), предоставляя пострадавшим системным поставщикам некоторое время для обновления своих материалов.

Еще неизвестно, как программное обеспечение, такое как git, и поставщики услуг, такие как GitHub, будут справляться с этим, особенно с точки зрения обратной совместимости.

Линус Торвальдс опубликовал заявление относительно git , отметив, что они совместимы с новыми хешами, но что это займет время.

Кстати,демонстрация «разрушенного» столкновения не влияет на git (без модификаций), потому что она использует SHA-1 следующим образом:

sha1("blob " + <size in octets as text> + "\0" + <contents>)

Вы можете получить хэш git, используя git hash-object <file path>, даже если файл не являетсяв git.

В новостях, связанных с , Subversion, по-видимому, является первой реальной жертвой этого доказательства, что приводит к повреждению хранилища, что делает упомянутые файлы практическими.

- ПРЕДЫДУЩАЯ ... -

76-раундовое столкновение было обнаружено Марк Стивенс .

Криптограф Жан-Филипп Аумассон, один из создателей BLAKE и SipHash и инициатор конкурса хэширования паролей (PHC) , догадывается о столкновении SHA-1 на полных 80раунды будут найдены к 2020 году .

Согласно продолжающееся исследование Marc Stevens et al.опубликовано в октябре 2015 года ,

... мы оцениваем стоимость столкновения SHA-1 сегодня (то есть осень 2015 года) между 75K $ и 120K $ аренда облачных вычислений Amazon EC2 на несколько месяцев.Напротив, эксперт по безопасности Брюс Шнайер ранее прогнозировал, что к 2018 году стоимость столкновения SHA-1 составит ~ 173 тыс. Долларов.

Они также описывают атаку на столкновение для функции сжатия SHA-1.

Answer 3

Первое известное столкновение было опубликовано в https://shattered.it/

Answer 4

Есть пример в Атаках поиска столкновений на бумаге SHA1 от Wang, Yin и Yu, 2005 г., но только для ослабленной версии с 58 раундами SHA-1.(Полный официальный SHA-1 выполняет 80 раундов.)

3 A collision example for 58-step SHA1

         h₁ = compress(h₀,M₀) = compress(h₀,M'₀)
 _____________________________________________________
   h₀:  67452301 efcdab89 98badcfe 10325476 c3d2e1f0
 _____________________________________________________
   M₀:  132b5ab6 a115775f 5bfddd6b 4dc470eb
        0637938a 6cceb733 0c86a386 68080139
        534047a4 a42fc29a 06085121 a3131f73
        ad5da5cf 13375402 40bdc7c2 d5a839e2
 _____________________________________________________
   M'₀: 332b5ab6 c115776d 3bfddd28 6dc470ab
        e63793c8 0cceb731 8c86a387 68080119
        534047a7 e42fc2c8 46085161 43131f21
        0d5da5cf 93375442 60bdc7c3 f5a83982
 _____________________________________________________
   h₁:  9768e739 b662af82 a0137d3e 918747cf c8ceb7d4
 _____________________________________________________

Table 2: A collision of SHA1 reduced to 58 steps. The two
messages that collide are M₀ and M'₀. Note that padding
rules were not applied to the messages. 

Answer 5

Не совсем коллизия SHA1, но есть коллизии PBKDF2-HMAC-SHA1 код аутентификации дайджеста сообщения.

Например, PBKDF2 (SHA1, пароль, соль, итерации, dkLen)из двух паролей plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd и eBkXQTfuBqp\'cTcar&g*, соль hunter2, 4 итераций, обеспечивают одинаковое значение (35d1c8f259129dc800ec8e073bb68f995424619c для dkLen 20).

На самом деле это тривиальнонайти такие коллизии для строк длиной более 64 байтов.

Другой пример коллизии (Python3):

>>> import hashlib, binascii
>>> def pbkdf2sha1hex(x, salt, iters):
...     h = hashlib.pbkdf2_hmac('sha1', x, salt, iters)
...     return binascii.hexlify(h)
>>> pbkdf2sha1hex(b'/3649409/demonstratsiya-stolknoveniya-sha1-primer', b'NaCl', 1000000)
b'20177527e04e05d5e7b448c1ab2b872f86831d0b'
>>> pbkdf2sha1hex(b'\x8c\xbf8\x94\xbc\xf4\xbe\x90xT,r\xbc\x03\xd1\xed\xd9\xea\xfb\x9f', b'NaCl', 1000000)
b'20177527e04e05d5e7b448c1ab2b872f86831d0b'

Обратите внимание, что та же самая «проблема» относится к PBKDF2-HMAC-SHA256 также:

>>> h1 = pbkdf2_hmac('sha256', b'/3649409/demonstratsiya-stolknoveniya-sha1-primer', b'NaCl', 1000000)
b"\xcf\xc5\xee\x15=\r\x0b\x0e\x89r\x9b\xe1\xb7'+\xa4'o\x98kn++u\x12\xec\xd9\xec\xea\xebL\xb7"
>>> h2 = pbkdf2_hmac('sha256', b'.\x83\xb0D\x93D\x9f\x162\xf3\xd4x\xb6\x1a\x9f-\x1f\xdb\xdc\xa4\x8f\xb3\x95Y5\xea\x99*\x97\x00V\x81', b'NaCl', 1000000)
>>> h1 == h2
True

Все это происходит, потому что из определения PBKDF2 для длинных строк он содержит:
PBKDF2(hashalgo, s, ...) == PBKDF2(hashalgo, hashalgo(s), ...).

Более подробная информация, например, здесь:https://mathiasbynens.be/notes/pbkdf2-hmac