MD5

In 1993, Den Boer and Bosselaers gave an early, although limited, result of finding a "pseudo-collision" of the MD5 compression function; that is, two different initialization vectors that produce an identical digest.

While this was not an attack on the full MD5 hash function, it was close enough for cryptographers to recommend switching to a replacement, such as SHA-1 (also compromised since) or RIPEMD-160.

MD5CRK was a distributed project started in March 2004 to demonstrate that MD5 is practically insecure by finding a collision using a birthday attack.

MD5CRK ended shortly after 17 August 2004, when collisions for the full MD5 were announced by Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu.

A few days later, Vlastimil Klima described an improved algorithm, able to construct MD5 collisions in a few hours on a single notebook computer.

[9] On 18 March 2006, Klima published an algorithm that could find a collision within one minute on a single notebook computer, using a method he calls tunneling.

In 2009, the United States Cyber Command used an MD5 hash value of their mission statement as a part of their official emblem.

Marc Stevens responded to the challenge and published colliding single-block messages as well as the construction algorithm and sources.

On 31 December 2008, the CMU Software Engineering Institute concluded that MD5 was essentially "cryptographically broken and unsuitable for further use".

[21] These hash and collision attacks have been demonstrated in the public in various situations, including colliding document files[22][23] and digital certificates.

While it was not deemed a fatal weakness at the time, cryptographers began recommending the use of other algorithms, such as SHA-1, which has since been found to be vulnerable as well.

Researchers additionally discovered more serious flaws in MD5, and described a feasible collision attack—a method to create a pair of inputs for which MD5 produces identical checksums.

[24][30] As of 2010, the CMU Software Engineering Institute considers MD5 "cryptographically broken and unsuitable for further use",[31] and most U.S. government applications now require the SHA-2 family of hash functions.

[39] Although Verisign declined to revoke existing certificates signed using MD5, their response was considered adequate by the authors of the exploit (Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, and Benne de Weger).

Furthermore, current collision-finding techniques allow specifying an arbitrary prefix: an attacker can create two colliding files that both begin with the same content.

[43][44] MD5 digests have been widely used in the software world to provide some assurance that a transferred file has arrived intact.

This method can be used to replace the Bates stamp numbering system that has been used for decades during the exchange of paper documents.

The main MD5 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.

Instead of the formulation from the original RFC 1321 shown, the following may be used for improved efficiency (useful if assembly language is being used – otherwise, the compiler will generally optimize the above code.

Since each computation is dependent on another in these formulations, this is often slower than the above method where the nand/and can be parallelised): The 128-bit (16-byte) MD5 hashes (also termed message digests) are typically represented as a sequence of 32 hexadecimal digits.

Diagram showing use of MD5 hashing in file transmission
Diagram showing use of MD5 hashing in file transmission
Figure 1. One MD5 operation. MD5 consists of 64 of these operations, grouped in four rounds of 16 operations. F is a nonlinear function; one function is used in each round. M i denotes a 32-bit block of the message input, and K i denotes a 32-bit constant, different for each operation. <<< s denotes a left bit rotation by s places; s varies for each operation. denotes addition modulo 2 32 .