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

этот вопрос уже есть ответ здесь:

  • Вероятность столкновений SHA1 3 ответы

учитывая две разные строки S1 и S2 (S1 != S2) возможно ли, что:

SHA1(S1) == SHA1(S2)

- это правда?

  1. если да - с какой вероятностью?
  2. если нет - почему нет?
  3. есть ли верхний привязан к длине входной строки, для которой вероятность получения дубликатов равна 0? Или вычисление SHA1 (следовательно, вероятность дубликатов) не зависит от длины строки?

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

пример:

Resource ID: X123
Parent ID: P123

I не хочу раскрывать природу моего ресурса, чтобы позволить клиенту видеть "X123-P123".

вместо этого я хочу создать новый хэш столбца("X123-P123"), скажем, это AAAZZZ. Тогда клиент может запросить ресурс с идентификатором AAAZZZ и не знать о моем внутреннем идентификаторе и т. д.

5 75
hashset cryptography sha1 checksum

5 ответов:

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

предполагая, что SHA-1 ведет себя как "случайный оракул" (концептуальный объект, который в основном возвращает случайные значения, с единственным ограничением, что как только он вернул output 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 года, кто-то сделал вычислить a столкновение SHA-1 с вышеупомянутым методом, и он работал точно так, как предсказывалось). Тем не менее, теория выглядит здравой, и действительно кажется, что SHA-1 не является случайным оракулом. Соответственно, что касается вероятности столкновения, ну, все ставки выключены.

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

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

114

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

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

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

31

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

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

4

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

4

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

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

3