Действительно ли возможно получить идентичный хеш SHA1? [дубликат]
4 ответа
То, что вы описали, называется коллизией. Коллизии обязательно существуют, поскольку 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 раз быстрее, чем алгоритм birthday-paradox. Такая атака не должна быть выполнима на истинном случайном оракуле. Имейте в виду, что эта атака не была фактически завершена, она остается теоретической (некоторые люди пытались, но, видимо, не смогли найти достаточно мощности процессора)(Update: по состоянию на начало 2017 года, кто-то сделал вычисление SHA-1 коллизии с помощью вышеупомянутого метода, и это сработало точно так, как было предсказано). Тем не менее, теория выглядит обоснованной, и действительно кажется, что 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 бит.
В хэш-функции почти всегда возможна коллизия. SHA1 на сегодняшний день достаточно безопасен для создания непредсказуемых коллизий. Опасность заключается в том, что когда коллизии можно предсказать, нет необходимости знать исходный входной хэш, чтобы сгенерировать такой же выходной хеш-код.
Например, в прошлом году были совершены атаки на MD5 против подписи сертификата сервера SSL, как показано в эпизоде 179 подкаста Security Now . Это позволило опытным злоумышленникам сгенерировать поддельный сертификат сервера SSL для мошенника. веб-сайт и кажется реальным. По этой причине настоятельно рекомендуется избегать покупки сертификатов, подписанных MD5.
То, о чем вы говорите, называется коллизией. Вот статья о коллизиях SHA1: http://www.rsa.com/rsalabs/node.asp?id=2927
Edit: So another answerer beat me to mention the pigeon hole principle LOL, but to clarify this is why it's called the pigeon hole principle, because if you have some holes cut out for carrier pigeons to nest in, but you have more pigeons than holes, then some of the pigeons (an input value) must share a hole (the output value).
Да, это возможно из-за принципа голубиной ямы.
Большинство хэшей (также и sha1) имеют фиксированную длину выхода, в то время как вход имеет произвольный размер. Поэтому, если долго пытаться, их можно найти.
Однако криптографические хэш-функции (например, семейство sha, семейство md и т.д.) разработаны для минимизации таких коллизий. Лучшая из известных атак требует 2^63 попыток найти коллизию, так что шанс равен 2^(-63), что на практике равно 0.