MD2 is a cryptographic hash function. It was developed by Ronald Rivest in 1989 and described in RFC 1319. The input is a message of arbitrary length. The hash size is 128 bits. Currently, the MD2 algorithm is considered obsolete, and the corresponding RFC 1319 has been transferred to historical status.
History of creation
Ronald Rivest developed a series of hashing algorithms called MDx, where x is the sequence number of the algorithm. MD1 is a proprietary algorithm whose specification has not been published. MD2 was developed in 1989 for use as one of the cryptographic algorithms included in the PEM Privacy-Enhanced Mail secure e-mail standard. In 1990, MD2 was proposed as a replacement for the BMAC Bidirectional MAC. Subsequently, the specification and updated implementation of MD2 were published in RFC 1319. MD3 was never published. The development of MD3 was abandoned. After MD2, MD4, MD5, and MD6 were developed in 1990, 1991, and 2008, respectively. In 2011, MD2 was officially decommissioned due to numerous successful crypto attacks. Currently, MD2 is only recommended for compatibility with older programs that still rely on it.
Safety
MD2 author Ronald Rivest suggested that:
the complexity of the task of searching for a preimage by a known hash sum is of the order of 2/128 operations;
the complexity of the problem of finding a collision of two messages with the same hash sum is of the order of 2/64 operations.
In 1994, Bruce Schneier wrote about the MD2 algorithm that, although slower than other hashing algorithms, was cryptographically strong at the time. Since then, cryptanalysts have made significant progress in analyzing MD2. The algorithm is now considered hacked.
MD2 cryptanalysis
In 1993, Bart Prenel noted in his work that since the last 32 bytes of the algorithm buffer are not used in the output hash value. It is possible to skip updating these bytes in the latest iteration of the buffer for the last block of input data. The same work notes that the number of rounds of the algorithm 18 by only one round exceeds the minimum possible for the output value of the algorithm to reach all possible 2/128 options. Therefore, we can conclude that the cryptographic strength of the algorithm is minimal and that it is impossible to increase the hash rate by reducing the number of rounds without loss of strength.
Bart Prenel also proposed a methodology for attacking full-round MD2 using differential cryptanalysis but did not describe specific attacks on the algorithm.
In 1995, a collision detection method was proposed, but it was not successful due to a checksum appended to the end of the message. In some works, it was noted that due to the original design of the MD2 algorithm, the well-known results of cryptanalysis of hash functions with a classical structure do not apply to this algorithm. However, back in 1996, RSA recommended not using the MD2 algorithm in cases where collision-free behavior is required. Otherwise, MD2 remained secure.
Roger and Chaveau published an example of collisions for MD2 in 1997, although they could not provide an algorithm for finding other collisions.
The first attack on MD in 2004 was proposed by Frederich Müller. makes. He made it possible to find a preimage with a laboriousness of 2/104 operations, which is significantly less than the theoretical complexity of searching for a preimage for MD2, which is 2/128 operations. Müller stated: “MD2 can no longer be seen as a cryptographically strong hashing algorithm.” Although the complexity of the attack was still too large for the possibility of carrying out this attack in practice.
In 2005, Lars Knudsen and John Mathiassen significantly improved Mueller’s results. The proposed attacks not only reduced the complexity of attacks but also allowed finding the desired messages of varying length, while Mueller’s attacks allowed only preimages of 128 blocks of 16 bytes to be found.
The next big step in MD2 cryptanalysis was taken by Soren Thomsen in 2008. He managed to reduce the complexity of the task of searching for a preimage to 2/73 operations, which brought this attack closer to the status of being implemented in practice. A year later, having joined forces, the authors of previous works improved the results of the collision search attack, reaching a complexity of 2/63.3 operations, which is slightly below the theoretical 2/64.
