Можно ли получить идентичный хэш SHA1?

Ответ 1

То, что вы описываете, называется столкновением. Коллизии обязательно существуют, поскольку SHA-1 принимает в качестве входных данных еще много различных сообщений, которые могут создавать отдельные выходы (SHA-1 может потреблять любую строку бит до 2 ^ 64 бит, но выводит только 160 бит, таким образом, по меньшей мере один вывод значение должно появляться несколько раз). Это наблюдение справедливо для любой функции с выходом, меньшим, чем его вход, независимо от того, является ли функция "хорошей" хэш-функцией или нет.

Предполагая, что SHA-1 ведет себя как "случайный оракул" (концептуальный объект, который в основном возвращает случайные значения, с единственным ограничением, которое, как только оно вернуло выход v на входе m, должно всегда после этого возвращать v на входе m), то вероятность столкновения для любых двух различных строк S1 и S2 должна быть 2 ^ (- 160). Все еще в предположении, что SHA-1 ведет себя как случайный оракул, если вы собираете много входных строк, то вы начнете наблюдать столкновения после того, как собрали около 2 ^ 80 таких строк.

(Это 2 ^ 80, а не 2 ^ 160, потому что с 2 ^ 80 строк вы можете сделать около 2 ^ 159 пар строк. Это часто называют "парадоксальным днем ​​рождения", потому что это становится неожиданностью для большинства людей, когда применяется к столкновениям в дни рождения. См. страницу Википедии по этому вопросу.)

Теперь мы сильно подозреваем, что SHA-1 действительно не ведет себя как случайный оракул, потому что подход "день рождения-парадокс" является оптимальным алгоритмом поиска столкновений случайного оракула. Тем не менее, существует опубликованная атака, которая должна найти столкновение примерно на 2 ^ 63 шага, следовательно, 2 ^ 17 = 131072 раз быстрее, чем алгоритм дня рождения-парадокса. Такая атака не должна выполняться на истинном случайном оракуле. Имейте в виду, что эта атака на самом деле не завершена, она остается теоретической (некоторые люди пытались, но, по-видимому, не смогли найти достаточную мощность процессора) ( Обновление: по состоянию на начало 2017 года, кто-то вычислил SHA-1 collision с вышеупомянутым методом, и он работал точно так же, как и было предсказано). Тем не менее, теория выглядит здорово, и действительно кажется, что SHA-1 не случайный оракул. Соответственно, что касается вероятности столкновения, ну, все ставки отключены.

Что касается вашего третьего вопроса: для функции с n-битным выходом необходимо обязательно коллизии, если вы можете вводить более 2 ^ n отдельных сообщений, т.е. если максимальная длина входного сообщения больше n. С оценкой m ниже n, ответ не так прост. Если функция ведет себя как случайный оракул, то вероятность существования столкновения уменьшается с m, а не линейно, скорее, с крутым обрезанием вокруг m = n/2. Это тот же анализ, что и парадокс дня рождения. При использовании SHA-1 это означает, что если m < 80, то есть вероятность того, что столкновения нет, а m > 80 делает существование хотя бы одного столкновения очень вероятным (при m > 160 это становится достоверностью).

Обратите внимание, что существует различие между "существует столкновение" и "вы обнаруживаете столкновение". Даже когда столкновение должно существовать, вы все равно получаете свою вероятность 2 ^ (- 160) каждый раз, когда пытаетесь. Что означает предыдущий параграф, так это то, что такая вероятность не имеет смысла, если вы не можете (концептуально) попробовать 2 ^ 160 пар строк, например. потому что вы ограничиваете себя строками менее 80 бит.

Ответ 2

Да, это возможно из-за принцип голубиной дыры.

Большинство хешей (также sha1) имеют фиксированную длину вывода, а вход имеет произвольный размер. Поэтому, если вы попробуете достаточно долго, вы можете их найти.

Однако криптографические хэш-функции (например, sha-family, md-family и т.д.) предназначены для минимизации таких столкновений. Лучшая атака, известная, требует 2 ^ 63 попыток найти столкновение, поэтому вероятность 2 ^ (- 63) равна 0 на практике.

Ответ 3

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

Например, атаки против MD5 были сделаны против подписания сертификата SSL-сервера в прошлом году, как показано в Security Now эпизоде ​​подкаста 179. Это позволило сложным атакующим создавать фальшивый сертификат SSL-сервера для сайта-изгоев и, по-видимому, являться предметом реала. По этой причине настоятельно рекомендуется избегать приобретения сертификатов, подписанных MD5.

Ответ 4

git использует хеши SHA1 в качестве идентификаторов, и до 2014 года все еще не известны столкновения SHA1. Очевидно, что алгоритм SHA1 является магическим. Я думаю, что это хорошая ставка, что коллизий не существует для строк вашей длины, поскольку они были бы открыты к настоящему времени. Однако, если вы не доверяете магии и не являетесь игроком ставок, вы можете генерировать случайные строки и связывать их с вашими идентификаторами в своей БД. Но если вы используете хэши SHA1 и первым обнаруживаете столкновение, вы можете просто изменить вашу систему, чтобы использовать случайные строки в то время, сохраняя хэши SHA1 как "случайные" строки для устаревших идентификаторов.

Ответ 5

То, о чем вы говорите, называется столкновением. Вот статья о столкновениях SHA1: http://www.rsa.com/rsalabs/node.asp?id=2927

Edit: Так что другой ответчик избил меня, чтобы упомянуть принцип голубого дыра LOL, но для того, чтобы прояснить это, это почему-то называется принципом голубины, потому что, если у вас есть отверстия, вырезанные для несущих голубей, чтобы гнездиться, но у вас есть больше голубей, чем отверстий, то некоторые из голубей (входное значение) должны разделять отверстие (выходное значение).