MD2 (hash function)

Last updated

MD2
General
Designers Ronald Rivest
First publishedAugust 1989 [1]
SeriesMD2, MD4, MD5, MD6
Detail
Digest sizes 128 bits
Rounds 18

The MD2 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1989. [2] The algorithm is optimized for 8-bit computers. MD2 is specified in IETF RFC 1319. [3] The "MD" in MD2 stands for "Message Digest".

Contents

Even though MD2 is not yet fully compromised, the IETF retired MD2 to "historic" status in 2011, citing "signs of weakness". It is deprecated in favor of SHA-256 and other strong hashing algorithms. [4]

Nevertheless, as of 2014, it remained in use in public key infrastructures as part of certificates generated with MD2 and RSA.

Description

The 128-bit hash value of any message is formed by padding it to a multiple of the block length (128 bits or 16 bytes) and adding a 16-byte checksum to it. For the actual calculation, a 48-byte auxiliary block and a 256-byte S-table are used. The constants were generated by shuffling the integers 0 through 255 using a variant of Durstenfeld's algorithm with a pseudorandom number generator based on decimal digits of π (pi) [3] [5] (see nothing up my sleeve number). The algorithm runs through a loop where it permutes each byte in the auxiliary block 18 times for every 16 input bytes processed. Once all of the blocks of the (lengthened) message have been processed, the first partial block of the auxiliary block becomes the hash value of the message.

The S-table values in hex are:

{ 0x29, 0x2E, 0x43, 0xC9, 0xA2, 0xD8, 0x7C, 0x01, 0x3D, 0x36, 0x54, 0xA1, 0xEC, 0xF0, 0x06, 0x13,    0x62, 0xA7, 0x05, 0xF3, 0xC0, 0xC7, 0x73, 0x8C, 0x98, 0x93, 0x2B, 0xD9, 0xBC, 0x4C, 0x82, 0xCA,    0x1E, 0x9B, 0x57, 0x3C, 0xFD, 0xD4, 0xE0, 0x16, 0x67, 0x42, 0x6F, 0x18, 0x8A, 0x17, 0xE5, 0x12,    0xBE, 0x4E, 0xC4, 0xD6, 0xDA, 0x9E, 0xDE, 0x49, 0xA0, 0xFB, 0xF5, 0x8E, 0xBB, 0x2F, 0xEE, 0x7A,    0xA9, 0x68, 0x79, 0x91, 0x15, 0xB2, 0x07, 0x3F, 0x94, 0xC2, 0x10, 0x89, 0x0B, 0x22, 0x5F, 0x21,   0x80, 0x7F, 0x5D, 0x9A, 0x5A, 0x90, 0x32, 0x27, 0x35, 0x3E, 0xCC, 0xE7, 0xBF, 0xF7, 0x97, 0x03,    0xFF, 0x19, 0x30, 0xB3, 0x48, 0xA5, 0xB5, 0xD1, 0xD7, 0x5E, 0x92, 0x2A, 0xAC, 0x56, 0xAA, 0xC6,    0x4F, 0xB8, 0x38, 0xD2, 0x96, 0xA4, 0x7D, 0xB6, 0x76, 0xFC, 0x6B, 0xE2, 0x9C, 0x74, 0x04, 0xF1,    0x45, 0x9D, 0x70, 0x59, 0x64, 0x71, 0x87, 0x20, 0x86, 0x5B, 0xCF, 0x65, 0xE6, 0x2D, 0xA8, 0x02,    0x1B, 0x60, 0x25, 0xAD, 0xAE, 0xB0, 0xB9, 0xF6, 0x1C, 0x46, 0x61, 0x69, 0x34, 0x40, 0x7E, 0x0F,    0x55, 0x47, 0xA3, 0x23, 0xDD, 0x51, 0xAF, 0x3A, 0xC3, 0x5C, 0xF9, 0xCE, 0xBA, 0xC5, 0xEA, 0x26,    0x2C, 0x53, 0x0D, 0x6E, 0x85, 0x28, 0x84, 0x09, 0xD3, 0xDF, 0xCD, 0xF4, 0x41, 0x81, 0x4D, 0x52,    0x6A, 0xDC, 0x37, 0xC8, 0x6C, 0xC1, 0xAB, 0xFA, 0x24, 0xE1, 0x7B, 0x08, 0x0C, 0xBD, 0xB1, 0x4A,    0x78, 0x88, 0x95, 0x8B, 0xE3, 0x63, 0xE8, 0x6D, 0xE9, 0xCB, 0xD5, 0xFE, 0x3B, 0x00, 0x1D, 0x39,    0xF2, 0xEF, 0xB7, 0x0E, 0x66, 0x58, 0xD0, 0xE4, 0xA6, 0x77, 0x72, 0xF8, 0xEB, 0x75, 0x4B, 0x0A,    0x31, 0x44, 0x50, 0xB4, 0x8F, 0xED, 0x1F, 0x1A, 0xDB, 0x99, 0x8D, 0x33, 0x9F, 0x11, 0x83, 0x14 }

