Explain the working of MD5 algorithm with a suitable example.

Introduction to MD5

The Message Digest Algorithm 5 (MD5), designed by Ronald Rivest in 1991, is a cryptographic hash function that produces a 128-bit (16-byte) hash value from an input message of arbitrary length. MD5 is part of the MD family (MD2, MD4) and was widely used for data integrity verification, password hashing, and digital signatures. However, due to vulnerabilities to collision attacks, MD5 is considered cryptographically broken and is deprecated for secure applications, though it remains relevant for non-security purposes like checksums. Understanding MD5’s working is essential for B.Tech students studying cryptographic hash functions and their limitations.

MD5 follows the Merkle-Damgård construction, processing input data in fixed-size blocks and applying a compression function to produce a fixed-length hash. It is deterministic, fast, and designed to exhibit pre-image resistance, second pre-image resistance, and collision resistance, though the latter is compromised in modern contexts.

Working of MD5 Algorithm

MD5 processes an input message through a series of steps, transforming it into a 128-bit hash. The algorithm operates in five main phases: padding, message division, initialization, compression, and output. Below is a detailed explanation:

1. Padding the Message:
   • The input message is padded to ensure its length (in bits) is congruent to 448 modulo 512 (i.e., 64 bits short of a 512-bit block).
   • Padding involves appending a single ‘1’ bit followed by enough ‘0’ bits to reach the required length.
   • The last 64 bits are reserved for the message’s original length (in bits), represented as a 64-bit integer.
   • Example: For a 24-bit message (3 bytes, e.g., “abc”), the message is padded with a ‘1’ bit, 421 ‘0’ bits, and a 64-bit length field (24), resulting in a 512-bit block.
2. Dividing into Blocks:
   • The padded message is divided into 512-bit (64-byte) blocks. If the padded message is longer than 512 bits, it is split into multiple blocks.
   • Each block is processed sequentially, updating the hash state.
3. Initializing the MD5 Buffer:
   • MD5 uses a 128-bit hash state, represented as four 32-bit registers (A, B, C, D), initialized with fixed constants (in hexadecimal):
     • A = 0x67452301
     • B = 0xEFCDAB89
     • C = 0x98BADCFE
     • D = 0x10325476
   • These values are derived from the sine function and ensure a random starting point.
4. Compression Function:
   • Each 512-bit block is processed in 64 steps, grouped into four rounds of 16 steps each.
   • The block is divided into 16 32-bit words (M[0] to M[15]).
   • Each step involves:
     • A non-linear function (F, G, H, or I, varying by round) applied to B, C, and D.
     • Addition of a 32-bit word from the block (M[i]).
     • Addition of a round-specific constant (K[i]), derived from the sine function.
     • Left rotation by a fixed number of bits (s[i]).
     • Addition to register A, followed by updating the registers (A, B, C, D).
   • The non-linear functions are:
     • F(B, C, D) = (B AND C) OR (NOT B AND D) [Round 1]
     • G(B, C, D) = (B AND D) OR (C AND NOT D) [Round 2]
     • H(B, C, D) = B XOR C XOR D [Round 3]
     • I(B, C, D) = C XOR (B OR NOT D) [Round 4]
   • After 64 steps, the registers are updated by adding their initial values to the computed values, preparing for the next block or final output.
5. Output:
   • After processing all blocks, the final values of A, B, C, and D are concatenated (in little-endian format) to produce the 128-bit hash, typically represented as a 32-character hexadecimal string.

Example of MD5 Hashing

Let’s compute the MD5 hash for the input message “abc” (3 bytes or 24 bits) to illustrate the process:

1. Padding:
   • The message “abc” is 24 bits (3 bytes: 01100001 01100010 01100011 in ASCII).
   • Append a ‘1’ bit: 01100001 01100010 01100011 1 (25 bits).
   • Append 423 ‘0’ bits to reach 448 bits: 01100001 01100010 01100011 1 000…000 (448 bits).
   • Append the 64-bit length (24 in binary: 000…11000): Total length = 512 bits (one block).
2. Dividing into Blocks:
   • The padded message forms one 512-bit block.
3. Initialization:
   • Set registers: A = 0x67452301, B = 0xEFCDAB89, C = 0x98BADCFE, D = 0x10325476.
4. Compression:
   • The 512-bit block is divided into 16 32-bit words. For simplicity, assume the first word includes “abc” and padding bits.
   • Process the block in 64 steps across four rounds:
     • Round 1 (steps 0–15): Use function F, constants K[0..15], and rotations s[0..15].
     • Round 2 (steps 16–31): Use function G, with different word ordering.
     • Round 3 (steps 32–47): Use function H.
     • Round 4 (steps 48–63): Use function I.
   • Each step updates A, B, C, D using the formula: A = B + ((A + F(B, C, D) + M[i] + K[i]) <<< s[i]), where <<< denotes left rotation.
   • After 64 steps, add the initial register values to the computed values.
5. Output:
   • The final register values (in little-endian) are concatenated to produce the hash.
   • For “abc”, the MD5 hash is: 900150983cd24fb0d6963f7d28e17f72 (verified using standard MD5 tools).

Simplified Example for Clarity

For a small input like “a” (8 bits):

• Padding: Append ‘1’, 439 ‘0’s, and length (8), forming one 512-bit block.
• Initialization: Use standard constants.
• Compression: Process the block through 64 steps, updating registers.
• Output: The hash for “a” is 0cc175b9c0f1b6a831c399e269772661.

MD5 Vulnerabilities

MD5’s 128-bit hash is vulnerable to collision attacks, where two different inputs produce the same hash. In 2004, researchers demonstrated practical collisions, and by 2008, attacks like the Flame malware exploited MD5 weaknesses in certificate forging. NIST deprecated MD5 for secure applications, recommending SHA-2 or SHA-3. However, MD5 is still used for non-security purposes, like file checksums (e.g., verifying ISO downloads).

Applications

• File Integrity: MD5 checksums verify file downloads (e.g., Ubuntu ISO files).
• Legacy Systems: Used in older protocols or password hashing (though insecure).
• Forensic Analysis: Generates hashes for evidence integrity in digital forensics.

Educational Insights

For students, MD5 illustrates the principles of cryptographic hashing, including padding, block processing, and compression. Its vulnerabilities highlight the need for stronger algorithms like SHA-2, emphasizing the importance of collision resistance in secure systems.

Conclusion

MD5 transforms an input message into a 128-bit hash through padding, block division, initialization, compression, and output. Despite its efficiency, its collision vulnerabilities render it insecure for modern applications. Understanding MD5’s mechanics and limitations prepares students for designing and evaluating cryptographic systems.