HomeAboutGitlab

How uniform is MD5

Introduction

At work we're building a system that will try to distribute users in a deterministic fashion: basically f(user, context) should be a pure function, always returning the same value for the same inputs.

There's the need that we want to use one of these functions to split our population in an uniform way: 25% will do something, the rest will do something else. Since we'll use this for experimentation, we always want the same user to fall in the same group (unless context changes).

A naive approach to do this, is every time you get a new tuple (user, context), you roll a dice and decide where to put this user according to the result. You'll need to make sure to store the assignment, so the next time the user comes, you will give him the already decided number (to keep the deterministic part of the contract), otherwise you would assign a different number to that tuple every time.

What are our (better) options

If we didn't care about storage and efficiency, this would work just fine. We would also need to consider that our dice is "fair": it returns each face with the same probability. This is, however, not practicall at all: if you wanted to keep the same assignment across multiple runs (which you want if you're running an experiment), you would need to pay the cost of a lookup on an external DB. Keeping the data in memory is not feasible unless your population is really small.

With that in mind, the next obvious question is: can I derive a number from my tuple (user, context) and somehow use that number to "roll the dice"? It turns out there's a whole family of functions that could help us with that: turning data into numbers is what hashing functions are for.

The basic idea of a hashing function is something like this:

how_uniform_is_md5_b267806fc6c35e1c200157fa42b16dc3e92dc2a8.png

where how_uniform_is_md5_bd106870037c0449355203d8a939fd6e5b4286fa.png is the set of natural numbers that can be represented in how_uniform_is_md5_1fe8726f263aa487212ae159aeb9fe732d0efcaf.png bits (that would be the size of the digest). With that generic definition, we will look into three of these hashing functions:

how_uniform_is_md5_f85243c82dd8dca3ea081336850273815fa009fb.png

The hashing value returned by each one of these functions is the same given the same data, but different from each other:

how_uniform_is_md5_a3bf5f68f681a0e9d08408fcbce196eef65dce27.png

The difference between MD5 and the other two (MurmurHash3 and SpookyHash) is that MD5 is a cryptographic hash function. Although long time ago MD5 was proven to be weak to be used as a cryptographic function, it's still very popular as a regular hashing function: to prove that data is not corrupted, or, like in our example, to try to correlate some data to a random number.

It is expected from a hashing function to try to be as uniform as possible: this means that given an arbitrary data feed into the function, it should try to return numbers that are spread as much as possible in the output range. As a more concrete example, if your hashing function had a digest of 1 bit (either 0 or 1 are the only two options), then if it's uniform then it should return 0 or 1 with equal probability (it should be a fair coint toss).

With that information at hand, we can now try to prove how uniform are these hashes.

How do we test for uniformity?

Let's work with our 1 bit hashing function for a little bit. Let's actually give it a name: coinhash.

how_uniform_is_md5_2d178424b8d43215ebf99ef85bc5efed05b3417b.png

If we run cointoss 100 times with 100 different data arguments, we would expect it to return 50 times 0 and 50 times 1. If it's too far apart, then we would say it's not uniform for our data set.

What does it mean not too far apart? how can we measure it?

It turns out that there's a statistical test for that, the how_uniform_is_md5_b8f704d39fa3c45f46e93512030e9803818d20d6.png test (Chi Squared test). The Chi Square test is used to determine significant difference between two distributions (expected and measured). If you want to learn more about Chi Square, I highly recommend you to look at the videos at Khan Academy on the subject.

For our experiment, running a Chi Squared test will return two important values, the Chi Square statistic, and a probability (p-value) that will tell us how probable is that we would get that statistic (the statistic is basically the normalized squared sum of the difference between the expected and the observed values).

Running our test

Now that we have a strategy on how to measure whether or not a hashing function can provide a uniform distribution, let's test them.

We'll use python and scipy, mostly because scipy (and numpy) can provide most of the statistic functions for us out of the box. I tried using Ruby and the gems provided by SciRuby, but the docs were really poor and the Chi Squared test failed to provide good results for large sets of data.

Before we begin let's state our null hypothesis:

how_uniform_is_md5_145c5fba31d376dbbaee0887814fb4cd629dcb3d.png MD5 hashing has a uniform distribution

We'll also decide upfront that any result with a p-value less that 5% will reject our null hypothesis.

Setup

We'll use the following python libraries:

import numpy as np
import mmh3
import struct
import md5
import sys
import numpy as np
import json
import socket
import random
import spooky_hash
from uuid import uuid4
from scipy import stats

Create the data set

We'll create a small dataset that probably will resemble what we'll by trying to do in real life: according to some specific user data (userid + some context), get a unique (hopefully random) number.

For that, we'll generate 5 million random users and store them in a "json-lines" text file, that we'll later use to test all three hashing functions (same dataset for all three).

TOTAL_RECORDS = 5000000
FILENAME= '/home/rolando/Documents/www.rolando.cl/wip/2018/12/dataset.txt'
# from https://stackoverflow.com/a/21014653
def random_ip():
        return socket.inet_ntoa(struct.pack('>I', random.randint(1, 0xffffffff)))

