Message digest functions convert sequences of bits, possibly quite long, called messages, into fixed-length binary "fingerprints" or message digests of the original sequences. See Figure 2-1. A message digest function has two goals:
Figure 2-1. Message digest function
In the common case where an authentication method takes a large amount of computational effort and that effort is proportional to the number of bits being authenticated, you can secure a large document by authenticating its much smaller fixed-size message digest.
A message digest function is not identical to a checksum. A checksum is usually quite simple and is designed to detect transmission errors or accidental changes. An adversary can deliberately circumvent the testing of a checksum by adjusting the message to leave the checksum unchanged. By comparison, a message digest is complex and is designed to defeat attempts by an adversary to change the message.
First, consider a checksum calculated by simply adding all octets in a message and discarding the bits of the sum above the least significant eight bits. In most cases, an adversary could easily modify the message to become a different message with the same checksum. For example, inserting an octet with value V into the message will have no effect on the checksum if you can also insert a second octet with value (256 - V) anywhere in the message.
Next, consider a more complex function in which you take the product of the octets in the message, adding to each octet its position in the message, and the check octet is the middle eight bits of this product. For example, if the message consists of bytes with values
then the check octet is the middle eight bits of
With this level of complexity, it is no longer quite so trivial for an adversary to figure out how to change the message without changing the check byte, although it can still be done. Cryptographically or computationally secure message digest functions are substantially more complex than this example, producing check quantities of at least 128 bits or 16 eight-bit bytes. They largely meet the following goals.
Expressing the goals of message digests more formally, if the message digest is N bits, then
Like other modern digital cryptographic functions, message digest functions are typically used and sometimes defined only for integer numbers of octets, rather than arbitrary numbers of bits.