それらを比較せずに同じファイルを発見する方法は？

Question

私はユーザーがコンテンツをアップロードできるサイトを構築しています。いつも私は世界的な優位性を目指しているので、同じファイルを2回保存しないでください。 たとえば、ユーザーが同じファイルを2回アップロードしようとした場合（名前を変更したり、過去にしたことをしたものについて忘れたりすることで）。

現在のアプローチは、各アップロードされたファイルを追跡するデータベースに各ファイルに関する次の情報を格納することがあります。

• バイト数
• MD5ファイルの内容の合計
• sha1ファイルの内容の合計

  、それらの3列の一意のインデックス。 の2つのハッシュを使用すると、誤検体のリスクが最小限に抑えられます。

  だから、私の質問は本当にあります。

  または：似たような（国連）複雑さのより賢い方法はありますか？

  （確率がファイルサイズに依存できることを理解しています）

  ありがとう！

Answer 1

The probability of two real-world files of the same size having the same SHA1 hash is zero for all practical purposes. Some weaknesses in SHA1 have been found, but creating a file from a SHA1 hash and a size (1) is incredibly expensive in terms of computing power and (2) produces either garbage or the original file.

Adding MD5 to the mix is total overkill. If you don't trust SHA-1, then a better option is to switch to SHA-2.

If you're really paranoid, try comparing files with identical (size, SHA1) signatures. That will, however, have to read both the files entirely if they are equal.

Answer 2

I believe storing MD5 and SHA1 hashes is adding unnecessary complexity and not good design. I would say storing the tuple of (SHA1, file size) would be by far good enough. Especially if you're starting a new community site, I'd safely use that solution and only create something more clever once it becomes a problem. As the saying goes, premature optimization is the root of all evil, and it's arguable if it'll be `optimizing'.

edit: I did not quantify the odds of you getting a MD5+SHA1 collision. I'd say it's zero. By a crude, back of the envelope calculation, the odds of two different files of arbitrary file sizes having identical (SHA1,MD5) tuple is 2^-288, which is zero as far as I'm concerned. Having to require identical file size reduces that even further.

Answer 3

You can use Broders implementation of the Rabin fingerprinting algorithm. It is faster to compute than sha1 and md5 and it is proven to be collision resistant. However, it is not considered to be safe against malicious attacks, it is possible fot someone to purposefuly alter the file in question sithout changing the fingerprint itself. If you just want to check the similarity of files, it is s pretty good solution.

C# implementation, not tested:

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