Hash Collision – каковы шансы?

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

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

Если вы предполагаете, что SHA-1 делает хорошую работу, вы можете сделать вывод, что существует вероятность 1 из 2 ^ 160, что два заданных сообщения имеют одинаковый hash (поскольку SHA-1 создает 160-битный хеш).

2 ^ 160 – смехотворно большое число. Это примерно 10 ^ 48. Даже если у вас есть миллион записей в вашей базе данных, это все еще вероятность того, что новая запись будет иметь один и тот же хеш.

SHA-1 оказался довольно хорошим, поэтому я не думаю, что вам нужно беспокоиться о столкновениях вообще.

В качестве дополнительной заметки используйте функцию raw_output PHP при использовании SHA-1, так как это приведет к более короткой строке и, следовательно, сделает операции с базой данных немного быстрее.

РЕДАКТИРОВАТЬ: Для решения парадокса дня рождения firebase database с 10 18 (миллион миллионов миллионов) записей имеет вероятность около 1 из 0,0000000000003 столкновения. На самом деле не стоит беспокоиться.

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

Это позволяет использовать разумные значения при разговоре с БД без какого-либо столкновения , большой безопасности при разговоре с клиентом и уменьшает вероятность попадания на ежедневный WTF примерно на 2 ^ 160.

См. Также Pounding A Nail: старая обувь или стеклянная бутылка? !

почему бы не сделать что-то, что гарантирует отсутствие столкновений, а также гарантирует, что никто не сможет изменить параметр GET, чтобы просмотреть то, что им не нужно: используя соль, объедините идентификатор и его hash.

 $salt = "salty"; $key = sha1($salt . $id) . "-" . $id; // 0c9ab85f8f9670a5ef2ac76beae296f47427a60a-5 

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

Если вы используете числовые идентификаторы в качестве входных данных, то шансы практически равны нулю, когда SHA-1 столкнется.

Если ID является единственным входным сигналом, то SHA-1, похоже, является довольно избыточным, создавая 160-битный хеш из 32-разрядного целого числа. Я предпочел бы использовать модульное возведение в степень, например, выбрать большой (32-разрядный) простой p, вычислить модульный генератор g этой группы, а затем использовать g ^ id. Это будет гарантировано без конфликтов и даст только 32-битные «hashи».

SHA-1 производит 160-битный дайджест. Поэтому вы в безопасности, если у вас меньше 2 ^ (160/2) записей. Разделение на 2 связано с парадоксальным днем ​​рождения .

Из первых принципов:

SHA-1 производит 160-битный дайджест. Предполагая, что он использует все бит-пространство равномерно (что, по-видимому, было предназначено для этого), это всего лишь вероятность 2 ^ -160 на каждой вставке, что вы получите столкновение.

Поэтому для каждой вставки должно быть безопасно предположить, что нет столкновения, и справиться с ошибкой, если она есть.

Это не означает, что вы можете полностью игнорировать вероятность столкновения.

Парадокс дня рождения предполагает вероятность того, что по крайней мере одно столкновение в вашей базе данных будет выше, чем вы предполагали, из-за возможных столкновений O (N ^ 2).

Если вам нужно обфускать некоторые данные в вашем URL-адресе, чтобы скрыть данные, вы делаете что-то неправильно.

Задайте вопрос, что будет стоить вам, если произойдет столкновение. Если это бесплатный сайт. Если вы управляете бизнесом для зарабатывания денег, а переоценка обойдется вам в миллион долларов, тогда я подумаю еще раз.

Я думаю, вы идете по этому неправильно.
Я думаю, вам нужно сохранить уникальный идентификатор, но вы хотите убедиться, что пользователи не могут вручную изменить ID.

Один из способов сделать это – поместить идентификатор и hash идентификатора (с некоторыми дополнительными данными) в ссылку.

Например: (мой PHP ржавый, так что общий алгоритм будет 🙂

 id = 5; hash = hash("My Private String " + id) link = "http://mySite.com/resource?id=" + id + "&hash=" + hash 

Затем, когда вы получаете запрос, просто подтвердите, что вы можете восстановить hash из ID. Это оставляет вас открытой для атаки, чтобы выработать «Моя приватная строка», но это будет довольно сложно вычислить, и вы всегда можете добавить что-то еще уникальное, недоступное пользователю (например, идентификатор сеанса).

Существует очень простое правило выяснить, будет ли какой-либо алгоритм хеширования иметь коллизии или нет. Если выходной диапазон алгоритма является конечным числом, рано или поздно у него будет столкновение.

Хотя SHA1 имеет очень большой диапазон 2 х 160 hash-возможностей, его все еще конечное число. Однако входы, которые могут быть переданы на эту функцию, буквально бесконечны. Учитывая достаточно большой набор входных данных, столкновения неизбежно произойдут.

Другие комментарии затронули вас по вероятностям, однако, если вы посмотрите на это прагматично, вы можете получить определенный ответ для себя.

Вы сами сказали, что собираетесь собирать свои последовательные идентификаторы. Было бы легко закодировать тестовый пример. Итерация через ~ 100 000 000 идентификаторов и проверка на наличие столкновений. Это не займет много времени. С другой стороны, у вас может закончиться четверть пути.

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

Стефан Эссер написал хорошую статью по этой теме.

  • Каковы рабочие характеристики sqlite с очень большими файлами базы данных?
  • Когда мы должны использовать PreparedStatement вместо Statement?
  • дизайн схемы базы данных streamов сообщений
  • Автоматически ли индексирует столбцы внешнего ключа MySQL?
  • HQL присоединился к запросу, чтобы получить большое количество связей
  • Sql - косвенный внешний ключ
  • Каков наилучший способ настройки паролей, не имея их слишком легко доступным для обычного читателя?
  • Что такое нормализация (или нормализация)?
  • Нулевые столбцы занимают дополнительное пространство в PostgreSQL?
  • T-SQL Pivot? Возможность создания столбцов таблицы из значений строк
  • Войдите в базу данных, используя log4j
  • Давайте будем гением компьютера.