The message-digest algorithm md5 1 Introduction

(1) What is a message-digest algorithm(MDA)?

A message-digest algorithm is also called a hash function or a cryptographic hash function. It accepts a message as input and generates a fixed-length output, which is generally less than the length of the input message. The output is called a hash value, a fingerprint or a message digest.
(2) Properties of a message-digest algorithm

When people plan to design a message-digest algorithm, they try to make the algorithm satisfy the following properties:

. It should be one-way. Given the message digest, it is hard to get the original message.

. Given both input and output, it is difficult to find another input message which generates same output.

. It should be collision-resistant. It is computationally infeasible to find two messages, which generates same message digest. This property is not same as the second property. It is easier to make attack on this property than on the second property.

. The message digest should satisfy pseudo-randomness.

Message-digest algorithms are mainly used in implementing digital signature. In this case, all of the above properties are required. However, the requirement is quite different when different applications use these algorithms. An application may rely upon some or all of the properties of the MDA. For example, some applications use the one-way property of a MDA. Because of its property of pseudo-randomness, MDA is also used to be part of the mechanism for random number generation.

There are three kinds of operations in MD5:

. Bitwise Boolean Operation

. Modular Addition

. Cyclic Shift Operation

All these three operations are very fast on a 32-bit machine. So MD5 is quite fast.

MD5, as well as MD2 and MD4, follows a design principle proposed by Merkle and Damagard. Its basic idea is to do hash in a block-wise mode. In a word, MD5 consists of two phases: padding phase and compression phase. In the padding phase, some extra bits (1 to 512bits) are appended to the input message. The result bits is congruent to 448 mod 512. Then the length of the initial message is transformed to a 64-bit binary-string(if the length is greater than 2⁶⁴, the lower 64-bit is used) and this 64 bits is added to the tail of the message too. So the padding phase ends with a bit stream that consists of one or more 512-bit blocks. In the compression phase, a compression function is used on each 512-bit block and generates a 128-bit output. The output is always involved in the calculation of next round.

1. 
   Add padding bits behind the input message
   

Length(the padded message)  448 mod 512

For example, suppose the initial message has 1000 bits. Then this step will add 1 bit “1” and 471 bits “0”. As another example, consider a message with just 448 bits. Since the algorithm doesn’t check whether the initial length is congruent to 448 mod 512, one bit “1” and 511 bits “0” will be appended to the message. Therefore, the padding bits’ length is at least one and at most 512.

2. 
   Add a 64-bit binary-string which is the representation of the message’s length
   

3. 
   Initialize four 32-bit values
   

A = 0x67452301

B = 0xEFCDAB89

C = 0x98BADCFE

D = 0x10325376

4. 
   Compress every 512-bit block
   

5. 
   Generate the 128-bit output
   

There are four rounds and sixteen steps in each round.

It uses more rounds.

Rivest designed MD2, MD4 as well as MD5.