Каким образом можно гарантировать уникальность хэш-строки для определенного файла?

Question

[happycodecom]

При разработке сервиса файл-хостинга встал вопрос быстрого поиска дубликатов.
У каждого алгоритма хэширования есть вероятность коллизий из-за ограничения длинны генерируемой строки.
Сравнивать содержимое файлов затратно при больших объемах, да и разные файлы могут быть с одинаковыми sha1/md5 суммами.

Может генерировать длинную строку из двух/трех и более алгоритмов?

Как лучше?

Answer 1

[MiiNiPaa]

У каждого алгоритма хэширования есть вероятность коллизий из-за ограничения длинны генерируемой строки.

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

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

На практике достаточно хранить достаточно длинный хэш (Даже SHA1 пойдёт) плюс, возможно, длину файла для предварительной проверки на уникальность (до хеширования)

Comments

[Владимир Мартьянов]

Для MD5 коллизии ищутся за минуты. Длину хранить, я полагаю, не надо, она подмешивается к хэшу при финализации.

[MiiNiPaa]

Я и не предлагал использовать MD5. Хотя даже в этом случае пользы от нахождения коллизий злоумышленнику может быть только одна: не дать в будущем загрузить какой-то конкретный файл.

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

[happycodecom]

Спасибо за ответ. Думаю остановлюсь на использовании длинного хэша из md5 и SHA1, как и планировал.

Answer 2

[Владимир Мартьянов]

SHA1 достаточно уникальна. Коллизии у MD5 ищутся за минуты, про SHA1 и тем более SHA512 такого не слышал.

Comments

[happycodecom]

Мне кажется вероятность коллизий при использовании как минимум двух алгоритмов для сравнения снижает шансы почти до нуля.

Нашел на хабре интересную статью на эту тему: habrahabr.ru/post/113127

[Владимир Мартьянов]

happycodecom: Два - тоже вариант, конечно :-)