Identifying identical files without reading them completely 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:


feed file size (as byte array) into sha256
read chunk at the beginning of file and feed into sha256
read chunk at middle of file (file size/2) and feed into sha256
read chunk at end of file and feed into sha256
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.
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.)