distribution for a subset of md5

I need to uniquely assign a 32 bit integer to a collection of human readable strings (i.e. they will not be generated with hash collision in mind). I don't expect more than a few thousand strings. I would like to evaluate the possibility of using the first 32 bits of the md5 sum for this. What is the distribution of these bits?

• I'll go a little off-topic, but... How about using this? gnu.org/software/gperf Commented Mar 13, 2014 at 14:19
• Disclaimer: I have never used it, just saw it some weeks ago by coincidence in the MacPorts repository. Commented Mar 13, 2014 at 14:20
• The collection can be extended, so unfortunately gperf will not work.
– JRG
Commented Mar 14, 2014 at 17:24

I guess it is wanted to assign a 32-bit integer to each of human readable strings in some collection (for the problem as worded, the answer is 00000000000000000000000000101010).

Assuming that the human readable strings are chosen independently of the definition of MD5, then the first 32-bit of the MD5 hash of each string is about uniformly distributed. That would be a classical result for any hash that is a PRF (for any distinguisher able to recognize the first 32 bits from a random function can trivially be turned into a distinguisher for the full function). MD5 was designed with the goal to be a PRF, and remains good enough. Sorry I do not have a reference.

Odds that there is at least one collision with $n$ strings is $$p=1-(2^{32})!/(2^{32}-n)!/2^{32\cdot n}\approx1-e^{-n\cdot(n-1)/2^{33}}\approx n\cdot(n-1)/2^{33}$$ The approximation on the right is quite good for $n$ up to about $2^{14}$, arguably including " a few thousand strings ". For $n=10,000$, $p\approx1.2\%$.

However, one knowing your plan to do this and in a position to generate the human readable strings can make the number of collisions high (including having all the strings giving 00000000000000000000000000101010). That MD5's collision resistance is now badly broken is not relevant: the problem is that a 32-bit value is too small. To solve this issue (and return to the probability of collision previously stated even for evil choice of the strings), use a MAC with a secret key, e.g. a truncated HMAC.

Note: the MAC solution also allows to solve the problem of finding a hash with no collision for a particular collection, known as a perfect hash, in a simple way: try distinct keys at random until finding one for which there is no collision: that's easy to check with with $2^{32}$ bits (512 MiB) of RAM. It is tried on average $1/(1-p)$ keys and less than $n/(1-p)$ MAC computations. When $n$ grows past about $2^{17}$ that becomes increasingly impractical, and dynamic perfect hashing comes to the rescue.

• The particular information I was seeking was "Assuming that the human readable strings are chosen independently of the definition of MD5, then the first 32-bit of the MD5 hash of each string is about uniformly distributed". Where can I find a reference?
– JRG
Commented Mar 14, 2014 at 17:26
• By human readable, I meant to convey 'not chosen with the intent of inducing collisions'
– JRG
Commented Mar 14, 2014 at 17:28
• I am always a little taken aback by birthday problem calculations at an order of magnitude I hadn't seen before. Intuition really fails, usually spectacularly.
– JRG
Commented Mar 14, 2014 at 17:37