2
$\begingroup$

Imagine the following situation:

  • there are many "big" files (100Gb+) lying on 2 different remote servers
  • you have no direct access to these files
  • you can only read a small amount of each file (e.g. 10Mb) as well as it's general information (e.g. file size)
  • files can have different names and paths but same content/size
  • security is no concern - nobody will try to create fake data to force collisions
  • file contents are solely audio and video files in all kinds of different formats

What's the best way to tell if there are duplicate files between these 2 servers (with a certain confidence) with the data that's available?

Goals:

  • find file duplicates
  • the resulting hash has to be the same for the same filesize + contents everytime
  • create a database of hashes (?) to compare newly added files with already existing for duplication

My naive approach looks like this right now:

  1. feed file size (as byte array) into sha256
  2. read chunk at the beginning of file and feed into sha256
  3. read chunk at middle of file (file size/2) and feed into sha256
  4. read chunk at end of file and feed into sha256
  5. use resulting hash for comparisons

The goal is not to 100% identify/verify those files but being able to tell with the highest possible confidence (provided the restrictions) that file1 on server1 is pretty likely file2 on server2 while providing good collision resistance.

$\endgroup$
8
  • $\begingroup$ Why feed it through a hash function at all? If you can read the files plaintext then running through the hash would merely add unnecessary complexity when you can just directly compare chunks of the file. Further, assuming two files are of the same size (if they weren't you would know they are different), it doesn't matter which pieces of each file you decide to compare: if you make the assumption that the contents of all files are random for the purpose of the comparison (ie you know all sections need not be the same), than it doesn't matter how you decide to compare, it is all the same. $\endgroup$
    – user918212
    Feb 28, 2020 at 0:04
  • 1
    $\begingroup$ while providing good collision resistance - you are going to read 0.0001 part of the file (10 MB out of 100 GB) and you are talking about collision resistance? $\endgroup$
    – mentallurg
    Feb 28, 2020 at 2:53
  • $\begingroup$ The question is too imprecise. At least, make the goal " tell if there are duplicate files between these 2 servers" precise. Are files with identical content but non-matching paths considered identical or different for the purpose of this determination? Can we assume we have access to all file names/path and their length? In crypto, we tend to assume an adversary trying to foil us, is that the correct (adversarial) model? We need some goal regarding desired residual probabilities of answering YES when truth is NO, and vice versa (both are possible). $\endgroup$
    – fgrieu
    Feb 28, 2020 at 3:05
  • $\begingroup$ thanks for the criticism, I tried to clarify the question. @Grassi: I did use a hash to be able to build a database of the files for later comparison as well. (wasn't clear in the original question) $\endgroup$
    – scable
    Feb 28, 2020 at 7:37
  • $\begingroup$ @mentallurg: yes I do, those are the restrictions. it just needs to be good enough $\endgroup$
    – scable
    Feb 28, 2020 at 7:40

3 Answers 3

2
$\begingroup$

It will never be secure to hash just part of a file. It will always be trivial to generate two distinct files which produce the same hash. (Just look for which parts of the file the lazy hash doesn't touch and modify those sections.)

If you don't need security, then you might be able to come up with some scheme that works most of the time for "natural" (not maliciously crafted) files.

One could hash the first $n$ kilobytes, prefixed with the file size, to generate a PRNG seed. Then you can use the chunk-reading strategy using the RNG to choose random starting positions for each chunk. The chunk size doesn't matter, other than for performance.

Just like how there is no one ultimate file compression algorithm which works for any kind of file, there isn't going to be one universal algorithm for the type of application you describe.

(Any compression algorithm will work well with some file contents and poorly, inflating the file size even, for other files. You get the best results by choosing an algorithm you know will be well suited to the type of data you're trying to compress.)

If you knew your target file formats, then you could design a lazy hash meant to specifically work for that format. For example, you could start reading from a position other than zero if you knew all files shared a common header or that files tended to start with the same boilerplate text.


Actually, store multiple hashes. One of the first 10kb of a file, one of the last 10kb, and one of a random sample of chunks. Check the start and end of the file for differences first so you can bail early by detecting files that contain different beginnings/ends. Fallback on the slower one if they both match. (Or just use one or two partial checksums along with a fallback to a strong hash of the full file, as I assume most software like this does.)


If you're interested in deduplicated file backups, look into Tarsnap.

Files are stored as a sequence of chunk hashes instead of as a sequence of bytes. Chunks values are also stored, but the hashes are used are used as keys in a lookup table to index those chunks. This adds overhead for random data, but allows one to store only one copy of each unique chunk even if it is part of multiple files or appears more than once in the same file.

If you want to use such a system, then just use Tarsnap or something like it. It's a big wheel to reinvent, so you're probably safer using a mature open source project. (I don't use it personally, though. And it's been a long time since I read about it.)

$\endgroup$
1
  • $\begingroup$ I added some clarifications to the question. Security is not a concern here. I really like the idea with the PRNG seed based on first chunk + filesize to generate "random" chunk positions and will play around with that a bit. $\endgroup$
    – scable
    Feb 28, 2020 at 7:47
1
$\begingroup$

1) Selective comparison

A) Compare size: If these audio and video files are not in some raw format, but compressed (e.g. mp3, mpeg), then the probability that two audio (or video) sequences produce files of the same lengths is very slow. That's why first check file size. If it is different, then the files are obviously different.

B) Compare contents selectively: If some files have the same size, compare fragments of these files at different random positions. Generate random position X, read e.g. 1000 bytes at this position X in both files, compare the constants. If the content is the same, continue: generate a new random position, read fragment, compare.

2) Remote command

