Comparing performance of 5 hash functions

(Cryptix Application Note #1 --July 1997)

 

Return to the Application Notes Index or the FAQ or the Overview


Introduction

Antoon Bosselaers, co-author of RIPEMD-160, has extensively reviewed the performance of the MD4, MD5, SHA, RIPEMD, RIPEMD-128 and RIPEMD-160 hash functions ([DBP96], [BGV96] and [Bos97]) on Pentium processors using highly optimised Assembler and C code. The following table gives performance indices of these hash algorithms (all except RIPEMD) based on Bosselaers latest implementations as published in his report [Bos97]:

Table-1: Antoon Bosselaers performance test results summary

Algorithm

Rate
(Mbits/sec)

Relative
Performance

MD4

190.6

100

MD5

133.1

70

SHA-1

54.9

29

RIPEMD-128

76.9

40

RIPEMD-160

45.2

24


Tests

I conducted a limited test (1 MB) using Cryptix's Java implementations of MD4, RIPEMD-128 and RIPEMD-160, and used Sun's MD5 and SHA available in the JDK sun package (source code in TestMDs). These are the result of this test obtained with a Pentium 133MHz running the JDK 1.1.3 Virtual Machine on a Windows95, both with and without the JIT compiler included in Sun's Performance Pack.

Table-2: Cryptix implementation performance with JDK 1.1.3

Without JIT compiler

With JIT compiler

Algorithm

Time
(millis.)

Rate
(Kbits/sec)

Relative
Performance

Time
(millis.)

Rate
(Kbits/sec)

Relative
Performance

MD4

5,220

1,569

100

770

10,638

100

MD5 (1)

7,630

1,073

68

880

9,309

87

MD5 (2)

10,930

788

50

1,590

5,152

48

SHA-1

7,910

1,035

65

770

10,638

100

RIPEMD-128

8,780

933

59

1,210

6,770

63

RIPEMD-160

12,200

671

42

1,320

6,206

58

The figures for the MD5 (1) line were obtained with a special version of Sun's MD5. I decompiled and re-compiled it with its engineUpdate() method redefined as public to allow access from the test class, and changed the place of the synchronisation lock to be on the whole class instead of it being local for some methods. This was done to have comparable execution times.

The MD5 (2) is the normal sun.security.provider.MD5. Figures for this version are slower than what they should be, mainly due to the inability to directly call the engineUpdate() method --it is defined as protected and hence only calls to update() from the MessageDigest superclass can be invoked. The difference between the two lines is mostly the penalty paid for mapping update(byte[]) from the MessageDigest superclass to MD5 class's engineUpdate(byte[], int, int) and back.

 
Conclusions

  1. The speed difference between assembler implementations and Java ones is striking --190Mb/s for MD4 in assembler compared to approx. 10Mb/s in Java (using a JIT).

  2. The speed difference between Sun's implementations of MD5 and SHA-1, compared to the same in Table-1 cannot be attributed only to quality of coding. Besides re-working the hash computation formulae in an incremental manner, the other explanation I can find is that operations such as left rotation and [de-]indexing cost more with Java than they do with assembler in terms of performance.

  3. Also different implementation of some algorithms, specifically RIPEMD-160, RIPEMD-128 and MD4-- show that, in Java, beyond a certain threshold, in-lining/macro style of C code, where a transform function is called/expanded n times with different parameters, does not always yield better performance than using traditional loops and in-lining the funtion itself within the loop block. The reasons are (a) no macro facility (code expansion) exists in Java, and (b) Java makes you pay a high price for method invocation. MD4 with its 48 functions seems to examplify this limit.

    The following table shows the test figures for just MD4, RIPEMD-128 and RIPEMD-160 algorithms, using two coding implementations: the same one used above and included in the cryptix package, and a different one (MD4-slow.java, RIPEMD128-slow.java and RIPEMD160-slow.java) where the main hash formulae loops have been in-lined.

    Table-3: Fast and slow implementation performance comparison (using JIT compiler)

    Fast

    Slow

    Algorithm

    Time
    (millis.)

    Relative
    Performance

    Time
    (millis.)

    Relative
    Performance

    MD4

    770

    100

    940

    100

    RIPEMD-128

    1,210

    63

    1,540

    63

    RIPEMD-160

    1,320

    58

    1,970

    58

 
References

All found on Antoon Bosselaers' web site.

[DBP96]
H. Dobbertin, A. Bosselaers, B. Preneel, RIPEMD-160: A strengthened version of RIPEMD.
 
[BGV96]
A. Bosselaers, R. Govaerts, H. Vandewalle, Fast hashing on the Pentium.
 
[Bos97]
Antoon Bosselaers, Even faster hashing on the Pentium.


Cryptix
Raif S. Naffah
Chatswood, 12 July 1997.

Copyright © 1996-1997 Systemics Ltd
on behalf of the Cryptix Development Team.
All rights reserved.
Cryptix is a trademark of Systemics Ltd.