MD5 algorithm overview

Roman Nepšinský aka Mem/Mlat, 17.10.2002

Contents

• Message-Digest algorithms characteristics
• MD2, MD4, MD5 algorithms overview
• MD5 algorithm description
• MD5 algorithm uses
• References

Message-Digest algorithms characteristics

Message-Digest (Fingerprint) algorithms are special functions which transform input of (usually) arbitrary length into output (so-called "fingerprint" or "message digest") of constant length. These transformation functions must fulfil these requirements:

• no one should be able to produce two different inputs for which the transformation function returns the same output
• no one should be able to produce input for given prespecified output

Message-Digest algorithms serve in digital signature applications for guaranteeing consistency (integrity) of data. Commonly used model is as follows (message-digest in cooperation with asymmetric cryptography):

• Sender creates input message (M) and computes its message digest (sMD). Then he uses his private key and encrypts message digest (esMD).
• Encrypted message digest (esMD) is attached to the input message (M) and the whole message (M-esMD) is sent to receiver.
• Receiver gets the message (M-esMD) and extracts the encrypted message digest (esMD). Then he computes his own message digest (rMD) of the received message (M). He also decodes received message digest (esMD) with sender's public key and gets decoded message digest (desMD). Then he compares both message digests (rMD ?= desMD). When both message digests are equal, the message was not modified during the data transmission.

MD2, MD4, MD5 algorithms overview

MD2, MD4 and MD5 are message-digest algorithms developed by Ronald L. Rivest (the Rivest that stands for the letter 'R' in RSA algorithm). All these three algorithms take input message of arbitrary length and produce a 128-bit message digest. (Short description taken from RSA Security Inc. [1].)

• MD2 - developed in 1989 (description available in Internet RFC 1319)
  The message is first padded so its length in bytes is divisible by 16. A 16-byte checksum is then appended to the message, and the hash value is computed on the resulting message. MD2 was optimized for 8-bit machines, whereas MD4 and MD5 were aimed at 32-bit machines.
  
  
• MD4 - developed in 1990 (description available in Internet RFC 1320)
  The message is padded to ensure that its length in bits plus 64 is divisible by 512. A 64-bit binary representation of the original length of the message is then concatenated to the message. The message is processed in 512-bit blocks in the Damgard/Merkle iterative structure, and each block is processed in three distinct rounds.
  
  
• MD5 - developed in 1991 (description available in Internet RFC 1321 [2])
  It is basically MD4 with "safety-belts" and while it is slightly slower than MD4, it is more secure. The algorithm consists of four distinct rounds, which has a slightly different design from that of MD4. Message-digest size, as well as padding requirements, remain the same.
  
  

MD5 algorithm description

MD5 algorithm takes input message of arbitrary length and generates 128-bit long output hash. MD5 hash algorithm consist of 5 steps (described in deatil in Internet RFC 1321 [2]):

• Step 1. Append Padding Bits
  
• Step 2. Append Length
  
• Step 3. Initialize MD Buffer
  
• Step 4. Process Message in 16-Word Blocks
  
• Step 5. Output
  

MD5 algorithm uses

MD5 is commonly used hash algorithm. It can be found in many implementations (available on some unix-based system as utility md5; class MD5CryptoServiceProvider in Microsoft's .NET Framework (namespace System.Security.Cryptography); example implemetation in Visual C++ [5] or JavaScript [4], etc). It is used sometimes as file CRC function (Napster...) or one-way cipher in authentization operations (for storing user password hash).

MD5 is also used in conjunction with other cryptographic methods in digital signature applications or in protocols like SSL and others.

References

• [1] RSA Security Inc.
  http://www.rsasecurity.com
• [2] RFC1321 - The MD5 Message-Digest Algorithm
  http://www.faqs.org/rfcs/rfc1321.html
• [3] MD5 Hash Algorithm - Version 1.0 (Part of W3C DSig 1.0 Recommendation)
  http://www.w3.org/TR/1998/REC-DSig-label/MD5-1_0
• [4] MD5 Message Digest algorithm in Javascript (online)
  http://www.geocities.com/SiliconValley/7116/jv_md5.html
• [5] Visual C++ implementation of RSA MD5 Message Digest by Langfine Ltd.
  http://www.langfine.com/rsa_md5.htm