Когда хэши сталкиваются?

Question

Я понимаю, что в соответствии с принципом почтового ящика, если количество элементов превышает количество контейнеров, то по крайней мере в одном контейнере будет более одного элемента. Имеет ли значение, какой контейнер это будет? Как это относится к хешам MD5, SHA1, SHA2?

Answer 1

Нет, не важно, какой это контейнер, и на самом деле это не так важно для криптографических хэшей; намного более важным является парадокс дня рождения , который говорит о том, что вам нужно в среднем хешировать sqrt(numberNeededByPigeonHolePrincipal) значений, прежде чем обнаруживать столкновение.

Таким образом, хеш должен быть достаточно большим, чтобы квадратный корень пространства поиска был слишком велик для грубой силы. Квадратный корень пространства поиска для SHA1 равен 2 ⁸⁰ , и по состоянию на март 2012 года не было найдено двух значений с одним и тем же хешем SHA1 (хотя я предсказываю, что это произойдет в пределах в следующем году или два ..); то же самое с SHA2, семейством хэшей, у которых все пространство поиска еще больше. Хотя MD5 некоторое время был сломан .

Answer 2

Если у вас есть больше элементов для хеширования, чем у вас есть слоты, то у вас будут хеш-коллизии. Но если у вас плохой алгоритм хеширования, вы увидите коллизии, даже когда соотношение предметов / слотов очень мало. Хороший алгоритм хэширования (включая большинство тех, которые вы увидите в дикой природе) будет пытаться распределить результирующие хэши по всему выходному пространству настолько равномерно, насколько это возможно, и таким образом минимизировать коллизии.

Обратите внимание, что коллизия хешей - это не конец света. Например, при использовании в хеш-таблице это просто означает, что в слоте хранится более одного элемента, и код таблицы должен будет пройти немного больше, чтобы найти или добавить целевой элемент, что немного увеличивает время поиска.

Вы увидите, что люди называют MD5 «сломанным» алгоритмом хеширования, хотя на самом деле его просто нельзя использовать в качестве криптографического хэша. Это будет лучше, чем то, что вы создадите сами.

Answer 3

Смысл хэш-функции заключается в случайном распределении элементов по контейнерам. Для любой хорошей хэш-функции не важно / не должно иметь значения, какой контейнер какой, поскольку они должны быть неразличимы.

Это не относится к реализациям "идеального хэша", которые пытаются добиться большего успеха, чем случайное распределение - в отличие от алгоритмов, которые вы упомянули.

Как упоминал Майкл, столкновения происходят ДОЛГО, прежде чем количество предметов равно слотам. У вас должна быть изящная обработка коллизий (или идеальный хеш), если вы хотите обработать парадокс дня рождения .

Answer 4

В зависимости от вашего приложения, криптографические хеши, такие как MDA, SHA1 / 2 и т. Д., Могут не быть идеальным выбором, именно потому, что они выглядят как совершенно случайные, что дает вам коллизии, как предсказано парадоксом дня рождения. Традиционно, одна из причин использования простых хэшей, основанных на операции с остатками, заключается в том, что ключи должны быть серийными номерами или аналогичными, так что операция с остатками будет выдерживать меньше коллизий, чем ожидалось в случайном порядке. Например. если ключи представляют собой целые числа 1..1000, вы можете вообще не иметь коллизий в контейнере размером 1009, если ваша хеш-функция является модом ключа 1009. Люди иногда настраивают системы вручную, тщательно выбирая размер контейнера и хэш-функцию, чтобы добиться равномерного разделения.

Конечно, если вам нужно беспокоиться о том, что люди злонамеренно выбирают ключи, которые вызовут у вас затруднения, или о том, что вышестоящая система отправляет вам очень предвзятые ключи (потому что, например, она имеет свою собственную хеш-таблицу и решает обработать все ключи, которые хэшируют по X однажды). Вы можете использовать хэш, основанный на криптографической хэш-функции с ключом, чтобы защититься от этого.

Answer 5

Я думаю, для какого приложения вы используете хеш-функцию, это важное различие. Например, частые столкновения в контейнерах хэширования могут ухудшить производительность. Частые столкновения в криптографии будут иметь гораздо более разрушительные последствия (см .: криптографическая хеш-функция в Википедии ).

Столкновение происходит относительно легко, даже с «приличным» алгоритмом хеширования. Например, в Java

String s = new String(new char[size]);

всегда хэшируется в 0. То есть все строки, содержащие только \0 хэшируются в 0 в Java.

---

Что касается «имеет ли значение, каким контейнером он будет?», Опять же, это зависит от приложения. Вы можете создавать хеш-функции, которые бы хэшировали «похожие» объекты с близлежащими значениями. Это полезно, например, если вы хотите искать похожие объекты. Просто хэш их всех и посмотреть, где они падают. В этом случае, столкновения или почти столкновения желательны, потому что это группирует объекты, которые похожи.

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