It is not clear how read the files. If by reading you mean transferring files via network from server to your computer, then there can be one more solution. If you have SSH access to the both servers, then you don't have to transfer files via network. You can obtain hashes for the whole files remotely. Use command like following:

ssh user@server1 sha512 /path/to/file

This means that the server1 will read the file *without network usage (locally to this server) and will return you only the hash. This can take however more time. Because sha512 can give 0,5 - 1 GB/s. For 100 GB file hash calculation will take thus ~100s ~= 2 min. You decide if it is slow for you or not. If you can accept the time needed for this, you will get the very high probability that the files are identical.

If it is too slow for you, still you can put some utility that reads selected pieces of the file (locally to the server 1 or to the server 2) and calculates hashes. And then you can call it in the same way per SSH, so that only hash will be sent via network.

$\endgroup$
2
  • $\begingroup$ With (2) you can substitute another hash function. You can use Blake3, which is faster in its single-thread form but also can benefit from however many cores you have available. $\endgroup$ Feb 29, 2020 at 0:38
  • $\begingroup$ @FutureSecurity: Sure, BLAKE would be faster. I just wanted to show an example of what can work on the most Linux systems directly, without installing anything else, so that the author can test it immediately. $\endgroup$
    – mentallurg
    Feb 29, 2020 at 23:42
0
$\begingroup$

Besides the observation by Future Security: "It will never be secure to hash just part of a file. It will always be trivial to generate two distinct files which produce the same hash"

It would also be trivial to have two video files that for any viewer are unnoticeably and effectively the same, yet they would completely fool any hashing strategy like the ones described here. I mean, for any 100 GB+ big video file, just flip some bits at beginning and end, and some bit in the middle of the file. Or if video editing, just remove a tiny fraction of a second from the beginning or the end of the video, save the rest in the other server. Files are technically different but for all intent and purposes, the video contents are the same. Neither hashing strategies like beginning + somewhere middle + end, nor even a complete file hashing, will be able to spot this trivial "partial" duplication though.

$\endgroup$
1
  • $\begingroup$ I agree with the most part. But the following statement is not correct: "nor even a complete file hashing, will be able to spot". Hash will change with very high probability. It is obvious that many hash collisions are possible. But modifying a file to produce given hash is very hard computational task. That's why changing even a single bit changes the hash. $\endgroup$
    – mentallurg
    Mar 6, 2020 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.