A message authentication code (MAC) function computes a MAC from a message and a secret key. If the originator and the receiver share knowledge of that secret key, the receiver can calculate the same function of the message and secret key and see if it matches the MAC accompanying the message. See Figure 2-2. If the MAC matches, then you know, within the strength of the MAC function and key, that some program with possession of the secret produced the MAC. Of course, every program that can verify the MAC needs to know this secret. Thus all of them can create valid MACs even if they should only receive and verify these codes.
Figure 2-2. Message authentication codes
A simple MAC function might append the secret to the message, then calculate a message digest of the result and use it as the MAC. The message (without the secret) and MAC could then be sent to the recipient. The recipient would also append the secret (which the receiver needs to know as well) to the message and calculate the same message digest function. If the resulting digest matches the MAC, it validates the message.
MACs are normally based on a message digest code; however, the simple technique suggested previously has subtle weaknesses that are beyond the scope of this book. Better, stronger MAC functions exist. All of the MAC functions discussed in this book (see Chapter 18) are based on the provable "security" HMAC [RFC 2104] method of combining a message, secret quantity, and message digest function to produce a MAC. [Schneier] documents other strong MAC functions as well.
A difficulty with MAC authentication in a system with multiple originators and receivers is that you must choose between two strategies, both of which have problems:
Digital signatures, as described in Section 2.6, are an operationally superior method of authentication in many circumstances.
As with message digest functions, if a strong MAC is N bits long, the difficulty of finding two messages with the same MAC is proportional to 2N/2. You should pick N large enough for your application and then, to avoid the secret quantity being the weak point, use a secret quantity that is random (see Section 2.10) and at least N/2 bits long. For example, if you need a 160-bit MAC, the secret key should be at least 80 random bits.