2.1 Message Digests

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:

• It should be computationally infeasible to find another message whose digest is the same as the digest of a given message.

• It should be computationally infeasible to find two arbitrary messages whose digests are the same.

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

1. To find a second message with the same message digest as a given message, no method should require an expected effort significantly less than trying 2^N-1 possible other messages;

2. To find two arbitrary messages with the same message digest, no method should require an expected effort significantly less than trying 2^N/2 messages, remembering all their digests, and looking for a match.

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.