 Keyed hash functions (MACs)

Keyed hash functions whose specific purpose is message authentication are called message authentication code (MAC) algorithms. Compared to the large number of MDC algorithms, prior to 1995 relatively few MAC algorithms had been proposed, presumably because the original proposals, which were widely adopted in practice, were adequate. Many of these are for historical reasons block-cipher based. Those with relatively short MAC bitlengths (e.g., 32-bits for MAA) or short keys (e.g., 56 bits for MACs based on DES-CBC) may still offer adequate security, depending on the computational resources available to adversaries, and the particular environment of application.

Many iterated MACs can be described as iterated hash functions (see Figure 9.2, and equation (9.1) on page 333). In this case, the MAC key is generally part of the output transformation y it may also be an input to the compression function in the first iteration, and be involved in the compression function / at every stage.

Fact 9.57 is a general result giving an upper bound on the security of MACs.

9.57 Fact (birthday attack on MACs) Let h be a MAC algorithm based on an iterated compression function, which has n bits of internal chaining variable, and is deterministic (i.e., the m-bit result is fully determined by the message). Then MAC forgery is possible using 0(2"/2) known text-MAC pairs plus a number v of chosen text-MAC pairs which (depending on h) is between 1 and about 2n_m.

MACs based on block ciphers

CBC-based MACs

The most commonly used MAC algorithm based on a block cipher makes use of cipher- block-chaining (§7.2.2(h)). When DES is used as the block cipher E,n = 6 4 in what follows, and the MAC key is a 56-bit DES key.

9.58 Algorithm CBC-MAC

INPUT: data x; specification of block cipher E; secret MAC key к for E.

OUTPUT: n-bit MAC on x (n is the blocklength of E).

• 1. Padding and blocking. Pad x if necessary (e.g., using Algorithm 9.30). Divide the padded text into n-bit blocks denoted xi,... , xt.
• 2. CBC processing. Letting Ek denote encryption using E with key к, compute the block Ht as follows: IIi <- Ek(xi); If, <- Ek(Hi-i®Xi), 2 < i < t. (This is standard cipher-block-chaining, IV = 0, discarding ciphertext blocks С* = #2.)
• 3. Optional process to increase strength of MAC. Using a second secret key к' Ф к, optionally compute: H't <- Ef,l(Ht), Ht <- Ek{H't). (This amounts to using two- key triple-encryption on the last block; see Remark 9.59.)
• 4. Completion. The MAC is the ?r-bit block If. Figure 9.6: CBC-based MAC algorithm.

For CBC-MAC with n = 64 = m, Fact 9.57 applies with v = 1.

• 9.59 Remark (CBC-MAC strengthening) The optional process reduces the threat of exhaustive key search, and prevents chosen-text existential forgery (Example 9.62), without impacting the efficiency of the intermediate stages as would using two-key triple-encryption throughout. Alternatives to combat such forgery include prepending the input with a length block before the MAC computation; or using key К to encrypt the length m yielding K' = Ек(т), before using K' as the key to MAC the message.
• 9.60 Remark (truncated MAC outputs) Exhaustive attack may. depending on the unicity distance of the MAC, be precluded (information-theoretically) by using less than n bits of the final output as the m-bit MAC. (This must be traded off against an increase in the probability of randomly guessing the MAC; 2-m.) For m = 32 and E = DES, an exhaustive attack reduces the key space to about 224 possibilities. However, even for m < n, a second text-MAC pair almost certainly determines a unique MAC key.
• 9.61 Remark (CBC-MACIV) While a random IV in CBC encryption serves to prevent a codebook attack on the first ciphertext block, this is not a concern in a MAC algorithm.
• 9.62 Example {existential forgery of CBC-MAC) While CBC-MAC is secure for messages of a fixed number t of blocks, additional measures (beyond simply adding a trailing length- block) are required if variable length messages are allowed, otherwise (adaptive chosen- text) existential forgery is possible as follows. Assume xt is an n-bit block, and let ±b denote the n-bit binary representation of b. Let (x,Mi) be a known text-MAC pair, and request the MAC Л/2 for the one-block message a;2 = Mi', then M2 = Ek{Ek(x 1)) is also the MAC for the 2-block message (xi ||±0). As a less trivial example, given two known text-MAC pairs (x.H), (х2,Я2) for one-block messages x,x2, and requesting the MAC M on a chosen 2-block third message (xi ||z) for a third text-MAC pair ((xiz),M),thea Щ = Ek(xf), M = Ek{H®z), and the MAC for the new 2-block message X = Х2||(#1Ф-г®Я2) is known - it is M also. Moreover, MD-strengthening (Algorithm 9.26) does not address the problem: assume padding by Algorithm 9.29, replace the third message above by the 3-block message (a;i||-L64||z), note and М3 is also the MAC for the new 3-block message X = (ж211J.6411 Я[ S#2 Фz). □

9.63 Example (RIPE-MAC) RIPE-MAC is a variant of CBC-MAC. Two versions RIPE-

MAC1 and RIPE-MAC3, both producing 64-bit MACs, differ in their internal encryption function E being either single DES or two-key triple-DES, respectively, requiring a 56- or 112-bit key к (cf. Remark 9.59). Differences from Algorithm 9.58 are as follows: the compression function uses a non-invertible chaining best described as CBC with data feedforward: Hi <- El (H> — 1 фа.'г)фа.'г; after padding using Algorithm 9.30, a final 64-bit length-block (giving bitlength of original input) is appended; the optional process of Algorithm 9.58 is mandatory with final output block encrypted using key к' derived by complementing alternating nibbles of к: for к = k0 ■. - к63 a 56-bit DES key with parity bits Ытз • • • к(УЛ, к’ = к e oxfOfOfOfOfOfOforo. □