Демонстрация столкновения SHA1 / пример
Этот вопрос похож на этот, но этот вопрос касается только демонстраций столкновений MD5.
Известны ли какие-либо реальные пары коллизий SHA1 произвольных сообщений?
Я хотел бы использовать их, чтобы проверить, как различные программные продукты (мой собственный и какой-то сторонний) справляются с этим.
Выполнение некоторых поисков в Google только выявило очень известные коллизии MD5 / SHA0 и некоторые намеки на подход к созданию коллизий SHA1, но я не смог достать ни одного примера.
5 ответов
Первое известное столкновение было опубликовано на https://shattered.it/
По состоянию на 23 февраля 2017 года этот ответ более не точен.
Более шести лет криптографическая хеш-функция SHA1, лежащая в основе безопасности Интернета, находится у двери смерти. Теперь он официально мертв, благодаря представлению первого известного случая фатального подвига, известного как "столкновение".
Для SHA-1 пока нет известных столкновений. Прямо сейчас:
- Есть некоторые коллизии на уменьшенных версиях SHA-1, с менее чем 80 раундами стандарта SHA-1.
- Был описан алгоритм, который должен получить столкновение SHA-1 с вычислительным усилием, примерно эквивалентным 2 63 вызовам SHA-1 для маленьких сообщений; это намного лучше, чем универсальные алгоритмы (которые требуют в среднем 2 80 вызовов), но это все еще довольно много, и этот алгоритм еще не запущен.
Была предпринята попытка получить коллизию SHA-1 за счет использования энергии от тех, у кого были запасные тактовые циклы ЦП, чтобы пожертвовать, с помощью структуры BOINC, чтобы организовать все это, но не было достаточно добровольцев, и усилия были прекращены в прошлом году. Следовательно, фактического столкновения SHA-1 пока нет.
Теоретические атаки основаны на некоторых предположениях, которые могут оказаться слегка ложными; например, атака на MD5 на самом деле немного быстрее, чем ожидалось (в какой-то момент есть свойство, которое должно быть выполнено, с теоретической вероятностью 2 -28, но на практике это больше похоже на 2 -27,7, т.е. атака на 20% быстрее, чем прогнозировалось). До сих пор считается, что теоретическая атака верна, а сложность "довольно точна".
Блог безопасности Google описывает первое публичное преднамеренное столкновение SHA-1 здесь: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html
Прямые ссылки на 2 файла PDF с тем же SHA-1 (с сайта, посвященного этой находке):
Снова Марк Стивенс был вовлечен вместе с CWI Amsterdam и некоторыми сотрудниками Google, но на этот раз для полного цикла SHA-1 на двух построенных PDF-файлах.
Стивенс также отмечает, что из-за конструкции Меркле-Дамгарда SHA-1, оба 2 PDF-файла могут быть расширены (добавлены) с одинаковыми произвольными данными для получения более длинных версий, хэширующих к одному и тому же дайджесту.
По всей видимости, Google опубликует сопроводительный исходный код через 90 дней (23 февраля 2017 г.), что даст поставщикам уязвимых систем некоторое время для обновления своих материалов.
Еще неизвестно, как с этим справятся такие программы, как git, и поставщики услуг, такие как GitHub, особенно с точки зрения обратной совместимости.
Линус Торвальдс выступил с заявлением относительно git, отметив, что они совместимы с новыми хешами, но что это займет время.
Кстати, "разрушенная" демонстрация столкновений не влияет на git (без модификаций), потому что она использует SHA-1 следующим образом:
sha1("blob " + <size in octets as text> + "\0" + <contents>)
Вы можете получить git hash используя git hash-object <file path>, даже если файл не в git.
В связанных новостях Subversion, кажется, является первой реальной жертвой этого доказательства, вызывая повреждение хранилища, тем самым делая упомянутые файлы практическими эксплойтами.
- ПРЕДЫДУЩАЯ... -
Столкновение с 76 раундами было обнаружено Марком Стивенсом.
Криптограф Жан-Филипп Аумассон, один из создателей BLAKE и SipHash и инициатор конкурса хэширования паролей (PHC), предполагает, что коллизия SHA-1 в полных 80 раундах будет обнаружена к 2020 году.
Согласно текущим исследованиям Марка Стивенса и соавт. опубликовано в октябре 2015 года,
... мы оцениваем стоимость коллизии SHA-1 сегодня (то есть осенью 2015 года) между 75K$ и 120K$, арендуя облачные вычисления Amazon EC2 в течение нескольких месяцев. Напротив, эксперт по безопасности Брюс Шнайер ранее прогнозировал, что к 2018 году стоимость столкновения SHA-1 составит ~ 173 тыс. Долларов.
Они также описывают атаку на столкновение для функции сжатия SHA-1.
В статье " Атаки по поиску столкновений на бумаге SHA1" есть пример Ван, Инь и Ю, 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.
Не совсем коллизия 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'http://stackru.com/questions/3475648/sha1-collision-demo-example/31136714', 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'http://stackru.com/questions/3475648/sha1-collision-demo-example/31136714', 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