2.2 Message Authentication Codes

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:

1. Have a different secret for every pair of entities. This method is logistically difficult because the number of keys increases with the square of the number of entities and the keys must be securely distributed. If the system includes E number of entities, you have E*(E 1)/2 pairs. For example, for 100 entities, you have 4950 pairs. For 1000 entities, you have 499,500 pairs.

2. Share one secret among all the entities. This technique is relatively insecure. The more entities that have a secret, the more likely the secret is to be compromised due to loss, subversion, or betrayal. This technique also means the same secret will be used many times; the more exposures of the uses of a secret, the easier an adversary may find it to break that secret analytically. In addition, with this strategy any of the entities can forge messages from any of the other entities and a recipient will be unable to detect this fraud based on the MAC.

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 2^N/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.