MD4
Overview
The MD4 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit (16-byte) hash value. It is commonly used to verify data integrity. MD4 was designed by Ronald Rivest in 1990 to replace an earlier hash function, MD2. With the advent of more powerful computers, it was found to be vulnerable to extensive cryptanalytic attacks and is now considered to be broken.
Design and Functionality
MD4 is designed to take an input (or 'message') and produce a fixed-size output of 128 bits. The input message is broken up into chunks of 512-bit blocks; the message is padded so that its length is divisible by 512. The padding works as follows: first, a single bit, 1, is appended to the end of the message. This is followed by as many zeros as are required to bring the length of the message up to 64 bits fewer than a multiple of 512. The remaining bits are filled up with 64 bits representing the length of the original message, modulo 2^64.
The main algorithm operates on a 128-bit state, divided into four 32-bit words, denoted A, B, C and D. These are initialized to certain fixed constants. The main algorithm then operates on each 512-bit message block in turn, each block modifying the state. The processing of a message block consists of three identical stages, each composed of four rounds; each round composed of 16 operations based on a non-linear function F, modular addition, and left rotation. As each round has a different function, they are denoted F, G and H.
Vulnerabilities and Cryptanalysis
MD4 was initially thought to be very secure, but numerous vulnerabilities were found that led to its deprecation in favor of stronger hash functions. The first major flaw in MD4 was published in 1995, only five years after its introduction. This was followed by a series of increasingly effective attacks, culminating in a full break of the MD4 hash function.
The most significant vulnerability is that the hash function is not collision-resistant; as such, it is possible to find two different inputs that hash to the same output. This property is a fundamental requirement of any cryptographic hash function. The lack of collision-resistance in MD4 allows an attacker to create two different documents with the same hash, a scenario that could have serious implications for document integrity verification systems.
Legacy and Usage
Despite its vulnerabilities, MD4 has had a significant impact on the design of later cryptographic primitives. Its design principles, particularly the use of bitwise operations and modular arithmetic, have influenced the design of newer hash functions, including those in the MD family like MD5 and SHA-1.
MD4 is still used in some systems for non-cryptographic purposes, such as checksumming, due to its simplicity and speed. However, for any application requiring a high level of security, MD4 is not recommended.