MD2 hashes

The 128-bit (16-byte) MD2 hashes (also termed message digests) are typically represented as 32-digit hexadecimal numbers. The following demonstrates a 43-byte ASCII input and the corresponding MD2 hash:

 MD2("The quick brown fox jumps over the lazy dog") =   03d85a0d629d2c442e987525319fc471

As the result of the avalanche effect in MD2, even a small change in the input message will (with overwhelming probability) result in a completely different hash. For example, changing the letter d to c in the message results in:

 MD2("The quick brown fox jumps over the lazy cog") =   6b890c9292668cdbbfda00a4ebf31f05

The hash of the zero-length string is:

 MD2("") =   8350e5a3e24c153df2275c9f80692773

Security

Rogier and Chauvaud presented in 1995 [6] collisions of MD2's compression function, although they were unable to extend the attack to the full MD2. The described collisions was published in 1997. [7]

In 2004, MD2 was shown to be vulnerable to a preimage attack with time complexity equivalent to 2104 applications of the compression function. [8] The author concludes, "MD2 can no longer be considered a secure one-way hash function".

In 2008, MD2 has further improvements on a preimage attack with time complexity of 273 compression function evaluations and memory requirements of 273 message blocks. [9]

In 2009, MD2 was shown to be vulnerable to a collision attack with time complexity of 263.3 compression function evaluations and memory requirements of 252 hash values. This is slightly better than the birthday attack which is expected to take 265.5 compression function evaluations. [10]

In 2009, security updates were issued disabling MD2 in OpenSSL, GnuTLS, and Network Security Services. [11]

See also

Related Research Articles

<span class="mw-page-title-main">HMAC</span> Computer communications hash algorithm

In cryptography, an HMAC is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and authenticity of a message. An HMAC is a type of keyed hash function that can also be used in a key derivation scheme or a key stretching scheme.

The MD5 message-digest algorithm is a widely used hash function producing a 128-bit hash value. MD5 was designed by Ronald Rivest in 1991 to replace an earlier hash function MD4, and was specified in 1992 as RFC 1321.

In cryptography, SHA-1 is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard. The algorithm has been cryptographically broken but is still widely used.

Articles related to cryptography include:

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

In cryptography, Tiger is a cryptographic hash function designed by Ross Anderson and Eli Biham in 1995 for efficiency on 64-bit platforms. The size of a Tiger hash value is 192 bits. Truncated versions can be used for compatibility with protocols assuming a particular hash size. Unlike the SHA-2 family, no distinguishing initialization values are defined; they are simply prefixes of the full Tiger/192 hash value.

<span class="mw-page-title-main">MD4</span> Cryptographic hash function

The MD4 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1990. The digest length is 128 bits. The algorithm has influenced later designs, such as the MD5, SHA-1 and RIPEMD algorithms. The initialism "MD" stands for "Message Digest".

In cryptography, a collision attack on a cryptographic hash tries to find two inputs producing the same hash value, i.e. a hash collision. This is in contrast to a preimage attack where a specific target hash value is specified.

In cryptography, PBKDF1 and PBKDF2 are key derivation functions with a sliding computational cost, used to reduce vulnerability to brute-force attacks.

In cryptography, Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway, and subsequently standardized in PKCS#1 v2 and RFC 2437.

SHA-2 is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression function itself built using the Davies–Meyer structure from a specialized block cipher.

<span class="mw-page-title-main">Merkle–Damgård construction</span> Method of building collision-resistant cryptographic hash functions

In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. This construction was used in the design of many popular hash algorithms such as MD5, SHA-1 and SHA-2.

In public-key cryptography, a public key fingerprint is a short sequence of bytes used to identify a longer public key. Fingerprints are created by applying a cryptographic hash function to a public key. Since fingerprints are shorter than the keys they refer to, they can be used to simplify certain key management tasks. In Microsoft software, "thumbprint" is used instead of "fingerprint."

