Насколько вы можете усечь хэш SHA1 и быть достаточно уверенным в том, что у вас уникальный идентификатор?

Question

Я создаю приложение, которое хранит документы и присваивает каждому UID на основе дайджеста SHA1 нескольких вещей, включая метку времени.В дайджесте много символов, и я хочу, чтобы пользователи могли идентифицировать документы по первым x символам полного дайджеста.Какое значение x является хорошим, если количество документов может составлять около 10–100 тыс.?

Answer 1

Адаптация формул на Википедия по проблеме «День рождения», вы можете аппроксимировать вероятность столкновения как e^(-n^2/(2^(b+1))), где n количество документов и b это количество битов. Построение графика этой формулы с n = 100 000, похоже, вам понадобится как минимум b > 45.Я бы больше склонялся к 64, чтобы получилось красивое и круглое число.Тем не менее, у вас есть план борьбы с коллизиями, если они происходят (может быть, слегка изменить временную метку или добавить nonce?)

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

Answer 2

Будьте осторожны с усечением, так как нет никаких доказательств того, что меньший хэш безопасен. Смотрите Келси http://csrc.nist.gov/groups/st/hash/documents/kelsey_truncation.pdf. Анкет Келси дает эвристическим аргументам, в которых говорится то же («связанные с хэш -выводами» и «близкие столкновения»). Бихам/Чен предлагает примеры почти столкновений; и Кнудсен демонстрирует усеченные дифференциалы.

В конце концов, вы, вероятно, хотите подавать свои данные в HMAC с Усеченный размер (размер также расщепляется HMAC), а затем использует усеченный HMAC.

Answer 3

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

Answer 4

Это обобщение из Проблема дня рождения. Анкет В вас случае не это количество документов, и вместо постоянного 365 у вас будет количество возможностей, которые дает вам отсечка (так что для k биты это 2^k).

Конечно, точный расчет не может быть и речи, но вы можете использовать приближение.

Answer 5

Ну, вот, возможно, слишком упрощенный ответ ..

Если с полным SHA1 вы получите около 1 на 2^160 шанс на столкновение, то, усекнув один персонаж, вы увеличиваете шансы на столкновение на 16 (все возможные значения усеченного символа) ... который составляет 2^4 .. Итак,, Если вы усекаете x символов, вы получаете 1 в 2^(160 - 4*x) шансы на столкновение .. верно?