In cryptography, a cipher block chaining message authentication code 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
previous block. 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 one
encrypts in CBC mode with zero initialization vector. The following
figure sketches the computation of the CBC-MAC of a message comprising blocks
using a secret key and a block cipher : Security with fixed and variable-length
messages If the block cipher used is secure, then
CBC-MAC is secure for fixed-length messages. However, by itself, it is not
secure for variable-length messages. Thus, any single key must only be used
for messages of a fixed and known length. This is because an attacker who
knows the correct message-tag pairs for two messages and can generate a
third message whose CBC-MAC will also be . This is simply done by XORing the
first block of with and then concatenating with this modified ;
i.e., by making . When computing the MAC for the message , it follows that we
compute the MAC for in the usual manner as , but when this value is chained
forwards to the stage computing we will perform an exclusive OR operation with
the value derived for the MAC of the first message. The presence of that tag
in the new message means it will cancel, leaving no contribution to the MAC from
the blocks of plain text in the first message : and thus the tag for is .
This problem cannot be solved by adding a message-size block to the end. There
are three main ways of modifying CBC-MAC so that it is secure for variable length
messages: 1) Input-length key separation; 2) Length-prepending; 3)
Encrypt last block. In such a case, it may also be recommended to use a
different mode of operation, for example, CMAC or HMAC to protect the
integrity of variable-length messages. = Length prepending =
One solution is to include the length of the message in the first block; in fact
CBC-MAC has been proven secure as long as no two messages that are prefixes of
each other are ever used and prepending the length is a special case of this.
This can be problematic if the message length may not be known when processing
begins. = Encrypt-last-block =
Encrypt-last-block CBC-MAC is defined as . Compared to the other discussed
methods of extending CBC-MAC to variable-length messages,
encrypt-last-block has the advantage of not needing to know the length of the
message until the end of the computation.
Attack methods As with many cryptographic schemes,
naïve use of ciphers and other protocols may lead to attacks being possible,
reducing the effectiveness of the cryptographic protection. We present
attacks which are possible due to using the CBC-MAC incorrectly.
= Using the same key for encryption and authentication =
One common mistake is to reuse the same key 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 Alice has sent to Bob the cipher text blocks . During the transmission
process, Eve can tamper with any of the cipher-text blocks and adjust any of the
bits therein as she chooses, provided that the final block, , remains the
same. We assume, for the purposes of this example and without loss of
generality, that the initialisation vector used for the encryption process
is a vector of zeroes. When Bob receives the message, he will
first decrypt the message by reversing the encryption process which Alice
applied, using the cipher text blocks . During the transmission process, Eve can
tamper with any of the cipher text blocks and adjust any of the bits
therein as she chooses, provided that the final block, , remains the same. Her
tampered version, later delivered to Bob in replacement of Alice's original, is .
Bob first decrypts the message received using the shared secret key to obtain
corresponding plain text. Note that all plain text produced will be different
from that which Alice originally sent, because Eve has modified all but the
last cipher text block. In particular, the final plain text, , differs from the
original, , which Alice sent; although is the same, , so a different plain text
is produced when chaining the previous cipher text block into the exclusive-OR
after decryption of : . It follows that Bob will now compute the
authentication tag using CBC-MAC over all the values of plain text which he
decoded. The tag for the new message, , is given by:
Notice that this expression is equal to which is exactly :
and it follows that . Therefore, Eve was able to modify the
cipher text in transit such that an entirely different message, , was
produced, but the tag for this message matched the tag of the original, and Bob
was unaware that the contents had been modified in transit. By definition, a
Message Authentication Code is broken if we can find a different message which
produces the same tag as the previous message, , with . It follows that the
message authentication protocol, in this usage scenario, has been broken, and Bob
has been deceived into believing Alice sent him a message which she did not
produce. If, instead, we use different keys for
the encryption and authentication stages, say and , respectively, this
attack is foiled. The decryption of the modified cipher-text blocks obtains
some plain text string . However, due to the MAC's usage of a different key , we
cannot "undo" the decryption process in the forward step of the computation of
the message authentication code so as to produce the same tag; each modified
will now be encrypted by in the CBC-MAC process to some value .
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. = Allowing the initialisation vector to
vary in value = When encrypting data using a block
cipher in cipher block chaining mode, it is common to introduce an initialization
vector to the first stage of the encryption process. It is typically
required that this vector be chosen randomly and that it is not repeated for
any given secret key under which the block cipher operates. This provides
semantic security, by means of ensuring the same plain text is not encrypted to
the same cipher text, allowing an attacker to infer a relationship exists.
When computing a message authentication code, such as by CBC-MAC, the use of an
initialisation vector is a possible attack vector.
In the operation of a cipher block chaining cipher, the first block of
plain text is mixed with the initialisation vector using an exclusive
OR. The result of this operation is the input to the block cipher for
encryption. However, when performing encryption and
decryption, we are required to send the initialisation vector in plain text -
typically as the block immediately preceding the first block of cipher text
- such that the first block of plain text can be decrypted and recovered
successfully. If computing a MAC, we will also need to transmit the
initialisation vector to the other party in plain text so that they can verify
the tag on the message matches the value they have computed.
If we allow the initialisation vector to be selected arbitrarily, it follows that
the first block of plain text can potentially be modified while producing
the same message tag. Consider a message . In particular, when
computing the message tag for CBC-MAC, suppose we choose an initialisation
vector such that computation of the MAC begins with . This produces a pair .
Now produce the message . For each bit modified in , flip the corresponding bit
in the initialisation vector to produce the initialisation vector . It follows
that to compute the MAC for this message, we begin the computation by .
As bits in both the plain text and initialisation vector have been flipped
in the same places, the modification is cancelled in this first stage, meaning
the input to the block cipher is identical to that for . If no further
changes are made to the plain text, the same tag will be derived despite a
different message being transmitted. If the freedom to select an
initialisation vector is removed and all implementations of CBC-MAC fix
themselves on a particular initialisation vector, this attack
cannot proceed. Standards that define the algorithm
FIPS PUB 113 Computer Data Authentication is a U.S. government
standard that specified the CBC-MAC algorithm using DES as the block cipher.
The CBC-MAC algorithm is equivalent to ISO/IEC 9797-1 MAC Algorithm 1.
See also CMAC – A block-cipher–based MAC
algorithm which is secure for messages of different lengths.
OMAC and PMAC – Other methods to turn block ciphers into message
authentication codes. One-way compression function – Hash
functions can be made from block ciphers. But note, there are significant
differences in function and uses for security between MACs and hashes.
References