The MD2 Message-Digest Algorithm is a
cryptographic hash function
A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography:
* the probability of a particular n-bit output ...
developed by
Ronald Rivest in 1989.
The algorithm is optimized for
8-bit
In computer architecture, 8-bit integers or other data units are those that are 8 bits wide (1 octet). Also, 8-bit central processing unit (CPU) and arithmetic logic unit (ALU) architectures are those that are based on registers or data buses of ...
computers. MD2 is specified in
IETF RFC 1319.
The "MD" in MD2 stands for "Message Digest".
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
SHA-2 (Secure Hash Algorithm 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 compressi ...
and other strong hashing algorithms.
Nevertheless, , it remained in use in
public key infrastructure
A public key infrastructure (PKI) is a set of roles, policies, hardware, software and procedures needed to create, manage, distribute, use, store and revoke digital certificates and manage public-key encryption. The purpose of a PKI is to facil ...
s as part of
certificates generated with MD2 and
RSA
RSA may refer to:
Organizations Academia and education
* Rabbinical Seminary of America, a yeshiva in New York City
*Regional Science Association International (formerly the Regional Science Association), a US-based learned society
*Renaissance S ...
.
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
byte
The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable unit ...
s) and adding a 16-byte
checksum
A checksum is a small-sized block of data derived from another block of digital data for the purpose of detecting errors that may have been introduced during its transmission or storage. By themselves, checksums are often used to verify dat ...
to it. For the actual calculation, a 48-byte auxiliary block and a 256-byte
S-table. The constants were generated by shuffling the integers 0 through 255 using a variant of
Durstenfeld's algorithm with a
pseudorandom number generator
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
based on decimal digits of
(pi) (see
nothing up my sleeve number
In cryptography, nothing-up-my-sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and ciphers. These algorithms often need rand ...
). 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:
MD2 hashes
The 128-bit (16-byte) MD2 hashes (also termed ''message digests'') are typically represented as 32-digit
hexadecimal
In mathematics and computing, the hexadecimal (also base-16 or simply hex) numeral system is a positional numeral system that represents numbers using a radix (base) of 16. Unlike the decimal system representing numbers using 10 symbols, h ...
numbers. The following demonstrates a 43-byte
ASCII
ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Because ...
input and the corresponding MD2 hash:
MD2("The quick brown fox jumps over the lazy og") =
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 to in the message results in:
MD2("The quick brown fox jumps over the lazy og") =
6b890c9292668cdbbfda00a4ebf31f05
The hash of the zero-length string is:
MD2("") =
8350e5a3e24c153df2275c9f80692773
Security
Rogier and Chauvaud (1997) described collisions of MD2's
compression function, although they were unable to extend the attack to the full MD2.
In 2004, MD2 was shown to be vulnerable to a
preimage attack
In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage (set of possible inputs).
In the context of attack, the ...
with
time complexity
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
equivalent to 2
104 applications of the compression function.
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
In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage (set of possible inputs).
In the context of attack, the ...
with
time complexity
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
of 2
73 compression function evaluations and memory requirements of 2
73 message blocks.
In 2009, MD2 was shown to be vulnerable to a
collision attack
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.
There are roug ...
with
time complexity
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
of 2
63.3 compression function evaluations and memory requirements of 2
52 hash values. This is slightly better than the
birthday attack which is expected to take 2
65.5 compression function evaluations.
In 2009, security updates were issued disabling MD2 in
OpenSSL
OpenSSL is a software library for applications that provide secure communications over computer networks against eavesdropping or need to identify the party at the other end. It is widely used by Internet servers, including the majority of HT ...
,
GnuTLS
GnuTLS (, the GNU Transport Layer Security Library) is a free software implementation of the TLS, SSL and DTLS protocols. It offers an application programming interface (API) for applications to enable secure communication over the network tra ...
, and
Network Security Services
Network Security Services (NSS) is a collection of cryptographic computer libraries designed to support cross-platform development of security-enabled client and server applications with optional support for hardware TLS/SSL acceleration on the ...
.
See also
*
Hash function security summary
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.
Table color key
...
*
Comparison of cryptographic hash functions
*
MD4
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" ...
*
MD5
*
MD6
*
SHA-1
In cryptography, SHA-1 (Secure Hash Algorithm 1) is a cryptographically broken but still widely used hash function which takes an input and produces a 160-bit (20- byte) hash value known as a message digest – typically rendered as 40 hexadec ...
References
Further reading
*
*
*
External links
{{Cryptography navbox , hash
Broken hash functions