Section 11.3. Message Authentication Codes
11.3. Message Authentication CodesA 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 MACsWhen 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 Pi = D(Ki, C) for all possible key values Ki until a Pi 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 M1 and MAC1, with MAC1 = C(K, M1), the cryptanalyst can perform MACi = C(Ki, M1) for all possible key values Ki. At least one key is guaranteed to produce a match of MACi = MAC1. Note that a total of 2k MACs will be produced, but there are only 2n < 2k 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 2k/2n = 2(k-n) keys will produce a match. Thus, the opponent must iterate the attack:
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 248 possible keys. The second round will narrow the possible keys to about 216 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 = (X1||X2||...||Xm) be a message that is treated as a concatenation of 64-bit blocks Xi. Then define
where Ym = Y1 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). 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 2n, where n is the number of bits in the MAC. 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')] = 2n. 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(n1) 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 DESThe 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: D1, D2,..., DN. 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):
Figure 11.6. Data Authentication Algorithm (FIPS PUB 113) The DAC consists of either the entire block ON or the leftmost M bits of the block, with 16 |
2(
EAN: 2147483647
Pages: 209