12.5 Message Authentication Codes – Introduction to Cryptography with Coding Theory, 3rd Edition

12.5 Message Authentication Codes

When Alice sends a message to Bob, two important considerations are

  1. Is the message really from Alice?

  2. Has the message been changed during transmission?

Message authentication codes (MAC) solve these problems. Just as is done with digital signatures, Alice creates an appendix, the MAC, that is attached to the message. Thus, Alice sends (m, MAC) to Bob.

12.5.1 HMAC

One of the most commonly used is HMAC (= Hashed MAC), which was invented in 1996 by Mihir Bellare, Ran Canetti, and Hugo Krawczyk and is used in the IPSec and TLS protocols for secure authenticated communications.

To set up the protocol, we need a hash function H. For concreteness, assume that H processes messages in blocks of 512 bits. Alice and Bob need to share a secret key K. If K is shorter than 512 bits, append enough 0s to make its length be 512. If K is longer than 512 bits, it can be hashed to obtain a shorter key, so we assume that K has 512 bits.

We also form innerpadding and outerpadding strings:

opad = 5C5C5C … 5C, ipad = 363636 … 36,

which are binary strings of length 512, expressed in hexadecimal (5=0101, C=1100, etc.).

Let m be the message. Then Alice computes

HMAC(m, K)=H((Kopad)||H((Kipad)||m)).

In other words, Alice first does the natural step of computing H((Kipad)||m). But, as pointed out in Section 11.3, this is susceptible to length extension attacks for hash functions based on the Merkle-Damgård construction. So she prepends Kopad and hashes again. This seems to be resistant to all known attacks.

Alice now sends the message m, either encrypted or not, along with HMAC(m, K), to Bob. Since Bob knows K, he can compute HMAC(m, K). If it agrees with the value that Alice sent, he assumes that the message is from Alice and that it is the message that Alice sent.

If Eve tries to change m to m, then H(Kipad||m) should differ from H(Kipad||m) (collision resistance) and therefore HMAC(m, K) should differ from HMAC(K, m) (again, by collision resistance). Therefore, HMAC(m, K) tells Bob that the message is authentic. Also, it seems unlikely that Eve can authenticate a message m without knowing K, so Bob is sure that Alice sent the message.

For an analysis of the security of HMAC, see [Bellare et al.]

12.5.2 CBC-MAC

An alternative to using hash functions is to use a block cipher in CBC mode. Let EK() be a block cipher, such as AES, using a secret key K that is shared between Alice and Bob. We may create an appendix very similar to the output of a keyed hash function by applying EK() in CBC mode to the entire message m and using the final output of the CBC operation as the MAC.

Suppose that our message m is of the form m=(m1, m2, , ml), where each mj is a block of the message that has the same length as the block length of the encryption algorithm EK(). The last block ml may require padding in order to guarantee that it is a full block. Recall that the CBC encryption procedure is given by

Cj=EK(mjCj1)j=1, 2, , l, 

where C0=IV is the initialization vector. The CBC-MAC is then given as

MAC=(IV, Cl)

and Alice then sends Bob (m, MAC).

CBC-MAC has many of the same concerns as keyed hash functions. For example, CBC-MAC also suffers from its own form of length extension attacks. Let MAC(a) correspond to the CBC-MAC of a message a. Suppose that Eve has found two messages a and b with MAC(a)=MAC(b). Then Eve knows that MAC(a, x)=MAC(b, x) for an additional block x. If Eve can convince Alice to authenticate a =[a, x], she can swap a with b =[b, x] to create a forged document that appears valid. Of course, the trick is in convincing Alice to authenticate a , but it nonetheless is a concern with CBC-MAC.

When using CBC-MAC, one should also be careful not to use the key K for purposes other than authentication. A different key must be used for message confidentiality than for calculating the message authentication code. In particular, if one uses the same key for confidentiality as for authentication, then the output of CBC blocks during the encryption of a message for confidentiality could be the basis for a forgery attack against CBC-MAC.