CBC-MAC

In cryptography, a Cipher Block Chaining Message Authentication Code, abbreviated CBC-MAC, is a technique for constructing a message authentication code from a block cipher. The message is encrypted with some block cipher algorithm in CBC mode to create a chain of blocks such that each block depends on the proper encryption of the block before it. This interdependence ensures that a change to any of the plaintext bits will cause the final encrypted block to change in a way that cannot be predicted or counteracted without knowing the key to the block cipher.

To calculate the CBC-MAC of message $m$ one encrypts $m$ in CBC mode with zero initialization vector. The following figure sketches the computation of the CBC-MAC of a message comprising blocks $m\_1|m\_2|cdots|m\_x$ using a secret key $k$ and a block cipher $E$:

Variable-length messages

Given a secure block cipher, CBC-MAC is secure for fixed-length messages. However, by itself, it is not secure for variable-length messages.An attacker who knows the correct message-tag pairs $(m,$ $t)$ and $(m\text{'},$ $t\text{'})$ can generate a third message $m"$ whose CBC-MAC will also be $t\text{'}$. This is simply done by XORing the first block of $m\text{'}$ with $t$ and then concatenating $m$ with this modified $m\text{'}$, i.e. by making $m"\; =\; m\; |\; [(m\_1\text{'}\; oplus\; t)\; |\; m\_2\text{'}\; |\; dots\; |\; m\_x\text{'}]$.

This problem cannot be solved by adding a message-size block (e.g., with Merkle-Damgård strengthening) and thus it is recommended to use a different mode of operation, for example, CMAC to protect integrity of variable-length messages.

Using the same key for encryption and authentication

One common mistake is to reuse the same key $k$ for CBC encryption and CBC-MAC. Although a reuse of a key for different purposes is a bad practice in general, in this particular case the mistake leads to a spectacular attack. Suppose that one encrypts a message $m\_0\; |\; m\_1\; |\; cdots\; |\; m\_\{x-1\}$ in the CBC mode using an IV $c\_\{-1\}$ and gets the following ciphertext: $c\_0\; |\; c\_1\; |\; cdots\; |\; c\_\{x-1\}$, where $c\_i\; =\; E\_k(m\_i\; oplus\; c\_\{i-1\})$. He also generates the CBC-MAC tag for the IV and the message: $t=M(m\_\{-1\}\; |\; cdots\; |\; m\_\{x-1\}).$ Now an attacker can change every bit before the last block $c\_\{x-1\}$ and the MAC tag still be valid. The reason is that $t\; =\; E\_k(m\_\{x-1\}\; oplus\; c\_\{x-2\})\; =\; c\_\{x-1\}$ (this is actually the reason why people make this mistake so often—it allows to increase the performance by a factor of two). Hence as far as the last block is not changed the equivalence $t\; =\; c\_\{x-1\}$ holds and thus the CBC-MAC tag is correct.

This example also shows that a CBC-MAC cannot be used as a collision resistant one-way function: given a key it is trivial to create a different message which “hashes” to the same tag.

ee also

* CMAC — A block-cipher–based MAC algorithm which is secure for messages of different lengths (recommended by NIST).
* OMAC and PMAC — Other methods to turn block ciphers into message authentication codes (MACs).
* One-way compression function - Hash functions are often based on block ciphers. But note, there is a slight difference in function and purpose between MACs (such as CBC-MAC) and hashes.
* DAA — A (now obsolete) U.S. government standard instantiation of CBC-MAC.

References

# [http://www.iso.org/iso/en/CatalogueDetailPage.CatalogueDetail?CSNUMBER=31136&ICS1=35&ICS2=40&ICS3= ISO/IEC 9797-2:2002]
# [http://www.cs.ucdavis.edu/research/tech-reports/1997/CSE-97-15.pdf The security of the cipher block chaining message authentication code.]