def create_user():
        return json.dumps({
                'id': str(uuid4()),
                'ip': random_ip()
        })

with open(FILENAME, 'w') as f:
        for i in range(0, TOTAL_RECORDS):
                user = create_user()
                f.write(user + "\n")

MD5

Ok, now to finally run the test for our first hashing function. For that we need to read the data and calculate histogram. I decided to use 10000 buckets to give us more granularity on the hashed data. A common scenario could also be use 100 buckets (that could easily be mapped later to a percentage).

MAX_DOUBLE = float(0xFFFFFFFFFFFFFFFF)
BUCKETS = 10000
sums_md5 = [0] * BUCKETS

def md5_hash(uuid):
        return struct.unpack_from('Q', md5.new(uuid).digest())[0]

with open(FILENAME, 'r') as f:
        for line in f:
                data = line.rstrip()
                val = md5_hash(data)
                bucket = int((val / MAX_DOUBLE) * BUCKETS)
                sums_md5[bucket] += 1

The gist of it is that we calculate the md5 digest of every line in the file (a json dump of our user data), then we get the first 128 bit unsigned integer from that large number. After that, we normalize it to how_uniform_is_md5_f6f80e1b22ff02a5cd4e74faa4c9ca1e2e67f72f.png and add a 1 to the bucket in sums_md5.

Now that we have the sums, we can calculate the Chi Squared test. The expected distribution is easy to get: we are expecting a uniform distribution, that is, the same number of elements in each bucket. How many? TOTAL_RECORDS / BUCKETS.

expected_q = float(TOTAL_RECORDS) / BUCKETS
expected = [expected_q] * BUCKETS

res = stats.chisquare(sums_md5, expected)
print(res)
Power_divergenceResult(statistic=10110.476, pvalue=0.21473669149106034)

Ok, we got a number. For our data set, MD5 results in how_uniform_is_md5_bde5b242061737b1a8f81bd173fc78641436b748.png. The probability to get that number is 21.47%. Since this is bigger than our threshold of 5%, we do not reject our null hypothesis and can say that MD5 is uniform (for our data set).

Murmurhash3

It's the time now for MurmurHash3. We'll do the same process: first, calculate histogram for the same dataset.

sums_murmur = [0] * BUCKETS

def murmur_hash(uuid):
                return mmh3.hash64(uuid, signed=False)[0]

with open(FILENAME, 'r') as f:
        for line in f:
                data = line.rstrip()
                val = murmur_hash(data)
                bucket = int((val / MAX_DOUBLE) * BUCKETS)
                sums_murmur[bucket] += 1

Now we can calculate the Chi Squared test for our observed data.

res = stats.chisquare(sums_murmur, expected)
print(res)
Power_divergenceResult(statistic=10084.668000000001, pvalue=0.27133381341907714)

We got very similar results than for MD5: 27% of getting that statistic. We can say MurmurHash3 is also uniform for our data set.

SspookyHash

Finally, the same process but now for SpookyHash.

sums_spooky = [0] * BUCKETS

def spooky_hash_(uuid):
                return struct.unpack_from('Q', spooky_hash.Hash64(uuid).digest())[0]

with open(FILENAME, 'r') as f:
        for line in f:
                data = line.rstrip()
                val = spooky_hash_(data)
                bucket = int((val / MAX_DOUBLE) * BUCKETS)
                sums_spooky[bucket] += 1

And the Chi Squared test for the observed data.

res = stats.chisquare(sums_spooky, expected)
print(res)
Power_divergenceResult(statistic=10092.240000000002, pvalue=0.2539818853860341)

Again, this also seems to be uniform with a p-value of 25%.

Bonus track: standard deviation

Since all three hashing functions proved to be uniform for our data set, I decided to get the standard deviation, to get an idea how spread apart was the data.

print("=== mean ===")
print expected_q
print("=== md5 ===")
print(np.std(np.array(sums_md5)))
print("=== murmurhash3 ===")
print(np.std(np.array(sums_murmur)))
print("=== spookyhash ===")
print(np.std(np.array(sums_spooky)))
=== mean ===
500.0
=== md5 ===
22.48385643078162
=== murmurhash3 ===
22.45514195011913
=== spookyhash ===
22.46357050871477

What does this mean?

It means that basically they are spread in a very similar way. Given that the expected number of items per bucket was 500, and the standard deviation for all of them was aprox. 22.45 (4.5%), I would say it's pretty uniform.

Conclusion

So, should we use MD5? or some other hash?

They all seem to be equally good (MurmurHash had a little bit higher probability). MD5 is slower though, and there's no clear advantage on using MD5 over any of the other non-cryptographic hashes (for the tested dataset). I would recommend to use either Murmurhash3 or SpookyHash since they are faster and provide an equally good result for our data set.

Copyright © 2012-2018 Rolando Abarca - Powered by orgmode

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License unless otherwise noted.