MD4 Hash

MD4 is a message digest algorithm (the fourth in a series) designed by Professor Ronald Rivest of MIT in 1990. It implements a cryptographic hash function for use in message integrity checks. The digest length is 128 bits. The algorithm has influenced later designs, such as the MD5, SHA and RIPEMD algorithms. MD4 is also used to compute NT-hash password digests on Microsoft Windows NT, XP and Vista.

MD4 was designed to be fast, which meant taking a few risks regarding security. By 1992 weaknesses had been found which led Rivest to produce a strengthened, but slower, version known as MD5. In 1998, Dobbertin [1, 2] found the first MD4 collisions, and he gave an algorithm for generating such collisions, with a work factor that is approximately equal to the computation of 2^20 MD4 hashes.

The MD4 hash should not be used for any cryptographic purposes.

Input
Calculate
Result

The Algorithm §

The MD4 algorithm is described by Rivest in RFC 1320, along with an efficient implementation (in C).

MD4 operates on 32-bit words. Let M be the message to be hashed. The message M is padded so that its length (in bits) is equal to 448 modulo 512, that is, the padded message is 64 bits less than a multiple of 512. The padding consists of a single 1 bit, followed by enough zeros to pad the message to the required length. Padding is always used, even if the length of M happens to equal 448 mod 512. As a result, there is at least one bit of padding, and at most 512 bits of padding. Then the length (in bits) of the message (before padding) is appended as a 64-bit block.

The padded message is a multiple of 512 bits and, therefore, it is also a multiple of 32 bits. Let M be the message and N the number of 32-bit words in the (padded) message. Due to the padding, N is a multiple of 16.

A four-word buffer (A,B,C,D) is used to compute the message digest. Here each of A, B, C, D is a 32-bit register. These registers are initialized to the following values in hexadecimal:

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

We first define three auxiliary functions that each take as input three 32-bit words and produce as output one 32-bit word.

where is logical and, is logical or and is logical xor. Do the following:

/* Process each 16-word block. */
For i = 0 to N/16-1 do
    /* Copy block i into X. */
    For j = 0 to 15 do
        Set X[j] to M[i*16+j].
    end /* of loop on j */
    
    /* Save A as AA, B as BB, C as CC, and D as DD. */
    AA = A
    BB = B
    CC = C
    DD = D
    
    /* Round 1. */
    /* Let [abcd k s] denote the operation:
             a = (a + F(b,c,d) + X[k]) <<< s. */
    /* Do the following 16 operations. */
    [ABCD  0  3]  [DABC  1  7]  [CDAB  2 11]  [BCDA  3 19]
    [ABCD  4  3]  [DABC  5  7]  [CDAB  6 11]  [BCDA  7 19]
    [ABCD  8  3]  [DABC  9  7]  [CDAB 10 11]  [BCDA 11 19]
    [ABCD 12  3]  [DABC 13  7]  [CDAB 14 11]  [BCDA 15 19]

    /* Round 2. */
    /* Let [abcd k s] denote the operation:
             a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. */
    /* Do the following 16 operations. */
    [ABCD  0  3]  [DABC  4  5]  [CDAB  8  9]  [BCDA 12 13]
    [ABCD  1  3]  [DABC  5  5]  [CDAB  9  9]  [BCDA 13 13]
    [ABCD  2  3]  [DABC  6  5]  [CDAB 10  9]  [BCDA 14 13]
    [ABCD  3  3]  [DABC  7  5]  [CDAB 11  9]  [BCDA 15 13]

    /* Round 3. */
    /* Let [abcd k s] denote the operation:
             a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */
    /* Do the following 16 operations. */
    [ABCD  0  3]  [DABC  8  9]  [CDAB  4 11]  [BCDA 12 15]
    [ABCD  2  3]  [DABC 10  9]  [CDAB  6 11]  [BCDA 14 15]
    [ABCD  1  3]  [DABC  9  9]  [CDAB  5 11]  [BCDA 13 15]
    [ABCD  3  3]  [DABC 11  9]  [CDAB  7 11]  [BCDA 15 15]

    /* Then perform the following additions. (That is, increment each
       of the four registers by the value it had before this block
       was started.) */
    A = A + AA
    B = B + BB
    C = C + CC
    D = D + DD
    
end /* of loop on i */

References §

H. Dobbertin, Cryptanalysis of MD4, Proceedings of the Third International Workshop on Fast Software Encryption, LNCS 1039, D. Goll- mann, Ed., Springer-Verlag, 1996, pp. 53-69

H. Dobbertin, Cryptanalysis of MD4, Journal of Cryptology, Vol. 11, NO. 4, 1998, pp. 253-271

R. Rivest, RFC 1320-the MD4 rnessage-digest algorithm, April 1992, at ftp.rfc-editor.org/in-notes/rfcl32O.txt

comments powered by Disqus