Change in probability of collision when removing digits from MD5 hexadecimal hash values

Question

I am aware that MD5 has a known collision vulnerability and should not be relied upon when uniqueness is required, but in the environment I am working on I only have access to MD5 hash function. Background detail below, but in general how much and how bad is the change in the probability of hash collision if I removed a few digits from the hexadecimal representation of MD5 hash values?

Background: I am working on migrating data between two systems. The target system has a built-in database column of length 30 characters that has unique/primary key resolution mechanism, meaning as long as I put a matching value in that column the system will map it to existing record if exists and create new record otherwise. Unfortunately the primary key from source system has length of between 50 to 100 characters so my best bet is to generate a shorter hash value from it. I only have access to MD5 hash function but the hexadecimal hash value is 32 digits long so I have to drop two of the digits. There is virtually zero probability of anyone wanting to use collision attack on the data so my concern is pretty much on the distant possibility of Heaven-assisted coincidence that two primary keys might generate the same hash value.

N.B. Possibly related to "Should I use the first or last bits from a SHA-256 hash?", but that question is about SHA-256 while this one is about MD5.

Answer 1

First things first: there is nothing magical in hexadecimal. The output of MD5 is, nominally, a sequence of 128 bits, or, if you prefer, 16 bytes (each being able to get any value between 0 and 255). Hexadecimal is just a trick to represent a single byte as two characters in a limited range (digits, and letters from 'a' to 'f'). If you can have 30 characters then you can probably use more than the hexadecimal digits. For instance, with Base64 encoding, you can unambiguously represent any MD5 output (16 bytes) into 24 characters chosen in a list consisting of digits, uppercase letters, lowercase letters, '+', '/' and '=' (the '=' sign appears only at the end, and your 24 characters will always end with a pair of '=' signs, which you can altogether omit; hence, make that 22 characters).

To answer your initial question, assuming that MD5 behaves "randomly" (which is kind of true as long as nobody is actively trying to produce collisions), then keeping $n$ hexadecimal characters means keeping $4n$ MD5 output bits, and collisions are expected to appear around $2^{2n}$ keys. With $n = 30$, that's $2^{60}$, also known as "approximately a billion billions", which is still kind of huge. Still, you'd better use a shorter encoding such as Base64, which avoids the issue altogether.