When Alice sends a message to Bob, two important considerations are
Is the message really from Alice?
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 to Bob.
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 . For concreteness, assume that processes messages in blocks of 512 bits. Alice and Bob need to share a secret key . If is shorter than 512 bits, append enough 0s to make its length be 512. If is longer than 512 bits, it can be hashed to obtain a shorter key, so we assume that 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 be the message. Then Alice computes
In other words, Alice first does the natural step of computing . 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 and hashes again. This seems to be resistant to all known attacks.
Alice now sends the message , either encrypted or not, along with , to Bob. Since Bob knows , he can compute . 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 to , then should differ from (collision resistance) and therefore should differ from (again, by collision resistance). Therefore, tells Bob that the message is authentic. Also, it seems unlikely that Eve can authenticate a message without knowing , so Bob is sure that Alice sent the message.
For an analysis of the security of HMAC, see [Bellare et al.]
An alternative to using hash functions is to use a block cipher in CBC mode. Let be a block cipher, such as AES, using a secret key that is shared between Alice and Bob. We may create an appendix very similar to the output of a keyed hash function by applying in CBC mode to the entire message and using the final output of the CBC operation as the MAC.
Suppose that our message is of the form , where each is a block of the message that has the same length as the block length of the encryption algorithm . The last block may require padding in order to guarantee that it is a full block. Recall that the CBC encryption procedure is given by
where is the initialization vector. The CBC-MAC is then given as
and Alice then sends Bob .
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 correspond to the CBC-MAC of a message . Suppose that Eve has found two messages and with . Then Eve knows that for an additional block . If Eve can convince Alice to authenticate , she can swap with to create a forged document that appears valid. Of course, the trick is in convincing Alice to authenticate , but it nonetheless is a concern with CBC-MAC.
When using CBC-MAC, one should also be careful not to use the key 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.