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

Question

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

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

Answer 1

Если вы предполагаете, что 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 столкновения. Действительно не стоит беспокоиться.

Answer 2

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

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

См. Также Стучать по гвоздю: старая обувь или стеклянная бутылка? !

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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

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

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

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

Answer 6

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

Answer 7

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

Answer 8

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

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

Answer 9

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

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

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

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

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

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

Answer 10

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

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