How do I assess the hash collision probability?

Question

I'm developing a back-end application for a search system. The search system copies files to a temporary directory and gives them random names. Then it passes the temporary files' names to my application. My application must process each file within a limited period of time, otherwise it is shut down - that's a watchdog-like security measure. Processing files is likely to take long so I need to design the application capable of handling this scenario. If my application gets shut down next time the search system wants to index the same file it will likely give it a different temporary name.

The obvious solution is to provide an intermediate layer between the search system and the backend. It will queue the request to the backend and wait for the result to arrive. If the request times out in the intermediate layer - no problem, the backend will continue working, only the intermediate layer is restarted and it can retrieve the result from the backend when the request is later repeated by the search system.

The problem is how to identify the files. Their names change randomly. I intend to use a hash function like MD5 to hash the file contents. I'm well aware of the birthday paradox and used an estimation from the linked article to compute the probability. If I assume I have no more than 100 000 files the probability of two files having the same MD5 (128 bit) is about 1,47x10^-29.

Should I care of such collision probability or just assume that equal hash values mean equal file contents?

Egwin

is this a hash on content of filename? – Behre

The content is hashed. There's no point in hashing the filenames - they change randomly. – Egwin

If you're worried about collisions, consider both the file size and the hash. – Lanford

Answer 1

Equal hash means equal file, unless someone malicious is messing around with your files and injecting collisions. (this could be the case if they are downloading stuff from the internet) If that is the case go for a SHA2 based function.

There are no accidental MD5 collisions, 1,47x10^-29 is a really really really small number.

To overcome the issue of rehashing big files I would have a 3 phased identity scheme.

1. Filesize alone
2. Filesize + a hash of 64K * 4 in different positions in the file
3. A full hash

So if you see a file with a new size you know for certain you do not have a duplicate. And so on.

Behre

@Egwin see this question for some tricks you can use: #789261 – Behre

I've got my first MD5 collision after 25K images already in DB – Charette

"There are no accidental MD5 collisions" - this statement is false. – Bihari

Loved the idea of hashing some small portions before hashing the whole file. Could greatly speed up duplicate file checking. – Fab

Answer 2

Just because the probability is 1/X it does not mean that it won't happen to you until you have X records. It's like the lottery, you're not likely to win, but somebody out there will win.

With the speed and capacity of computers these days (not even talking about security, just reliability) there is really no reason not to just use a bigger/better hash function than MD5 for anything critical. Stepping up to SHA-1 should help you sleep better at night, but if you want to be extra cautious then go to SHA-265 and never think about it again.

If performance is truly an issue then use BLAKE2 which is actually faster than MD5 but supports 256+ bits to make collisions less likely while having same or better performance. However, while BLAKE2 has been well-adopted, it probably would require adding a new dependency to your project.

Bihari

With the lottery, though, you have a guaranteed winner. Whereas there are no known SHA256 collisions, and it's technically possible for there to never be one up until full exhaustion, right? – Duchy

Good point, in general for a file-hashing app you can pretty safely assume that SHA-256 will never produce a collision (unlike SHA1 which is used by git and collisions have occurred in large real-world projects). However, if using SHA-256 to hash random input bits (such as to generate a session id) you should still consider that the chances of a RNG collision are the same for a given number of input bits regardless of the hashing method used. That is, hashing a random 32-bit integer with SHA-256 is still just 32 bits of data so collisions are likely to occur. – Bihari

Answer 3

I think you shouldn't.

However, you should if you have the notion of two equal files having different (real names, not md5-based). Like, in search system two document might have exactly same content, but being distinct because they're located in different places.

Swelter

That's the problem of the search system, not of my application. My application only needs to extract text from passed files. – Egwin

Answer 4

I came up with a Monte Carlo approach to be able to sleep safely while using UUID for distributed systems that have to serialize without collisions.

from random import randint
from math import log
from collections import Counter

def colltest(exp):
    uniques = []
    while True:
        r = randint(0,2**exp)
        if r in uniques:
            return log(len(uniques) + 1, 2)
        uniques.append(r)

for k,v in Counter([colltest(20) for i in xrange(1000)]):
    print k, "hash orders of magnitude events before collission:",v

would print something like:

5 hash orders of magnitude events before collission: 1
6 hash orders of magnitude events before collission: 5
7 hash orders of magnitude events before collission: 21
8 hash orders of magnitude events before collission: 91
9 hash orders of magnitude events before collission: 274
10 hash orders of magnitude events before collission: 469
11 hash orders of magnitude events before collission: 138
12 hash orders of magnitude events before collission: 1

I had heard the formula before: If you need to store log(x/2) keys, use a hashing function that has at least keyspace e**(x).

Repeated experiments show that for a population of 1000 log-20 spaces, you sometimes get a collision as early as log(x/4).

For uuid4 which is 122 bits that means I sleep safely while several computers pick random uuid's till I have about 2**31 items. Peak transactions in the system I am thinking about is roughly 10-20 events per second, I'm assuming an average of 7. That gives me an operating window of roughly 10 years, given that extreme paranoia.

Torin

Answer 5

Here's an interactive calculator that lets you estimate probability of collision for any hash size and number of objects - http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/

Syreetasyria

The question is not about estimating the probability. I know the probability. The question is what I do next. – Egwin

What you do next is simple: you choose a hash function with more bits and preferably a better distribution, such as sha1, and then describe the chance of a collision, what happens when it occurs, and what are the consequences. – Trueblue

Answer 6

For temporary file names, use OS functionality. It likely uses an intermediate subdirectory, Unix-epoch, etc.

Blanco