Hash Collision - каковы шансы?
У меня есть некоторый код на моем PHP-сайте, который создает случайный хэш (используя sha1()) и я использую его для сопоставления записей в базе данных.
Каковы шансы на столкновение? Должен ли я сгенерировать хеш, а затем сначала проверить, находится ли он в базе данных (я бы предпочел избежать дополнительного запроса), или автоматически вставить его, исходя из вероятности того, что он, вероятно, не столкнется с другим.
11 ответов
Если вы предполагаете, что 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 столкновения. На самом деле не стоит беспокоиться.
Используйте симметричную схему шифрования и личный ключ сервера для шифрования идентификатора (и других значений) при отправке их клиенту и повторной расшифровке при получении. Позаботьтесь о том, чтобы ваша криптографическая функция обеспечивала как конфиденциальность, так и проверку целостности.
Это позволяет вам использовать разумные значения при обращении к БД без каких-либо коллизий, обеспечивает большую безопасность при общении с клиентом и снижает вероятность попадания на ежедневный WTF примерно в 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. Это оставляет вас открытыми для атаки, чтобы выработать "My Private String", но это будет довольно сложно в вычислительном отношении, и вы всегда можете добавить что-то уникальное, что не доступно непосредственно пользователю (например, идентификатор сеанса).
Существует очень простое правило, чтобы выяснить, есть ли у любого алгоритма хеширования коллизии или нет. Если диапазон выходных данных алгоритма является конечным числом, то рано или поздно возникнет коллизия.
Несмотря на то, что SHA1 имеет очень большой диапазон хэш-возможностей 2^160, его число все еще ограничено. Однако входные данные, которые можно передать этой функции, буквально бесконечны. Учитывая достаточно большой набор входных данных, столкновения обязательно произойдут.
Другие комментарии охватили вас о вероятностях, однако, если вы посмотрите на это прагматично, то вы можете получить определенный ответ для себя.
Вы сами сказали, что собираетесь хэшировать свои последовательные идентификаторы. Было бы легко закодировать тестовый пример. Переберите ~100 000 000 идентификаторов и проверьте наличие коллизий. Это не займет много времени, чтобы сделать. С другой стороны, вы можете исчерпать память на четверть пути.
Я не думаю, что sha1() доставит вам здесь какие-то проблемы, слабая генерация случайных чисел - более вероятный кандидат на столкновения.
Стефан Эссер написал хорошую статью на эту тему.
Каковы шансы столкновения?
Я не вижу точного ответа на этот конкретный вопрос, поэтому здесь я привожу вероятность коллизии для некоторого количества записей:
- Кол-во записей: 2 ^ 54 Вероятность столкновения: 1e-16
- Кол-во записей: 2 ^ 64 Вероятность столкновения: 1e-10
- Кол-во записей: 2 ^ 71 Вероятность столкновения: 2e-06
- Кол-во записей: 2 ^ 76 Вероятность столкновения: 2e-03
- Кол-во записей: 2 ^ 80 Вероятность столкновения: 0,39
- Кол-во записей: 2 ^ 82 Вероятность столкновения: > 0,99
Примеры интерпретации:
- Если у вас меньше 2^54 (18014398509481984) записей, вы можете быть уверены, как никто другой, что у вас не будет столкновения.
- Если вам каким- то образом удастся получить 2^76 (75,557,863,725,914,323,419,136) записей, вы можете быть уверены только в некоторой степени (вероятность столкновения составляет 2 из миллиона!)
Теперь вы можете решить для себя, достаточно ли для вас вероятности.