3 ms·
Deduplication is the kind of application where CRC is a decent approach and CRC has no resistance to attack whatsoever. SHA1 adds the advantage of lower natural
by jcrawfordor 4y ago
Deduplication is the kind of application where CRC is a decent approach and CRC has no resistance to attack whatsoever. SHA1 adds the advantage of lower natural collision probability while still being extremely fast. It's important to understand that not all applications of hashing are cryptographic or security applications, but that the high degree of optimization put into cryptographic algorithms often makes them a convenient choice in these situations.
These types of applications are usually using a cryptographic hash as one of a set of comparison functions that often start with file size as an optimization and might even include perceptual methods that are intentionally likely to produce collisions. Some will perform a byte-by-byte comparison as a final test, although just from a performance perspective this probably isn't worth the marginal improvement even for hash functions in which collisions are known to occur but vanishingly rare in organic data sets (this would include for example MD5 or even CRC at long bit lengths, but the lack of mixing in CRC makes organic collisions much more common with structured data).
SHA2 is significantly slower than SHA1 on many real platforms, so given that intentional collisions are not really part of the problem space few users would opt for the "upgrade" to SHA2. SHA1 itself isn't really a great choice because there are faster options with similar resistance to accidental collisions and worse resistance to intentional ones, but they're a lot less commonly known than the major cryptographic algorithms. Much of the literature on them is in the context of data structures and caching so the bit-lengths tend to be relatively small in that more collision-tolerant application and it's not always super clear how well they will perform at longer bit lengths (when capable).
Another way to consider this is from a threat modeling perspective: in a common file deduplication operation, when files come from non-trusted sources, someone might be able to exploit a second-preimage attack to generate a file that the deduplication tool will errantly consider a duplicate with another file, possibly resulting in one of the two being deleted if the tool takes automatic action. SHA1 actually remains highly resistant to preimage and second preimage attacks, so it's not likely that this is even feasible. SHA1 does have known collision attacks but these are unlikely to have any ramifications on a file deduplication system since both files would have to be generated by the adversary - that is, they can't modify the organic data set that they did not produce. I'm sure you could come up with an attack scenario that's feasible with SHA1 but I don't think it's one that would occur in reality. In any case, these types of tools are not generally being presented as resistant to malicious inputs.
If you're working in this problem space, a good thing to consider is hashing only subsets of the file contents, from multiple offsets to avoid collisions induced by structured parts of the format. This avoids the need to read in the entire file for the initial hash-matching heuristic. Some commercial tools initially perform comparisons on only the beginning of the file (e.g. first MB) but for some types of files this is going to be a lot more collision prone than if you incorporate samples from regular intervals, e.g. skipping over every so many storage blocks.