Exploring the Performance of MD5: Efficiency and Security

In this project, we explored the performance of the popular hash function MD5 — Message Digest Algorithm Version 5. Firstly we introduce the algorithm in detail. Then we check the algorithm’s complexity in two aspects: computational and space complexity. Furthermore we check the security aspects of MD5: whether it is feasible to find collision it using brute force, birthday attack, and cryptanalysis. Available cryptanalysis methods are introduced so that we can find out why MD5 is not considered secure any more.

The computational complexity of MD5 can be seen from the following diagram:

The bash script used to generate the above diagram is as follows:

#!/bin/sh
# Date:   Nov. 28th, 2009
# Usage:  ./timemd5.sh Directory_Name

USAGE='Usage: ./timemd5.sh Directory_Name'

if [ $# != 1 ]
then
    echo $USAGE
    exit
fi

if [ -d $1 ]
then
    DICTORY=$1
else
    echo $USAGE
    exit
fi

# Create a statics file
DATE=`date +%Y%m%d%H%M%S%N`
STATICS="$HOME/statics.$DATE"
if [ ! -e "$STATICS"]
then
    touch "$STATICS"
fi
cat /dev/null >$STATICS

cd $DICTORY

# For each file in the directory, 
# compute its MD5 value with 'md5sum'.
# And record the file size and the time
# it takes to compute its MD5 hash.
find $PWD -iname "*" |\
while read i
do
    if [ -f "$i" ]
    then
        echo "Calculating MD5 for: $i"
        SIZE=`du -m "$i" |cut -f1`
        (time -f "%e" -o /tmp/time md5sum \
         "$i")1> /dev/null
        TIME=`cat /tmp/time`
        echo "$SIZE\t\t$TIME" >>$STATICS
    fi
done

rm /tmp/time
echo "Size\t\tTime"
cat $STATICS

# Draw a more straightforward graph
# using 'gnuplot'
cd $HOME
GNUPLOTFILE="plot"
echo "set terminal postscript eps 22" \
      >$GNUPLOTFILE
echo "set output \"graph.eps\"" \
      >>$GNUPLOTFILE
echo "set key left top Left" \
      >>$GNUPLOTFILE
echo "setxlabel \"File Size (M)\"" \
      >>$GNUPLOTFILE
echo "set ylabel \"Processing Time (s)\"" \
      >>$GNUPLOTFILE
echo "plot [0:1500][0:50] \""$STATICS"\" \
      with points ps 1 pt 7 title \"\"" \
      >>$GNUPLOTFILE
gnuplot <$GNUPLOTFILE

evince graph.eps&

#rm $GNUPLOTFILE
#rm $STATICS
echo "Task done!"

exit