What's the likelihood of a collision if I use a hash to detect data change?

Question

I have a set of data that I want to sync, and instead of sending an entire set of data, I wanted to use a hash.

It is basically a list of GUIDs with either "true" or "false".

eaa54efe-2b10-4d3b-b9c2-30d2bcca7e06 : true
94297d72-573a-4e6c-a45e-37a390750b64 : false
36d1acbd-b2dc-4a90-a7be-fb65b63639a5 : true

I plan to generate a hash of the entire list so that I can send much fewer data to sync than the entire data set.

Should I ever be concerned that a specific change of true/false will happen to randomly result in a collision and become "undetected" or is that really not going to happen?

I don't really understand the math and proofs behind the hashes, but I also understand that good hashes are supposed to be designed against trivial collision.

Note: the main goal is just data comparison. There is no encryption of the data because they're useless data without the meaning behind the GUIDs. This is, literally, live data I just posted.

Answer 1

When syncing two data set over the internet one can basically two choices;

• send all the data and compare: This is slow but complete.
• send the hash of the data: This is very fast but there is a tiny-tiny-tiny change of a collision is almost zero. If you are that lucky, you probably become reach or hit by an asteroid. This is very common on Linux's CD/DVD image downloads.

In your case, you want to just send a hash of one huge list. If you fear that the almost zero ( $2/2^{256}$ for a 256-bit bash function) is bothering you, you can decrease the change below almost zero by taking another hash function to have two hashes, though not necessary.

and, yes, Cryptographical hash functions are designed to have collision resistance, however, over the time one might find better attacks than generic collision attack like SHA-1 and it has already removed from the standard. This attack, actually, searching for different inputs, where the data structure enables, to find a collision. And the generic collision attack is $2^{80}$ on SHA-1, that is low in today's standards if you consider that Bitcoin miners reached $\approx 2^{92}$ SHA-256 hashes per year in 06 Agust 2019. Reaching $2^{128}$ way beyond classical computing.

Stick to a good hash function, SHA-256, SHA-512, SHA3, Blake2.

Answer 2

As was said already in other answers, using a modern, non-deprecated hash (see here for a list of most common hashes with the information of which ones should not be used any more), the chance of collisions are negligible and you need not worry about it: you can rely on the fact that a change in the data will cause very different hash values.

However there are things you must be careful about, for instance: how are you going to transport the hash from source to destination? If you send the hash via the same way you send the data, and you are afraid that someone modifies the data in-flight, then that same person could also modify the hash to be the hash of the modified data. One solution is to find a way to securely transfer a key from source to destination (for instance by SSHing into each), and then using a MAC which the adversary won't be able to re-compute for the modified data.

To give more precise directions we would need more details from you, in particular, how and where do you think an adversary may modify your data: is it just during network transfer? Is it on disk?

Finally, it looks like you are trying to roll your own crypto here (search the Web about rolling your own crypto) if this is just for your own curiosity or training or research this is fine, but if you plan to protect real value with this you should use tools where all the cryptographic decisions are already made for you.

Answer 3

The others are talking about hash collisions in an adversarial context, in which someone else is motivated to find a collision.

This raises the first question you should be asking: what is your threat model?

If you are talking about no adversary, you can do this and should not worry. If your program was running on every pc on Earth and syncing over a 256 bit hash with every other pc every second, your chance of having even a single collision within a hundred years is 1 in 100000000000000000000000000000000000000000000000000. That works for any hash as long as it is evenly distributed: it doesn't even need to be a cryptographic hash.

Do note that this mechanism can only tell you that nothing has changed. You would need to send the whole list if you got a hash mismatch.

If you did have an adversary who was for some reason trying to cause an undetected divergence, then you would have to think more carefully.