Grøstl is a cryptographic hash function submitted to the NIST hash function competition by Praveen Gauravaram, Lars Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, and Søren S. Thomsen. Grøstl was chosen as one of the five finalists of the competition. It uses the same S-box as AES in a custom construction. The authors claim speeds of up to 21.4 cycles per byte on an Intel Core 2 Duo, and 9.6 cycles/byte on an Intel i7 with AES-NI.

The following tables compare general and technical information for a number of cryptographic hash functions. See the individual functions' articles for further information. This article is not all-inclusive or necessarily up-to-date. An overview of hash function security/cryptanalysis can be found at hash function security summary.

The following outline is provided as an overview of and topical guide to cryptography:

This article summarizes publicly known attacks against cryptographic hash functions. Note that not all entries may be up to date. For a summary of other hash function parameters, see comparison of cryptographic hash functions.

BLAKE is a cryptographic hash function based on Daniel J. Bernstein's ChaCha stream cipher, but a permuted copy of the input block, XORed with round constants, is added before each ChaCha round. Like SHA-2, there are two variants differing in the word size. ChaCha operates on a 4×4 array of words. BLAKE repeatedly combines an 8-word hash value with 16 message words, truncating the ChaCha result to obtain the next hash value. BLAKE-256 and BLAKE-224 use 32-bit words and produce digest sizes of 256 bits and 224 bits, respectively, while BLAKE-512 and BLAKE-384 use 64-bit words and produce digest sizes of 512 bits and 384 bits, respectively.

Streebog is a cryptographic hash function defined in the Russian national standard GOST R 34.11-2012 Information Technology – Cryptographic Information Security – Hash Function. It was created to replace an obsolete GOST hash function defined in the old standard GOST R 34.11-94, and as an asymmetric reply to SHA-3 competition by the US National Institute of Standards and Technology. The function is also described in RFC 6986 and one out of hash functions in ISO/IEC 10118-3:2018.

Kupyna is a cryptographic hash function defined in the Ukrainian national standard DSTU 7564:2014. It was created to replace an obsolete GOST hash function defined in the old standard GOST 34.11-95, similar to Streebog hash function standardized in Russia.

References

  1. ↑ Linn, John (August 1989). "RSA-MD2 Message Digest Algorithm". Privacy Enhancement for Internet Electronic Mail: Part III — Algorithms, Modes, and Identifiers. Rivest, Ron. IETF. sec. 4.2. doi: 10.17487/RFC1115 . RFC 1115 . Retrieved 26 April 2021.
  2. ↑ RSA Laboratories. "What are MD2, MD4, and MD5?". Public-Key Cryptography Standards (PKCS): PKCS #7: Cryptographic Message Syntax Standard. RSA Laboratories. Archived from the original on 16 January 2017.
  3. 1 2 Kaliski, Burt (April 1992). The MD2 Message-Digest Algorithm. IETF. p. 3. doi: 10.17487/RFC1319 . RFC 1319 . Retrieved 22 November 2014.
  4. ↑ RFC   6149, MD2 to Historic Status
  5. ↑ "How is the MD2 hash function S-table constructed from Pi?". Cryptography Stack Exchange. Stack Exchange. 2 August 2014. Retrieved 23 May 2021.
  6. ↑ Rogier, N.; Chauvaud, Pascal (18–19 May 1995). The Compression Function of MD2 is not Collision Free. Selected Areas in Cryptography (SAC) 1995, Ottawa, Canada (workshop record).
  7. ↑ Rogier, N.; Chauvaud, Pascal (1997). "MD2 is not Secure without the Checksum Byte". Designs, Codes and Cryptography. 12 (3): 245–251. doi:10.1023/A:1008220711840. S2CID   21613457.
  8. ↑ Muller, Frédéric (2004). The MD2 Hash Function is Not One-Way (PDF). ASIACRYPT 2004. pp. 214–229. doi: 10.1007/978-3-540-30539-2_16 . Retrieved 26 April 2021– via International Association for Cryptologic Research.
  9. ↑ Thomsen, Søren S. (2008). "An Improved Preimage Attack on MD2" (PDF).{{cite journal}}: Cite journal requires |journal= (help)
  10. ↑ Knudsen, Lars R.; Mathiassen, John Erik; Muller, Frédéric; Thomsen, Søren S. (2009). "Cryptanalysis of MD2". Journal of Cryptology. 23: 72–90. doi: 10.1007/s00145-009-9054-1 . S2CID   2443076.
  11. ↑ CVE - 2009-2409

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.