Entropy of truncated MD5 hashing

Description of the problem

MD5 is a commonly used hashing algorithm to store passwords whose input can vary in length (from a single character to an entire text of Iliad if you’d like) but whose output is uniformly 128 bits. Today I’d like to test the following: if we were to select certain bytes from the output and use these bytes only as our hash, would we see something other than a truly uniform random output? Are there weaknesses in MD5, not when we use the whole 128 bits but certain parts of it?

Entropy

Entropy is a good numerical measure for randomness. So, I will generate a good number of random strings then apply the hash function. Then I will use a fixed portion of the output and measure the entropy. If the entropy is less than the entropy for a uniformly random collection of bytes then MD5 might have weakness in those bytes.

Implementation

I am going to need an MD5 implementation for lisp.

(require :md5)

The following function is for generating random strings of a specific length. I lifted the code from code codex with minimal modification.

(defun random-string (n)
   (let* ((chars "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789")
          (m (length chars)))
      (coerce (loop repeat n collect (aref chars (random m))) 'string)))

RANDOM-STRING

The following function generates a collection of random strings and then pushes through MD5 hashing function with the specified projection. At the end we calculate all the collisions and calculate the entropy of these collisions.

(defun entropy (m n pick)
   (let ((coll (make-hash-table :test 'equal))
         (res 0.0d0))
      (loop repeat m do
         (let* ((str (md5:md5sum-string (random-string n)))
                (pro (mapcar (lambda (i) (aref str i)) pick))
                (val (gethash pro coll 0)))
            (setf (gethash pro coll) (1+ val))))
      (maphash 
         (lambda (x y) 
             (incf res (* y (log y 2d0)))) 
         coll)
      (- (log m 2d0) (/ res m))))

ENTROPY

I am going to test all of the projections of MD5 onto 2 bytes.

An analysis

The theoretical limit for the entropy for truly random collection of 2 bytes is \[ -\sum_{i=1}^{2^{16}} \frac{1}{2^{16}}\log_2(2^{-16}) = 16 \] and the values are uniformly close to the theoretical value. I didn’t have time to repeat the experiment with 3 or more bytes. The code above took about a minute on my old workstation at work.

In short, if you’d like to cut short of an MD5 hash you can use any portion of it you’d like.