Как найти идентичные файлы, не сравнивая их друг с другом?

Question

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

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

• размер файла в байтах
• MD5 сумма содержимого файла
• SHA1 сумма содержимого файла

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

Итак, мой вопрос на самом деле: какова вероятность того, что два разных ("реальных") файла одинакового размера будут иметь одинаковые хэши MD5 и SHA1?

Или: Есть ли более умный метод аналогичной (не) сложности?

(я понимаю, что вероятность может зависеть от размера файла).

Спасибо!

Answer 1

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

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

Если вы действительно параноик, попробуйте сравнить файлы с одинаковыми (размер, SHA1) подписи.Это, однако, должно прочитать оба файла полностью, если они равны равны.

Answer 2

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

edit: я не определял шансы на то, что вы получите столкновение MD5 + SHA1.Я бы сказал, что это ноль.Грубо говоря, в расчете на конверт шансы двух разных файлов произвольного размера с одинаковым (SHA1, MD5) кортежем составляют 2 ^ -288, что, на мой взгляд, равно нулю.Необходимость идентичного размера файла уменьшает это еще больше.

Answer 3

Вы можете использовать реализацию Broders алгоритма дактилоскопии Рабина.Он быстрее вычисляется, чем sha1 и md5, и доказано, что он устойчив к столкновениям.Тем не менее, он не считается безопасным от злонамеренных атак, возможно, что кто-то намеренно изменяет рассматриваемый файл без изменения самого отпечатка пальца.Если вы просто хотите проверить сходство файлов, это довольно хорошее решение.

Реализация на C #, не тестировалась:

http://www.developpez.net/forums/d863959/dotnet/general-dotnet/contribuez/algorithm-rabin-fingerprint/