Насколько безопасно я могу предположить уникальность части SHA1-хэша? - PullRequest
9 голосов
/ 22 марта 2011

В настоящее время я использую SHA1, чтобы несколько сократить URL:

Digest::SHA1.hexdigest("salt-" + url)

Насколько безопасно использовать только первые 8 символов SHA1 в качестве уникального идентификатора, как, очевидно, делает GitHub для коммитов?

Ответы [ 4 ]

11 голосов
/ 22 марта 2011

Чтобы рассчитать вероятность столкновения с заданной длиной и количеством имеющихся хешей, см. Задачу на день рождения .Я не знаю, сколько хешей у вас будет, но вот несколько примеров.8 шестнадцатеричных символов - это 32 бита, поэтому для около 100 хэшей вероятность столкновения составляет около 1/1 000 000, для 10 000 хешей - около 1/100, для 100 000 - 3/4 и т. Д.

См. Таблицу встатья Атака на день рождения в Википедии, чтобы найти хорошую длину хеша, которая бы удовлетворяла вашим потребностям.Например, если вы хотите, чтобы коллизия была менее вероятной, чем 1/1 000 000 000 для набора из более чем 100 000 хешей, используйте 64 бита или 16 шестнадцатеричных цифр.

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

7 голосов
/ 22 марта 2011

Если вы говорите о SHA-1 в шестнадцатеричном формате, то вы получаете только 4 бита на символ, всего 32 бита. Вероятность столкновения обратно пропорциональна квадратному корню из этого максимального значения, поэтому около 1/65536. Если ваш URL укорачивает, то, вероятно, пройдет очень много времени, прежде чем вы начнете видеть коллизии.

Что касается альтернатив, наиболее очевидным является, вероятно, просто ведение счетчика. Поскольку вам нужно сохранить таблицу URL-адресов, чтобы перевести сокращенный URL-адрес обратно в исходный, вы просто сохраняете каждый новый URL-адрес в своей таблице. Если он уже присутствовал, вы даете его существующий номер. В противном случае, вы вставляете его и даете ему новый номер. В любом случае, вы даете этот номер пользователю.

3 голосов
/ 22 марта 2011

Это зависит от того, чего вы пытаетесь достичь.Вывод SHA1 является фактически случайным по отношению к входу (выход хорошей хеш-функции изменяется на половину своих битов на основе однобитового изменения на входе, а SHA1, хотя и не идеальный, довольно хорош), ивзяв 32-разрядное (в предположении 8 шестнадцатеричных) подмножество 160-разрядного вывода, вы уменьшите пространство вывода с 2 ^ 160 до 2 ^ 32 значений.При прочих равных условиях, которыми они никогда не являются, это значительно уменьшит сложность обнаружения коллизии.

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

Мне было бы более интересно узнать, почему вы это делаете.Это касается URL, которые пользователь должен будет запомнить и ввести?Если это так, добавление случайных шестнадцатеричных цифр, вероятно, является плохой идеей.Это URL или параметр URL, который будет просто передан программно?Тогда мне было бы наплевать на длину.В любом случае, возможно, есть лучшие способы сделать то, что вы пытаетесь достичь.

2 голосов
/ 22 марта 2011

Если вы используете двоичный выход для SHA1 и Base64 для кодирования результата, вы получите гораздо более высокую плотность информации на символ;у вас могут быть те же 8-символьные имена, но вместо возможностей 16^8 (2^32), у вас будет 64^8 (2^48) возможностей.

Используя предположение, что 50% вероятности столкновения масштабируется с 1.177 * sqrt (N) , при использовании кодирования в стиле Base64 потребуется 256 раз больше входных данных, чем шестнадцатеричный вывод, прежде чем будет достигнута вероятность столкновения 50%.

...