Identifying identical files without reading them completely

Question

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.

Answer 1

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.)

Answer 2

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.

Answer 3

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.