From Wikipedia, the free encyclopedia

History and cryptanalysis

Collision vulnerability

Other vulnerabilities

Applications

Algorithm

Figure 1. One MD5 operation. .MD5 consists of 64 of these operations, grouped in four rounds of 16 operations.^ If the password is longer than 64 bytes, the hash-function digest of the password is used as an input (16-byte for [MD5] and 20-byte for [SHA-1] ) to the keyed hashed calculation.

• Binkp Specification 10 January 2010 19:35 UTC www.ritlabs.com [Source type: Reference]

^ Each phase consists of 16 basic steps, for a total of 64 basic steps.

• Performance Analysis of MD5 10 January 2010 19:35 UTC www.isi.edu [Source type: Reference]

.F is a nonlinear function; one function is used in each round.^ The compression function performs 64 rounds, in each round updating the state, using some bits from the input block.

• MD5 considered harmful today 10 January 2010 19:35 UTC www.win.tue.nl [Source type: FILTERED WITH BAYES]

.M_i denotes a 32-bit block of the message input, and K_i denotes a 32-bit constant, different for each operation.^ Then the padded input bit string is divided into blocks of 512 bits each, hereafter called "input blocks".

• MD5 considered harmful today 10 January 2010 19:35 UTC www.win.tue.nl [Source type: FILTERED WITH BAYES]

^ Overview of the MD5 algorithm MD5 is a block-chained digest algorithm, computed over the data in phases of 512-byte blocks organized as little-endian 32-bit words ( Figure 1 ).

• Performance Analysis of MD5 10 January 2010 19:35 UTC www.isi.edu [Source type: Reference]

^ The second code compiles to 8 internal operations on machines with no rotate or swap opcodes, and uses a single 32-bit load (see Table 2 ).

• Performance Analysis of MD5 10 January 2010 19:35 UTC www.isi.edu [Source type: Reference]

._s denotes a left bit rotation by s places; s varies for each operation.^ The second code compiles to 8 internal operations on machines with no rotate or swap opcodes, and uses a single 32-bit load (see Table 2 ).

• Performance Analysis of MD5 10 January 2010 19:35 UTC www.isi.edu [Source type: Reference]

^ Bitwise rotate a 32-bit number to the left.

• MD5 Message Digest 10 January 2010 19:35 UTC secureplay.com [Source type: Academic]

^ The following code took 1 load, 1 store, and 5 internal operations, because this machine has a 32-bit rotate (see Table 2 ).

• Performance Analysis of MD5 10 January 2010 19:35 UTC www.isi.edu [Source type: Reference]

denotes addition modulo 2³².

denote the XOR, AND, OR and NOT operations respectively.

Pseudocode

//Note: All variables are unsigned 32 bits and wrap modulo 2^32 when calculating
var int[64] r, k

//r specifies the per-round shift amounts
r[ 0..15] := {7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22} 
r[16..31] := {5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20}
r[32..47] := {4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23}
r[48..63] := {6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21}

//Use binary integer part of the sines of integers (Radians) as constants:
for i from 0 to 63
    k[i] := floor(abs(sin(i + 1)) × (2 pow 32))

//Initialize variables:
var int h0 := 0x67452301
var int h1 := 0xEFCDAB89
var int h2 := 0x98BADCFE
var int h3 := 0x10325476

//Pre-processing:
append "1" bit to message
append "0" bits until message length in bits ≡ 448 (mod 512)
append bit /* bit, not byte */ length of unpadded message as 64-bit little-endian integer to message

//Process the message in successive 512-bit chunks:
for each 512-bit chunk of message
    break chunk into sixteen 32-bit little-endian words w[i], 0 ≤ i ≤ 15

    //Initialize hash value for this chunk:
    var int a := h0
    var int b := h1
    var int c := h2
    var int d := h3

    //Main loop:
    for i from 0 to 63
        if 0 ≤ i ≤ 15 then
            f := (b and c) or ((not b) and d)
            g := i
        else if 16 ≤ i ≤ 31
            f := (d and b) or ((not d) and c)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47
            f := b xor c xor d
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63
            f := c xor (b or (not d))
            g := (7×i) mod 16
 
        temp := d
        d := c
        c := b
        b := b + leftrotate((a + f + k[i] + w[g]) , r[i])
        a := temp

    //Add this chunk's hash to result so far:
    h0 := h0 + a
    h1 := h1 + b 
    h2 := h2 + c
    h3 := h3 + d

var int digest := h0 append h1 append h2 append h3 //(expressed as little-endian)

  //leftrotate function definition
  leftrotate (x, c) 
      return (x << c) or (x >> (32-c)); 

