У меня есть код на моем сайте с PHP, который создает случайный хеш (используя sha1()), и я использую его для сопоставления записей в базе данных.
Каковы шансы на столкновение? Должен ли я генерировать хэш, а затем сначала проверить, если он в базе данных (я бы предпочел избежать дополнительного запроса) или автоматически вставить его, исходя из вероятности того, что он, вероятно, не столкнется с другим.
Если вы предполагаете, что SHA-1 выполняет хорошую работу, вы можете заключить, что существует вероятность 1 из 2 ^ 160, что два заданных сообщения имеют одинаковый хеш (поскольку SHA-1 создает 160-битный хэш).
2 ^ 160 - смехотворно большое число. Это примерно 10 ^ 48. Даже если у вас есть миллион записей в вашей базе данных, это все еще вероятность того, что новая запись будет иметь один и тот же хэш.
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).
Если вам нужно обфускать некоторые данные в вашем URL-адресе, чтобы скрыть данные, вы делаете что-то неправильно.
Задайте вопрос, что будет стоить вам, если произойдет столкновение. Если это бесплатный сайт. Если вы управляете бизнесом по созданию денег, а переоценка обойдется вам в миллион долларов, тогда я подумаю еще раз.
Я думаю, вы идете по этому неправильно. Я думаю, вам нужно сохранить уникальный идентификатор, но вы хотите, чтобы пользователи не могли вручную изменить идентификатор.
Один из способов сделать это - поместить идентификатор и хэш идентификатора (с некоторыми дополнительными данными) в ссылку.
Пример: (мой PHP ржавый, поэтому общий алгоритм будет:)
id = 5;
hash = hash("My Private String " + id)
link = "http://mySite.com/resource?id=" + id + "&hash=" + hash
Затем, когда вы получаете запрос, просто подтвердите, что вы можете восстановить хэш из ID. Это оставляет вас открытой для атаки, чтобы выработать "Моя приватная строка", но это будет довольно сложно вычислить, и вы всегда можете добавить что-то еще уникальное, которое не доступно пользователю (например, идентификатор сеанса).
Существует очень простое правило выяснить, будет ли какой-либо алгоритм хэширования иметь коллизии или нет. Если диапазон результатов алгоритма является конечным числом, рано или поздно у него будет столкновение.
Несмотря на то, что SHA1 имеет очень большой диапазон возможностей хэша 2 ^ 160, его все еще конечное число. Однако входы, которые могут быть переданы на эту функцию, буквально бесконечны. Учитывая достаточно большой набор входных данных, столкновения неизбежно произойдут.
Другие комментарии затронули вас по вероятностям, однако, если вы посмотрите на это прагматично, вы можете получить определенный ответ для себя.
Вы сами сказали, что собираетесь собирать свои последовательные идентификаторы. Было бы легко закодировать тестовый пример. Итерация через ~ 100 000 000 идентификаторов и проверка на наличие столкновений. Это не займет много времени. С другой стороны, у вас может закончиться четверть пути.
Я не думаю, что sha1() будет вам неприятно здесь, слабая генерация случайных чисел является более вероятным кандидатом на столкновение.
Стефан Эссер написал хорошую статью статью по этой теме.