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

In other words, Alice first does the natural step of computing $H((K\oplus ipad)||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 $K\oplus opad$ 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\text{,}K)$, to Bob. Since Bob knows $K$, he can compute $HMAC(m\text{,}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^{\prime }$, then $H(K\oplus ipad||m^{\prime })$ should differ from $H(K\oplus ipad||m)$ (collision resistance) and therefore $HMAC(m^{\prime }\text{,}K)$ should differ from $HMAC(K\text{,}m)$ (again, by collision resistance). Therefore, $HMAC(m\text{,}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.]

An alternative to using hash functions is to use a block cipher in CBC mode. Let $E_K()$ 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 $E_K()$ 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=(m_1\text{,}{m}_2\text{,}\cdots \text{,}{m}_l)$, where each $m_j$ is a block of the message that has the same length as the block length of the encryption algorithm $E_K()$. The last block $m_l$ may require padding in order to guarantee that it is a full block. Recall that the CBC encryption procedure is given by

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

and Alice then sends Bob $(m\text{,}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\text{,}x)=MAC(b\text{,}x)$ for an additional block $x$. If Eve can convince Alice to authenticate $a^{{}^{\prime }}=[a\text{,}x]$, she can swap $a^{{}^{\prime }}$ with $b^{{}^{\prime }}=[b\text{,}x]$ to create a forged document that appears valid. Of course, the trick is in convincing Alice to authenticate $a^{{}^{\prime }}$, 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.