(0  ≤ i ≤ 15): f := d xor (b and (c xor d))
(16 ≤ i ≤ 31): f := c xor (d and (b xor c))

MD5 hashes

 MD5("The quick brown fox jumps over the lazy dog") 
  = 9e107d9d372bb6826bd81d3542a419d6

 MD5("The quick brown fox jumps over the lazy dog.") 
  = e4d909c290d0fb1ca068ffaddf22cbd0

 MD5("") 
  = d41d8cd98f00b204e9800998ecf8427e

See also

• Comparison of cryptographic hash functions
• md5deep
• md5sum
• HashClash
• MD6

Notes

References

• Berson, Thomas A. (1992). "Differential Cryptanalysis Mod 2³² with Applications to MD5". EUROCRYPT. pp. 71–80. ISBN 3-540-56413-6. 
• Bert den Boer; Antoon Bosselaers (1993). .Collisions for the Compression Function of MD5.^ Previous work on MD5 collisions between 2004 and 2007 showed that the use of this hash function in digital signatures can lead to theoretical attack scenarios.
  • MD5 considered harmful today 10 January 2010 19:35 UTC www.win.tue.nl [Source type: FILTERED WITH BAYES]
  
  ^ A revised version of Collisions for Hash Functions MD4, MD5, HAVAL -128 and RIPEMD has been posted showing collisions for MD5 with the right IVs.
  • Educated Guesswork: August 2004 Archives 10 January 2010 19:35 UTC www.rtfm.com [Source type: General]
  
  ^ We have picked a CA that uses the MD5 hash function to generate the signature of the certificate, which is important because our certificate request has been crafted to result in an MD5 collision with a second certificate.
  • MD5 considered harmful today 10 January 2010 19:35 UTC www.win.tue.nl [Source type: FILTERED WITH BAYES]
  
  Berlin ; London: Springer. pp. 293–304. ISBN 3-540-57600-2. 
• Hans Dobbertin, Cryptanalysis of MD5 compress. Announcement on Internet, May 1996 [8].
• Dobbertin, Hans (1996). "The Status of MD5 After a Recent Attack". CryptoBytes 2 (2). .ftp://ftp.rsasecurity.com/pub/cryptobytes/crypto2n2.pdf. 
• Xiaoyun Wang; Hongbo Yu (2005).^ In 2004 Xiaoyun Wang and Hongbo Yu presented a collision for MD5 consisting of 2 input blocks, neglecting padding.
  • MD5 considered harmful today 10 January 2010 19:35 UTC www.win.tue.nl [Source type: FILTERED WITH BAYES]
  
  ^ Xiaoyun Wang and Hongbo Yu, "How to Break MD5 and Other Hash Functions" In: Ronald Cramer (editor), "Advances in Cryptology - EUROCRYPT 2005", volume 3494 of Lecture Notes in Computer Science, pages 19-35, Springer Verlag, Berlin, 2005.
  • MD5 considered harmful today 10 January 2010 19:35 UTC www.win.tue.nl [Source type: FILTERED WITH BAYES]
  
  ^ The "Colliding X.509 Certificates based on MD5-collisions" website, Arjen Lenstra, Benne de Weger, Xiaoyun Wang, March 2005.
  • MD5 considered harmful today 10 January 2010 19:35 UTC www.win.tue.nl [Source type: FILTERED WITH BAYES]
  
  ."How to Break MD5 and Other Hash Functions".^ From their introduction until the present day, the hash functions MD5 and SHA-1 have been the work horses of many cryptographic systems.
  • MD5 considered harmful today 10 January 2010 19:35 UTC www.win.tue.nl [Source type: FILTERED WITH BAYES]
  
  ^ When all certificates in the chain up to the root CA certificate use other hash functions than MD5 such as SHA-1, our attack has not been used.
  • MD5 considered harmful today 10 January 2010 19:35 UTC www.win.tue.nl [Source type: FILTERED WITH BAYES]
  
  ^ Our result only applies when digital certificates are signed using the hash function MD5, which is known to be broken.
  • MD5 considered harmful today 10 January 2010 19:35 UTC www.win.tue.nl [Source type: FILTERED WITH BAYES]
  
  EUROCRYPT. ISBN 3-540-25910-4. http://www.infosec.sdu.edu.cn/uploadfile/papers/How%20to%20Break%20MD5%20and%20Other%20Hash%20Functions.pdf. 

External links

• RFC 1321 The MD5 Message-Digest Algorithm
• W3C recommendation on MD5

Definition from Wiktionary, a free dictionary

English

Initialism

1. Message Digest 5

Derived terms

• MD5-summed

External links

• MD5 on Wikipedia.Wikipedia

Here are sentences from other pages on MD5, which are similar to those in the above article.