У меня есть код на моем сайте с PHP, который создает случайный хэш (с использованием sha1()), и я использую его для сопоставления записей в базе данных.
Каковы шансы столкновения? Должен ли я сгенерировать хэш, а затем сначала проверить, есть ли он в базе данных (я бы предпочел избежать лишнего запроса) или автоматически вставить его, исходя из вероятности того, что он вероятно не столкнется с другим.
Если вы предполагаете, что SHA-1 работает хорошо, вы можете сделать вывод, что вероятность того, что два заданных сообщения имеют одинаковый хэш, составляет 1 из 2 ^ 160 (поскольку SHA-1 создает 160-битный хеш).
2 ^ 160 - смехотворно большое число. Это примерно 10 ^ 48. Даже если в вашей базе данных миллион записей, вероятность того, что новая запись будет иметь тот же хэш, составляет 1 из 10 ^ 42.
SHA-1 оказался довольно хорошим, поэтому я не думаю, что вам вообще нужно беспокоиться о коллизиях.
В качестве побочного примечания используйте функцию PHP raw_output при использовании SHA-1, поскольку это приведет к более короткой строке и, следовательно, сделает ваши операции с базой данных немного быстрее.
РЕДАКТИРОВАТЬ: Чтобы решить парадокс дня рождения, база данных с 10 ^ 18 (миллион миллионов миллионов) записей имеет шанс примерно 1 на 0,0000000000003 столкновения. На самом деле не о чем беспокоиться.
Используйте симметричную схему шифрования и закрытый ключ сервера для шифрования идентификатора (и других значений) при их отправке клиенту и повторного дешифрования при получении. Позаботьтесь о том, чтобы ваша криптографическая функция обеспечивала как проверку конфиденциальности, так и целостность.
Это позволяет использовать разумные значения при разговоре с БД без каких-либо конфликтов, обеспечивает большую безопасность при разговоре с клиентом и снижает вероятность попадания на thedailyWTF примерно на 2 ^ 160.
См. Также Забивать гвоздь: старый башмак или стеклянная бутылка?!
почему бы не сделать что-то, что гарантирует отсутствие коллизий, а также гарантирует, что никто не может изменить параметр GET для просмотра того, чего не следует: используя соль, объедините идентификатор и его хэш.
$salt = "salty";
$key = sha1($salt . $id) . "-" . $id;
// 0c9ab85f8f9670a5ef2ac76beae296f47427a60a-5
даже если вы случайно наткнетесь на два числа, которые имеют один и тот же хэш sha1 (с вашей солью), тогда ключ $ все равно будет другим, и вы избежите всех столкновений.
Если вы используете в качестве входных данных численно увеличивающиеся идентификаторы, то вероятность столкновения SHA-1 практически равна нулю.
Если идентификатор является единственным входом, то SHA-1 кажется излишним - создание 160-битного хэша из 32-битного целого числа. Я бы предпочел использовать модульное возведение в степень, например выберите большое (32-битное) простое число p, вычислите модульный генератор g этой группы, а затем используйте g ^ id. Это гарантирует отсутствие коллизий и дает только 32-битные «хэши».
SHA-1 создает дайджест длиной 160 бит. Поэтому вы в безопасности, пока у вас меньше 2 ^ (160/2) записей. Разделение на 2 связано с парадоксом дня рождения.
Из первых принципов:
SHA-1 создает 160-битный дайджест. Предполагая, что он использует все битовое пространство равномерно (что, по-видимому, именно для этого он был разработан), это всего лишь 2 ^ -160 шансов на каждую вставку, что вы получите столкновение.
Таким образом, для каждой вставки должно быть безопасно предположить, что столкновения нет, и обработать ошибку, если она есть.
Это не означает, что вы можете полностью игнорировать вероятность столкновения.
Парадокс дня рождения предполагает, что вероятность того, что в вашей базе данных есть хотя бы одна коллизия, выше, чем вы могли бы предположить, из-за возможных коллизий O (N ^ 2).
Задайте вопрос, сколько вам будет стоить столкновение. Если это бесплатный сайт, отлично. Если вы ведете бизнес, приносящий прибыль, и перезапись обойдется вам в контракт в миллион долларов, я бы подумал еще раз.
Я думаю, что вы поступаете неправильно.
Я думаю, вам нужно сохранить уникальный идентификатор, но вы хотите убедиться, что пользователи не могут вручную изменить идентификатор.
Один из способов сделать это - поместить в ссылку идентификатор и хэш идентификатора (с некоторыми дополнительными данными).
Например: (мой PHP ржавый, поэтому общий алгоритм будет :)
id = 5;
hash = hash("My Private String " + id)
link = "http://mySite.com/resource?id=" + id + "&hash=" + hash
Затем, когда вы получите запрос, просто подтвердите, что вы можете восстановить хеш из идентификатора. Это оставляет вас уязвимым для атаки на «My Private String», но это будет довольно сложно с вычислительной точки зрения, и вы всегда можете добавить что-то еще уникальное, что напрямую не доступно пользователю (например, идентификатор сеанса).
Есть очень простое правило, чтобы узнать, будет ли какой-либо алгоритм хеширования иметь коллизии или нет. Если выходной диапазон алгоритма - конечное число, рано или поздно у одного из них обязательно произойдет коллизия.
Несмотря на то, что SHA1 имеет очень большой диапазон хеш-возможностей 2 ^ 160, это все еще конечное число. Однако входные данные, которые можно передать этой функции, буквально бесконечны. При достаточно большом наборе входных данных коллизии неизбежны.
Другие комментарии касались вас вероятностей, однако, если вы посмотрите на это прагматично, вы сможете получить для себя однозначный ответ.
Вы сами сказали, что собираетесь хешировать свои последовательные идентификаторы. Было бы легко написать тестовый пример. Переберите ~ 100000000 идентификаторов и проверьте наличие коллизий. Это не займет много времени. С другой стороны, у вас может закончиться нехватка памяти на четверть пути.
Я не думаю, что sha1 () доставит вам какие-либо проблемы, слабая генерация случайных чисел - более вероятный кандидат на коллизии.
Стефан Эссер написал хорошую статью по теме.
точная вероятность того, что n хэшей столкнутся с S общим количеством различных возможных хэшей:
(идеальное поведение хеш-функции, парадокс дня рождения, бла-бла-бла ...)
Вы не сможете вычислить это напрямую, поскольку это огромные числа, поэтому мы используем ограничения и делаем 2 предположения:
С этими двумя предположениями вероятность столкновения может быть вычислена с помощью:
Теперь вы можете вычислить вероятность столкновения для некоторого количества n записей. Это очень и очень точно для всего, что меньше 2 ^ 70 записей для sha1 (S = 2 ^ 160), чем хуже приближение, тем больше n подхода 2 ^ 80.
Например, если вы хотите сохранить огромное количество пользователей, в частности столько же, сколько человек в мире (~ 8 миллиардов), и вы используете sha1 (S = 2 ^ 160), вероятность столкновения будет 2,5e-29 (обратите внимание, что выполняются 2 предположения). Для справки: вероятность выиграть джекпот Euromillion составляет 7e-9 приблизительно.
Вычислите предел напрямую без второго предположения.
Например, первое столкновение ожидается около квадратного корня из S (в случае sha1 n = 2 ^ 80). При этом значении второе условие не выполняется, но мы можем вычислить предел напрямую с помощью:
что составляет 40% ок. вероятности столкновения.
