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

    

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

    

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

SHA1(S1) == SHA1(S2)

это правда?

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

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

Пример:

Resource ID: X123
Parent ID: P123

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

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

75 голосов | спросил drozzy 19 MarpmFri, 19 Mar 2010 20:33:50 +03002010-03-19T20:33:50+03:0008 2010, 20:33:50

4 ответа


0

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

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

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

ответил Thomas Pornin 20 MaramSat, 20 Mar 2010 00:54:39 +03002010-03-20T00:54:39+03:0012 2010, 00:54:39
0

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

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

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

ответил Henri 19 MarpmFri, 19 Mar 2010 20:45:13 +03002010-03-19T20:45:13+03:0008 2010, 20:45:13
0

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

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

ответил spoulson 20 MaramSat, 20 Mar 2010 05:02:59 +03002010-03-20T05:02:59+03:0005 2010, 05:02:59
0

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

ответил Vladimir Kornea 22 J000000Tuesday14 2014, 01:50:55

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132