Cryptography and Network Security (4th Edition)

11.3. Message Authentication Codes

A MAC, also known as a cryptographic checksum, is generated by a function C of the form

MAC = C(K, M)

where M is a variable-length message, K is a secret key shared only by sender and receiver, and C(K, M) is the fixed-length authenticator. The MAC is appended to the message at the source at a time when the message is assumed or known to be correct. The receiver authenticates that message by recomputing the MAC.

In this section, we review the requirements for the function C and then examine a specific example. Other examples are discussed in Chapter 12.

Requirements for MACs

When an entire message is encrypted for confidentiality, using either symmetric or asymmetric encryption, the security of the scheme generally depends on the bit length of the key. Barring some weakness in the algorithm, the opponent must resort to a brute-force attack using all possible keys. On average, such an attack will require 2^(k-1) attempts for a k-bit key. In particular, for a ciphertext-only attack, the opponent, given ciphertext C, would perform P_i = D(K_i, C) for all possible key values K_i until a P_i was produced that matched the form of acceptable plaintext.

In the case of a MAC, the considerations are entirely different. In general, the MAC function is a many-to-one function, due to the many-to-one nature of the function. Using brute-force methods, how would an opponent attempt to discover a key? If confidentiality is not employed, the opponent has access to plaintext messages and their associated MACs. Suppose k > n; that is, suppose that the key size is greater than the MAC size. Then, given a known M₁ and MAC₁, with MAC₁ = C(K, M₁), the cryptanalyst can perform MAC_i = C(K_i, M₁) for all possible key values K_i. At least one key is guaranteed to produce a match of MAC_i = MAC₁. Note that a total of 2^k MACs will be produced, but there are only 2ⁿ < 2^k different MAC values. Thus, a number of keys will produce the correct MAC and the opponent has no way of knowing which is the correct key. On average, a total of 2^k/2ⁿ = 2^(k-n) keys will produce a match. Thus, the opponent must iterate the attack:

• Round 1

  Given: M₁, MAC₁ = C(K, M₁)

  Compute MAC_i = C(K_i, M₁) for all 2^k keys

  Number of matches 2⁽ⁿ⁾

• Round 2

  Given: M₂, MAC₂ = C(K, M₂)

  Compute MAC_i = C(K_i, M₂) for the 2^(k-n) keys resulting from Round 1

  Number of matches 2⁽ⁿ⁾

and so on. On average, a rounds will be needed if k = a x n. For example, if an 80-bit key is used and the MAC is 32 bits long, then the first round will produce about 2⁴⁸ possible keys. The second round will narrow the possible keys to about 2¹⁶ possibilities. The third round should produce only a single key, which must be the one used by the sender.

If the key length is less than or equal to the MAC length, then it is likely that a first round will produce a single match. It is possible that more than one key will produce such a match, in which case the opponent would need to perform the same test on a new (message, MAC) pair.

Thus, a brute-force attempt to discover the authentication key is no less effort and may be more effort than that required to discover a decryption key of the same length. However, other attacks that do not require the discovery of the key are possible.

Consider the following MAC algorithm. Let M = (X₁||X₂||...||X_m) be a message that is treated as a concatenation of 64-bit blocks X_i. Then define

where is the exclusive-OR (XOR) operation and the encryption algorithm is DES in electronic codebook mode. Thus, the key length is 56 bits and the MAC length is 64 bits. If an opponent observes {K, M)}, a brute-force attempt to determine K will require at least 2⁵⁶ encryptions. But the opponent can attack the system by replacing X₁ through X_m-1 with any desired values Y₁ through Y_m-1 and replacing X_m with Y_m where Y_m is calculated as follows:

Y_m = Y₁ ... m1 D(M)

The opponent can now concatenate the new message, which consists of Y₁ through Y_m, with the original MAC to form a message that will be accepted as authentic by the receiver. With this tactic, any message of length 64 x (m 1) bits can be fraudulently inserted.

Thus, in assessing the security of a MAC function, we need to consider the types of attacks that may be mounted against it. With that in mind, let us state the requirements for the function. Assume that an opponent knows the MAC function C but does not know K. Then the MAC function should satisfy the following requirements:

1. If an opponent observes M and C(K, M), it should be computationally infeasible for the opponent to construct a message M' such that C(K, M') = C(K, M).

2. C(K, M) should be uniformly distributed in the sense that for randomly chosen messages, M and M', the probability that C(K, M) = C(K, M') is 2ⁿ, where n is the number of bits in the MAC.

3. Let M' be equal to some known transformation on M. That is, M' = f(M). For example, f may involve inverting one or more specific bits. In that case, Pr[C(K, M) = C(K, M')] = 2ⁿ.

The first requirement speaks to the earlier example, in which an opponent is able to construct a new message to match a given MAC, even though the opponent does not know and does not learn the key. The second requirement deals with the need to thwart a brute-force attack based on chosen plaintext. That is, if we assume that the opponent does not know K but does have access to the MAC function and can present messages for MAC generation, then the opponent could try various messages until finding one that matches a given MAC. If the MAC function exhibits uniform distribution, then a brute-force method would require, on average, 2⁽ⁿ¹⁾ attempts before finding a message that fits a given MAC.

The final requirement dictates that the authentication algorithm should not be weaker with respect to certain parts or bits of the message than others. If this were not the case, then an opponent who had M and C(K, M) could attempt variations on M at the known "weak spots" with a likelihood of early success at producing a new message that matched the old MAC.

Message Authentication Code Based on DES

The Data Authentication Algorithm, based on DES, has been one of the most widely used MACs for a number of years. The algorithm is both a FIPS publication (FIPS PUB 113) and an ANSI standard (X9.17). However, as we discuss in Chapter 12, security weaknesses in this algorithm have been discovered and it is being replaced by newer and stronger algorithms.

The algorithm can be defined as using the cipher block chaining (CBC) mode of operation of DES (Figure 6.4) with an initialization vector of zero. The data (e.g., message, record, file, or program) to be authenticated are grouped into contiguous 64-bit blocks: D₁, D₂,..., D_N. If necessary, the final block is padded on the right with zeroes to form a full 64-bit block. Using the DES encryption algorithm, E, and a secret key, K, a data authentication code (DAC) is calculated as follows (Figure 11.6):

The DAC consists of either the entire block O_N or the leftmost M bits of the block, with 16 64.