DVC is vulnerable to MD5 collisions

[aparpara]

As DVC cache entirely relies on MD5 hash sums, it is vulnerable to MD5 collisions. I.e. if 2 different files have the same MD5, they are considered as identical. I understand the probability of this event is about 2^-64, but according to Murphy's law, sooner or later it should happen. And IMHO this should be explicitly mentioned in DVC documentation so that users can be aware of this possibility. But unfortunately I found no such mentions.

To reproduce the collision one may use an example from Wikipedia:

1. Create an empty folder
2. Init DVC:
   dvc init --no-scm
3. Make sure DVC uses links:
   dvc config cache.type reflink,hardlink,symlink
4. Add test files. In Python this will be

with open('md5coll-1.bin', 'wb') as f: 
    f.write(codecs.decode(
        'd131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89'
        '55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b'
        'd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0'
        'e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70', 'hex'))
with open('md5coll-2.bin', 'wb') as f: 
    f.write(codecs.decode(
        'd131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89'
        '55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b'
        'd8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0'
        'e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70', 'hex'))

5. Make sure the files are different.
6. Add them to DVC:
   dvc add md5coll-1.bin md5coll-2.bin
7. See now the files are identical, because DVC has put md5coll-1.bin into the cache, and replaced both md5coll-1.bin and md5coll-2.bin with links to the same cached file.

[efiop]

Hi @aparpara Did you experience hash collision while using dvc in real world?

[aparpara]

With all due respect it is a perfectly reasonable argument. The probability is small, but it is not so small to disregard the corresponding risk. And a user should be aware of all known risks in advance. The way you compute MD5 (with dos2unix or not) is completely irrelevant here, because it doesn't influence the collision probability. If you use a larger checksum, it will certainly reduce the probability, but still not reduce it to zero. So there should be a caveat anyway.

[efiop]

I understand your concerns. If you are keen, please feel free to submit a docs PR for it. Otherwise, we might get to it once we adjust our hashing algorithm. Might be worth creating an issue in https://github.com/iterative/dvc.org for that.

Probably the best place to put the note about md5 is somewhere in the user guide (don't see an existing page to add it to, so will probably need to create a new one there).

[apethree]

I think one of the more important reason is the speed as DVC is designed for large files speed is very important. SHA1 is much much slower that MD5 and I think one good alternative would be to use xxhash(128) instead it reduces collision chances and also improves the speed. So we will get best of the both worlds. Let me know if you need my help implementing that.

[apethree]

Just glanced at the source code, it's gonna be a lot of work to refactor and change/support multiple hash functions.

[Erotemic]

+1 for xxhash (or blake3). I'm eagerly waiting for adjustable hash algorithms.