서로 비교하지 않고도 동일한 파일을 서로 비교하는 방법을 찾는 방법은 무엇입니까?

Question

사용자가 콘텐츠를 업로드 할 수있는 사이트를 구축하고 있습니다. 항상 세계 지배력을 목표로하는 것처럼 나는 동일한 파일을 두 번 저장하지 않으려고합니다. 예를 들어 사용자가 동일한 파일을 두 번 두 번 업로드하려고 시도하면 (과거에서 수행 한 것에 대해 잊어 버리거나 단순히 잊어 버림)

내 현재 접근 방식은 각 파일에 대한 다음 정보를 추적하는 데이터베이스를 각 파일에 대한 다음 정보를 추적하는 것입니다.

• 파일 크기 바이트
• MD5 파일 내용의 합계
• sha1 파일 내용의 합계

  및 그 세 열의 고유 한 색인. 두 해시를 최소화 의 위험을 최소화하십시오.

  그래서, 내 질문은 정말로 동일한 크기의 동일한 크기의 두 가지 ( "실제") 파일의 확률이 무엇입니까? sha1 해시는

  또는 : (un) 복잡성의 더 똑똑한 방법이 있습니까?

  (확률이 파일 크기에 의존 할 수 있음)

  감사합니다!

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/