Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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? –  Josh Guffin Mar 14 at 17:26
    
By human readable, I meant to convey 'not chosen with the intent of inducing collisions' –  Josh Guffin Mar 14 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. –  Josh Guffin Mar 14 at 17:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.